加重クイックユニオンアルゴリズムでノードからルートまでの平均距離は？

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 ^（N + 1）ノードは】ルート（マージ後の1以上）から任意のノードのN + 1の最大距離を持つことになり、各ツリーを得、2^n個のノードを有する2ツリーをマージすると言うことができ。最悪の症例において

ツリーサイズは2^Nである場合、ルートノードからの任意の距離は常にnよりも小さいです。

最大距離は、nが2^n個のノードツリーのためであれば、我々は平均距離を計算することができますどのように

？

Answer 1

あなたが言ったように最悪の場合、常に同じ高さの2つのツリーを追加します。それを達成するためには、高さn-1の樹木が2つ必要です。それを達成するには、高さn-2の樹木が4つ必要です....

最後に、n個の樹木が必要です1、n/2ツリーの高さ2、...、1ツリーの高さn。

これはあなたの宿題ですので、私は継続する方法を説明しますヒンティングによって行われますに：

prvious観察を使用し、木を構築し、最悪の場合を「達成」するためのアルゴリズムに従ってください。
ツリーをこのように構築する場合は、[プライベート例としてで始まり、N = 1,2,3、どのようにそれが「振る舞い」を参照してください。]あなたが正式に証明する必要がある場合 - 各深さにありますどのように多くの葉に注意してくださいそれはおそらく高さ[n]の誘導によって行われるはずです。