加权快速联合算法中节点与根的平均距离？

Question

Compute the average distance from a node to the root in a worst-case tree of 
2^n nodes built by the weighted quick union algorithm? 

这是C++算法练习（Robert Sedgewick）。

我知道最坏的情况下的距离，但有人可以建议我正确的方法来计算平均距离？

最糟糕的情况是合并具有相同数量节点的2棵树。可以说合并2棵树，每棵树有2^n个节点，生成树[=大小2 ^（n + 1）个节点]将具有n + 1 max任何节点距离根的距离（合并后超过1） 。

在最坏的情况下 - 如果树大小为2^n，从根节点到任何节点的距离总是小于n。

如果2^n节点树的最大距离为n，那么我们如何计算平均距离？

Answer 1

最糟糕的情况是，如你所说，你总是添加两棵相同高度的树。为了实现它，你需要：2棵高度为n-1的树，并且为了达到它你需要4棵高度为n-2的树......。

最后，你需要n棵高度为1，n/2高度为2的树，...，高度为1的树n。

使用prvious观察，并按照算法来构建树和“实现”最糟糕的情况：

因为这是你的功课，我会通过暗示你如何继续进行。请注意每个深度有多少树叶 - 如果您以此方式构建树木[以私人案例，n = 1,2,3为例并查看它如何“表现”]
如果您需要正式证明它 - 应该可能通过在高度[n]上的感应完成。