AVL 트리

탐색 순서와 높이

이진 탐색 트리의 키 순서를 지키면서 높이 조건을 추가한다. 왼쪽과 오른쪽 노드 수가 같아야 하는 것은 아니다. 균형 조건은 루트 한 곳에서만 검사하는 것이 아니라 모든 노드에 적용하며, 부분 트리도 같은 조건을 만족해야 한다.

편향을 줄이는 방법

삽입이나 삭제로 높이 조건이 깨지면 연결을 바꾸는 회전을 사용한다. 회전은 중위 순회에서 얻는 키 순서를 보존하면서 부분 트리의 모양을 바꾼다. 긴 쪽으로 한 번 회전하는 것으로 충분한 경우와 먼저 자식 쪽을 회전한 뒤 다시 회전하는 경우를 구분한다.

높이가 로그로 제한되는 이유

높이 h를 만드는 최소 노드 수를 N(h)라 하면 두 자식의 최소 높이는 h−1과 h−2가 된다. 따라서 N(h)=1+N(h−1)+N(h−2)라는 관계가 나온다. 높이를 하나씩 늘리는 데 필요한 최소 노드 수가 지수적으로 증가하므로 반대로 높이는 노드 수의 로그 수준으로 제한된다.

갱신 때의 처리

일반적인 구현은 노드 높이나 균형 정보를 함께 관리한다. 삽입과 삭제 후에는 영향을 받은 조상 경로의 정보를 갱신하고 필요한 위치에서 균형을 복구한다. 한 번의 국소 회전 비용이 작다는 사실과 전체 갱신 비용을 구분해야 하며 탐색 경로를 포함한 표준 연산은 O(log n)이다.