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

Question

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

3

我正在阅读由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

如果所有子树大小都是等可能的，这对于二叉搜索树是正确的（因为子树大小仅取决于插入到树中的第一个元素的相对排名），但不适用于二叉树，则D(i)和D(n-i-1)的平均值为（1/n）从j=0到n-1的D(j)之和。这产生了下面的公式。 D(n) = (2/n)（从j=0到n-1的D(j)之和）+ (n-1)。以上关系获得D(n)的平均值为O(nlogn)。

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

1.作者的意思是“由于子树大小只取决于插入到树中的第一个元素的相对排名”，这是什么意思？

2.作者如何从D(n)得到平均值O(nlogn)? 有人能展示一下实现所述结果涉及的步骤吗？

谢谢！

- venkysmarty

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ricky Bobby · 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 j ) + 2

由于 D(n) = (2/n)(sum from j = 0 to n-1 of D(j)) + (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