AVL 트리

AVL 트리는 값을 추가하거나 삭제할 때 스스로 균형을 잡는 이진 탐색 트리이다.

이 트리는 두 자식 트리의 높이가 항상 최대 1만큼 차이나야 하며 차이가 1보다 커지면 스스로 트리를 회전하여 균형을 잡으며 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다.

검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간 복잡도가 걸린다. 

 

회전

트리의 자식 노드 간 차수의 차가 1보다 커지게 되면 균형이 맞지 않다고 보고 트리를 재구성하는데 이 작업을 회전이라 한다.

회전하는 모양에 따라서 LL 회전, LR 회전, RR 회전, RL 회전이라고 할 수 있다.

각 회전을 구분하는 방법은 회전하는 노드가 왼쪽 자식 노드, 왼쪽 자식 노드이면 LL, 오른쪽 자식 노드, 오른쪽 자식 노드이면 RR, 등 과 같다.

 

아래 불군형한 AVL 트리가 있다.(마지막으로 9가 추가됨)

    10
   /
  8
   \
    9

위 트리를 회전하면 아래와 같이 변경되며 이는 LR 회전이다.

    9
   / \
  8  10

회전하는 노드에 자식 노드가 있을 경우(마지막 5가 추가됨)

      10
     /  \
    8   12
   / \
  6   9
 /
5

다음과 같이 변경되며 이는 LL 회전이다.

     8
    / \
   6   10
  /    / \
 5    9   12

자식 노드를 배치하는 것은 불균형 상태가 된 노드를 회전한 후 왼쪽 자식엔 작은 노드를 오른쪽 노드엔 큰 노드를 배치한다고 생각하면 쉽다.

 

추가

트리에 새로운 노드를 추가하는 방법은 트리에서 새 노드를 루트 노드에서부터 크면 오른쪽 작으면 왼쪽으로 자리를 찾아가다가 단말 노드를 찾으면 해당 노드의 자식 노드로 추가한다.

새 노드를 삽입하여 트리가 불균형해지면 균형이 깨진 세 개의 노드를 기준으로 회전시켜 균형을 맞춘다.

 

삭제

트리에서 노드를 삭제하는 방법은 노드를 검색하여 노드가 단말 노드가 아니라면 자신의 왼쪽 부분 트리 중에서 최댓값을 갖는 노드나 오른쪽 부분 트리 중에서 최솟값을 갖는 노드와 바꾼다. 이 작업을 노드가 단말 노드가 될 때까지 반복하여 단말 노드를 삭제한다.

삭제했을 때 트리가 불균형해지면 삽입과 동일한 방법으로 노드의 부모를 회전시켜 균형을 맞춘다.