최소 Heigth AVL 트리

Question

AVL-Tree의 최소 노드 수를 증명하는이 (http://condor.depaul.edu/ntomuro/courses/417/notes/lecture1.html) 논문을 방금 읽었습니다. 그러나 O (log n)가 노드의 수를 전혀 언급하지 않기 때문에 결과의 의미를 이해할 수 없습니다. 어떻게 증명 될 수 있습니까? 그러나 첫 번째 단계와 반복이 어떻게 단순화되는지는 알 수 있습니다. 그러나 네 번째 단계가 끝나면 나는 그가 정확히 무엇을하고 있는지 이해하지 못하고있다. (비록 내가 막연하게 상상할 수는 있지만). 아무에게 나에게 설명 할 수 있겠습니까? 마지막 몇 줄을 증명하고 파트 1의 끝에서 표현을 어떻게 단순화하고 있습니까?

감사합니다.

Answer 1

O (logn)은 노드를 나타냅니다. "n"은 노드 수를 나타냅니다. 각 후속 레벨의 노드 수가 두 배가된다는 것을 알면 직관적으로 생각할 수 있습니다. AVL 트리이므로 노드를 다음 수준으로 밀어 넣기 전에 이전 수준이 가득 차 있어야합니다. 이렇게하면 각 레이어가 노드 수를 두 배로 늘리기 때문에 트리 높이를 logn으로 제한합니다. 즉, 노드 수는 nodes = 2^height - 1로 작성할 수 있습니다. 높이와 라운드를 풀 때 logn을 얻습니다.