Среднее расстояние узла от корня в алгоритме взвешенного быстрого объединения?

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 ++ (Роберт Седжвик).

Я знаю наихудшее расстояние, но может кто-нибудь подсказать мне правильный способ вычисления среднего расстояния?

Наихудший сценарий - это слияние двух деревьев с одинаковым количеством узлов. допустим, дерево слияния 2, каждое из которых имеет 2 ^ n узлов, в результате дерево [= size 2 ^ ( n + 1 ) узлов] будет иметь n + 1 max расстояние любого узла от root (более 1 после слияния).

В худшем случае - если размер дерева равен 2 ^ n, расстояние от корня до любого узла всегда меньше n.

Как мы можем вычислить среднее расстояние, если максимальное расстояние равно n для 2 ^ n дерева узлов?

Answer 1

В худшем случае, как вы сказали, вы всегда добавляете два дерева одинаковой высоты. Для этого вам нужно: 2 дерева высотой n-1, а для достижения этого вам нужно 4 дерева высотой n-2, ....

В конце, вам нужно n деревьев высотой 1, n / 2 деревьев высоты 2, ..., 1 дерево высоты n .

Так как это ваша домашняя работа, я сделаю подсказку, как продолжить:

Используйте предварительное наблюдение и следуйте алгоритму для построения деревьев и «достижения» наихудшего случая. Обратите внимание, сколько листьев на каждой глубине - если вы строите дерево таким образом [, начните с примеров частных случаев , n = 1,2,3 и посмотрите, как оно «ведет себя»]
Если вам нужно формально доказать это - это, вероятно, следует сделать индукцией по высоте [n].