n AVL 트리 합치기

Question

크기가 n_1, n_2, ..., n_n 인 n 개의 AVL 트리가 있으므로 sum (n_i) = n이됩니다. 두 개의 AVL을 더 큰 크기의 선형 시간으로 병합 할 수 있습니다. 이 n 개의 나무를 얼마나 오래 병합 할 수 있습니까? 임의의 도움을위한 Thy

Answer 1

다른 나무가 k 개있는 경우 합계 (k - 1) 병합을 수행하여 함께 하나의 나무로 모아야합니다. 그래서 문제는 각 머지가 얼마나 걸릴지입니다.

언제든지 두 개의 가장 작은 나무를 항상 병합한다는 전략을 채택한다고 가정 해보십시오. 이렇게 할 때 m 개의 트리를 사용할 수 있다면 두 번째로 작은 트리의 크기가 병합의 런타임을 지배하게됩니다. 이 크기는 최대 (n - 1)/(k - 1)이며, 가장 작은 트리에 요소가 하나만 있고 다른 모든 트리에는 요소가 모두있는 경우에 발생합니다. 이것은 당신이 병합 케이 할 경우, 비용이

N - 1 N - 1 N - 1   N - 1 
----- + ----- + ----- + ... + ----- 
K - 1 K - 2 K - 3   1 

수 있다는 것을 의미하지만이 (N - 1)이다 (K - 1) H, H는 (K-1)가 (K-1) 일입니다 harmonic number. 이 전체 식은 O (n log k)이므로 병합하는 동안 수행 된 전체 작업은 O (n log k)입니다.

그러나 위에는 각 지점에서 가장 작은 두 개의 나무를 찾는 쉬운 방법이 있습니다. 이것은 크기가 내림차순으로 트리를 저장하는 우선 순위 큐를 사용하여 수행 할 수 있습니다. 트리에서 대기열에서 대기열 제거를 두 번 수행 한 다음 대기열 대기열을 하나씩 수행하므로 모든 우선 순위 대기열 작업의 총 시간은 O (k log k)입니다. 이것은 또한 O (n log k)이므로 알고리즘의 총 런타임은 O (n log k)입니다.

자신의 AVL 트리 (k = n)에서 n 개의 노드로 시작할 수 있기 때문에 이보다 훨씬 더 잘할 수 없다고 확신합니다. 만약 당신이 Ω (n log n)보다 빠른 병합을 할 수 있다면, 더 작은 모든 나무들을 합쳐서 형성된 AVL 트리를 생성하여 비교만을 사용하여 Ω (n log n)보다 빨리 소팅 할 수 있습니다. 그리고 나서 O에서 inorder traversal을 수행합니다. n) Ω (n log n)보다 나은 정렬 시간. is known to be impossible.

희망이 도움이됩니다.