가중치 조합 알고리즘에서 루트와 노드의 평균 거리?

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 개의 노드를 갖는 병합을 수행한다고 가정하면 결과 트리 [= 크기 2^(n + 1) 노드]는 n + 1 최대 루트에서 모든 노드까지의 거리 (병합 후 1보다 큼) .

트리 크기가 2^n 인 경우 루트에서 노드까지의 거리가 항상 n보다 작습니다.

2^n 노드 트리의 최대 거리가 n 인 경우 평균 거리를 어떻게 계산할 수 있습니까?

Answer 1

당신이 말했듯이, 최악의 경우는 항상 같은 높이의 나무 두 개를 더합니다. 그것을 달성하기 위해서는 높이 n-1의 나무 2 그루를 얻고 높이 n-2의 나무 4 개가 필요합니다. ...

마지막으로 너는 n 개의 나무가 필요합니다. 1, n/2 나무의 높이 2, ..., 1 나무의 높이 n.

이 나무를 구축하고 최악의 경우를 "달성"하는 알고리즘을 prvious 관찰를 사용하여 수행 :이 숙제이기 때문에

는 어떻게 계속하는 방법을 암시에 의해 수행됩니다. 각 깊이에 몇 개의 잎이 있는지 확인하십시오. - 이렇게하면 나무를 만들 수 있습니다. 개인 사례의 사례로 시작하십시오., n = 1,2,3 및 어떻게 작동하는지보십시오.
공식적으로 증명해야하는 경우 그것은 아마도 높이 [n]에 유도에 의해 이루어져야합니다.