algorithm - 二叉搜索树内部路径长度分析

Question

我正在阅读 Mark Allen Weiss 的《数据结构和算法》一书中关于树的一章。这是文本片段。

Let D(n) be the internal path length for some tree T of n nodes. D(1) = 0. An n-node tree consists of an i-node left subtree and an (n - i - 1)-node right subtree, plus a root at depth zero for 0<= i < n. D(i) is the internal path length of the left subtree with respect to its root. In the main tree, all these nodes are one level deeper. The same holds for the right subtree. Thus, we get the recurrence

D(n) = D(i) + D(n - i -1) + n -1

If all subtree sizes are equally likely, which is true for binary search trees (since the subtree size depends only on the relative rank of the first element inserted into the tree), but not binary trees, then the average value of both D(i) and D(n - i -1) is (1/n) sum from j =0 to n-1 of D(j). This yields

D(n) = (2/n)(sum from j = 0 to n-1 of D(j)) + (n-1).

The above recurrence obtains an average values of D(n) = O(nlogn).

以下是我对上述文本片段的问题。

1. 作者的意思是“因为子树的大小仅取决于插入树中的第一个元素的相对等级”？
2. 作者如何从 D(n) 中获得平均值 O(nlogn)？任何人都可以告诉我实现上述结果所涉及的步骤吗？

谢谢!

Answer 1

关于你的第一点:

在二叉树中，左子树的大小对应于小于根的元素的个数，右子树的大小对应于大于根的元素的个数。

因此，子树的大小仅取决于插入的第一个元素的相对等级。

关于你的第二点，我没有解决方案，但我会这样开始:

您可以先转换总和:

你知道 sum(j=0 to n, of j ) = n*(n-1)/2

然后 n-1 = 2/n*sum(j=0 to n-1, of 1 ) +2/n*n = 2/n*sum(j=0 to n-1, of 1 j) + 2

由于 D(n) = (2/n)(从 j = 0 到 D(j) 的 n-1 的总和)+ (n-1)，您得到新公式

D(n) = (2/n)(sum from j = 0 to n-1 of (D(j) + j)) + 2 (1)

现在你可以用 Dn-1 来表达 Dn

你会发现(如果我是对的):

D(n)= (n+1)/n*D(n-1) + 2  (2)

然后尝试将 Dn 表示为 n*Sum(1/k) 等价于 nln(n)...

由上面的公式(2)得到(你可以试试写):

D(n) = n+1 * SUM( 2 /k for k=1 to n) +2 ... which is a O(n ln(n))

如果你对这个证明有更多问题，请告诉我

希望对你有帮助

---

编辑:关于 (2) 的详细信息

D(n) = (2/n)(sum from j = 0 to n-1 of (D(j) + j)) + 2

=> D(n) = (2/n)(sum from j = 0 to n-2 of (D(j) + j)) + 2 + (2/n)*(D(n-1)+n-1)

=> D(n) = ((n-1)/n)* [ 2/(n-1) *(sum from j = 0 to n-2 of (D(j) + j)) + 2]  + 2 + (2/n)*D(n-1)

note: the +2 between the brackets comes  from (2/n)*(D(n-1)+n-1) =  (2/n)*D(n-1) + 2 *(n-1)/n

between the brackets [] you have D(n-1) then :

=>  D(n) = ((n-1)/n)* D(n-1)  + 2 + (2/n)*D(n-1)

=> D(n) = (n+1)/n*D(n-1) + 2