AVL 트리

균형잡힌 트리가 아니다.

 

이진 탐색 트리가 편향 트리이면 최악의 경우 O(h)의 시간복잡도를 가진다. 항상 O(logh)의 시간복잡도를 유지하려면 트리의 균형을 맞추어야 한다. AVL 트리는 균형 잡힌 트리 중 하나이다. AVL 트리에서는 균형의 정도를 표현하기 위해 균형 인수를 사용한다.

 

균형 인수는 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이이다. 

균형을 잡기 위해 트리를 재조정할 때, 균형 인수의 절댓값이 크면 클수록 트리의 균형이 무너진 상태이다. 

균형 인수의 절대값이 1 이하여야 균형 잡힌 트리라고 할 수 있다.

 

트리의 균형을 잡는 방법은 Rebalancing, Refactoring 등으로 부른다.

 

재조정이 필요한 상태는 크게 4가지이다.

1) Left Left 상태

루트 노드의 균형 인수가 +2인 경우. 왼쪽 서브트리의 높이가 높으므로 트리는 왼쪽으로 치우쳐졌다.

이 불균형을 해소하기 위해 LL회전을 수행한다. LL회전은 오른쪽으로 회전해 왼쪽 서브트리의 높이를 낮춘다.

- LL상태인 트리에서 root 노드를 왼쪽 자식노드로 옮긴다.

- 이때 왼쪽 자식노드의 자식노드가 2개일 때, 오른쪽 서브트리를 root 노드의 왼쪽 자식노드로 옮긴다.

- 루트 노드의 균형 인수가 +2이면, LL회전을 한번 수행한다. 왼쪽 서브트리 높이-1, 오른쪽 서브트리 높이+1이 되므로 균형 인수는 0이다.

 

2) Right Right 상태

루트 노드의 균형 인수가 -2인 경우. 오른쪽 서브트리의 높이가 높으므로 트리는 오른쪽으로 치우쳐졌다.

이 불균형을 해소하기 위해 RR회전을 수행한다. RR회전은 왼쪽으로 회전해 오른쪽 서브트리의 높이를 낮춘다.

- RR상태인 트리에서 root 노드를 오른쪽 자식노드로 옮긴다.

- 이때 오른쪽 자식노드의 자식노드가 2개일 때, 왼쪽 서브트리를 root 노드의 오른쪽 자식노드로 옮긴다.

- 루트 노드의 균형 인수가 -2이면, RR회전을 한번 수행한다. 왼쪽 서브트리 높이+1, 오른쪽 서브트리 높이-1이 되므로 균형 인수는 0이다.

 

3) Left Right 상태

LR상태는 자식이 왼쪽으로 하나 있고, 자식노드의 자식이 오른쪽에 하나 있는 상태이다.

LR상태는 한번의 회전으로는 균형을 맞출 수 없다. 부분 RR회전과 전체 LL회전, 2번 회전이 필요하다.

- 먼저 트리를 LL상태로 만들어야 한다.

- 오른쪽 자식노드만 가지고 있는 노드를 root로 한 서브트리를 분리한다.

- 오른쪽 자식노드를 가지고 있어 RR회전이 가능하다. RR회전으로 root는 왼쪽 자식노드에, 자식노드는 root로 이동한다.

- 서브트리를 트리에 붙인다. 이렇게 만들어진 트리는 LL상태이다.

- LL회전을 시켜서 균형을 잡을 수 있다.

 

4) Right Left 상태

RL상태는 자식이 오른쪽으로 하나 있고, 자식노드의 자식이 왼쪽에 하나 있는 상태이다.

RL상태 역시 한번의 회전으로는 균형을 맞출 수 없다. 부분 LL회전, 전체 RR회전이 필요하다.

- 먼저 트리를 RR상태로 만들어야 한다.

- 왼쪽 자식노드만 가지고 있는 노드를 root로 한 서브트리를 분리한다.

- LL회전을 한다. root는 오른쪽 자식노드에, 자식노드는 root 자리로 이동한다.

- 서브트리를 트리에 붙인다. 이렇게 만들어진 트리는 RR상태이다.

- RR회전을 시켜서 균형을 잡을 수 있다.

 

 

정리 이미지