AVL 트리

AVL 트리는 이진 탐색 트리의 일종으로, 서브트리의 높이 차이가 최대 1인 자가 균형 트리다.

이진 트리는 왼쪽과 오른쪽 서브트리에 대략 같은 수의 노드가 있을 때 균형이 잡혔다고 한다. 이렇게 되면 트리 탐색이 매우 빠르다. 하지만 이진 탐색 트리가 균형이 잡히지 않으면 탐색 속도가 크게 느려질 수 있다.

다음은 균형이 잡히지 않은 트리의 예시다:

모든 자식 노드가 왼쪽 가지에만 있고 오른쪽 가지에는 없다. 이는 사실상 연결 리스트와 같다. 결과적으로 탐색 시간은 이진 탐색 트리에서 기대하는 빠른 O(log n) 대신 **O(n)**이 된다.

이 트리의 균형 잡힌 버전은 다음과 같다:

이진 탐색 트리를 균형 잡히게 만드는 한 가지 방법은 노드를 완전히 무작위 순서로 삽입하는 것이다. 하지만 이 방법은 성공을 보장하지 않을 뿐만 아니라 항상 실용적이지도 않다.

다른 해결책은 자가 균형 이진 트리를 사용하는 것이다. 이 자료구조는 노드를 삽입하거나 삭제한 후에도 트리가 균형을 유지하도록 조정한다. 이러한 트리의 높이는 *log(n)*으로 보장되며, 여기서 n은 노드의 수다. 균형 잡힌 트리에서는 모든 삽입, 삭제, 탐색 연산이 O(log n) 시간에 수행된다. 이는 매우 빠른 속도를 의미한다. ;-)

AVL 트리 소개

AVL 트리는 트리를 왼쪽 또는 오른쪽으로 "회전"시켜 불균형을 해결한다.

AVL 트리에서 노드는 두 서브트리의 "높이" 차이가 최대 1일 때 균형 잡혔다고 본다. 모든 노드가 균형 잡혀 있으면 트리 전체가 균형 잡힌 상태다.

노드의 높이는 해당 노드에서 가장 낮은 리프 노드까지 가는 단계 수를 의미한다. 예를 들어, 아래 트리에서 A에서 E까지 가려면 세 단계가 필요하므로 A의 높이는 3이다. B의 높이는 2, C의 높이는 1이며, 나머지 노드는 리프 노드이므로 높이가 0이다.

앞서 언급했듯이, AVL 트리에서 노드는 왼쪽과 오른쪽 서브트리의 높이가 같을 때 균형 잡혔다고 본다. 정확히 같을 필요는 없지만, 높이 차이가 1을 넘어서는 안 된다. 다음은 모두 균형 잡힌 트리의 예시다:

하지만 아래 트리들은 왼쪽 서브트리의 높이가 오른쪽 서브트리보다 너무 커서 균형이 깨진 상태다:

왼쪽과 오른쪽 서브트리의 높이 차이를 균형 인수라고 한다. 이 값은 다음과 같이 계산한다:

balance factor = abs(height(left subtree) - height(right subtree))

삽입이나 삭제 후 균형 인수가 1보다 커지면 AVL 트리의 해당 부분을 재균형해야 한다. 이때 회전을 사용한다.

트리 회전

각 트리 노드는 현재 균형 인수를 변수로 관리한다. 새로운 노드를 삽입한 후, 부모 노드의 균형 인수를 업데이트해야 한다. 균형 인수가 1보다 커지면, 트리의 일부를 "회전"시켜 균형을 복원한다.

회전에 사용하는 용어는 다음과 같다:

루트(Root) - 회전할 서브트리의 부모 노드
피벗(Pivot) - 회전 후 루트 위치가 될 노드
회전 서브트리(RotationSubtree) - 피벗의 회전 방향에 있는 서브트리
반대 서브트리(OppositeSubtree) - 피벗의 회전 반대 방향에 있는 서브트리

오른쪽 (시계 방향) 회전을 사용해 불균형 트리를 균형 잡는 예를 살펴보자:

회전 단계는 다음과 같다:

회전 서브트리를 루트의 새로운 반대 서브트리로 할당한다.
루트를 피벗의 새로운 회전 서브트리로 할당한다.
최종 결과를 확인한다.

위 알고리즘을 의사 코드로 표현하면 다음과 같다:

Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot

이 작업은 상수 시간 복잡도(O(1))를 가진다. 삽입 작업은 최대 2회의 회전만 필요하다. 삭제 작업은 최대 log(n) 회전이 필요할 수 있다.

코드 분석

AVLTree.swift 파일에 있는 대부분의 코드는 일반적인 이진 탐색 트리와 동일하다. 이진 탐색 트리를 구현한 어떤 코드에서도 볼 수 있는 내용이다. 예를 들어, 트리 검색은 완전히 동일하다. AVL 트리가 약간 다르게 동작하는 부분은 노드 삽입과 삭제뿐이다.

참고: 이진 탐색 트리의 기본 동작에 대해 잘 모르겠다면, 먼저 이 부분을 공부하는 것을 추천한다. AVL 트리의 나머지 부분을 이해하는 데 도움이 될 것이다.

흥미로운 부분은 노드 삽입 또는 삭제 후에 호출되는 balance() 메서드에 있다.

AVL 트리

AVL 트리 소개

트리 회전

코드 분석

관련 자료