0
예를 들어, 값 10, 9 ... 1의 노드가 단일 왼쪽 분기에서 내림차순으로 정렬 된 경우 트리에서 균형 잡힌 AVL 트리를 만들기 위해 어떻게 회전을 수행 할 수 있습니까? 나는 하나의 올바른 회전을 반복 할 생각 이었지만 누군가가 여기에 일련의 단계를 보여줄 수 있습니까?트리를 단일 분기로 균형을 맞추는 방법은 무엇입니까?
A
답변
2
5가 맨 위에 올 때까지 루트에서 회전하지 마십시오. 이제 트리가 거꾸로되어 있습니다. 이제 두 하위 트리 각각에서 비슷한 작업을 수행하십시오.
단일 왼쪽 분기 트리를 뒤집어 하나의 오른쪽 분기 트리 (포도 나무라고 함)를 만든 다음 포도 나무를 트리로 변환 할 수 있습니다. [rebalance tree.pdf] (http://web.eecs.umich.edu/~qstout/pap/CACM86.pdf)에 링크하십시오. – rcgldr