1. AVL 트리의 개념

1. 이진 탐색 트리의 단점

이진 탐색 트리에서의 삽입, 삭제 연산을 앞에서 다루었지만,

이들 연산들은 이진 탐색 트리를 유지시키기는 하지만, 균형 트리를 보장하지는 않는다.

만약 이진 탐색 트리가 균형 트리가 아닐 경우에는 탐색의 시간이 높아지게 된다.

 

예를 들어, {5,2,8,1,7,3,9}와 같은 순서로 정수를 공백 이진 탐색 트리에 삽입하면

아래 [그림 1]과 같은 이진 탐색 트리가 만들어 진다.

그러나, 만약 {1,2,3,5,7,8,9}의 순으로 입력 된다면 [그림 2 ]와 같은 트리가 만들어 질 것이다.

 

[그림 1 ]

[그림 2 ]

위의 [ 그림 1]의 이진 탐색 트리에서 최대 비교 횟수는 3회인 반면,

[그림 2 ]의 트리에서는 7회가 된다.

이진 탐색 트리가 [그림 2 ]와 같이 경사 트리가 되면 탐색 시간은 순차 탐색과 같게 되어,

효율이 떨어진다.

따라서, 이진 탐색 트리에서 균형을 유지하는 것이 무엇보다 중요하다.

 

2. AVL 트리 개념

AVL 트리는 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인

이진 탐색 트리를 말한다.

먼저 아래의 [ 그림 1 ] 과 [ 그림 2 ]를 보자.

[ 그림 1 : AVL 트리 ]

[ 그림 2 : 비 AVL 트리 ]

위의 [그림 1] 을 보면, 모든 노드에서 양쪽 서브 트리의 높이의 차이가 1이하인 것을 볼 수 있다.

그러나 [그림 2]에서는 노드 5에서 왼쪽 서브 트리의 높이가 2인 반면,

오른쪽 서브 트리 높이가 0이므로 높이 균형을 이루지 못하고 따라서, AVL 트리가 아니다.

AVL 트리는 트리가 불균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다.

AVL트리는 균형 트리가 항상 보장된다.

 

3. AVL 트리에서 삽입

균형 인수(Balance factor)에 대해 먼저 설명해보자.

'균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이' 로 정의 한다.

모든 노드의 균형 인수가 +1 이하 이고 -1 이상이면 AVL트리이다.

위의 [그림 1]은 모든 노드의 균형 인수가 +1 이하이고, -1 이상이기 때문에 AVL 트리이며,

위의 [그림 2]에서는 노드 5와 노드 7이 균형 인수가 1 보다 큰 2 이기 때문에 AVL 트리가 아니다. 

 

균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 이유는

노드의 삽입과 삭제 연산 때문에 이루어진다.

삽입연산은 삽입되는 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다.

따라서, 새로운 노드의 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉,  균형 인수가

+2 혹은 -2가 된 가장 가까운 조상 노드의 서브 트리들에 대하여 다시 균형을 잡아야 한다.

그외의 다른 노드들은 일체 변경할 필요가 없다.

 

아래의 그림과 같이 균형을 이루는 AVL트리가 있다고 가정하자.

[그림 3 : 삽입 연산 전의 AVL 트리 ]

위의 트리에 정수1이 삽입되었다고 가정하면 아래와 같은 그림이 된다.

 

[그림 4 : 삽입 연산 후의 AVL 트리 ]

위의 그림을 보면, 노드 5 와 노드 7 이 균형인수가 2가 되어 균형이 깨지게 된다.

따라서, 여기서는 균형 인수가 2가 된 가장 가까운 조상 노드인 노드5부터 그 아래에 있는 노드들을 

다시 배치하여 균형 상태로 만들어야 한다.

그러면, 어떻게 해야 위의 그림과 같이 균형이 깨진 트리를 다시 균형있게 만들 수 있는지 생각해봐야 한다.

해결방법은 새로운 노드부터 균형 인수가 +2혹은 -2가 된 가장 가까운 조상 노드까지를 회전시키는 것이다.

위의 그림의 경우에는 노드 1, 노드 3, 노드 5를 오른쪽으로 회전 시키면 된다.

위의 그림의 노드1, 노드3,노드5를 오른쪽으로 회전시키면 아래와 같은 그림이 된다.

[그림 5 ]

즉, 위의 그림과 같이 다시 균형 트리를 이루게 된다.

[그림 4]에서 [그림 5]를 보면, 다른 노드들은 변경시키지 않았다.

 

AVL 트리에서 균형이 깨지는 경우에는 아래와 같이 4가지의 경우가 있다.

새로 삽입된 노드N으로부터 가장 가까우면서 균형 인수가 +2혹은 -2가 된 조상 노드를 A라고 하자.

 

1. LL타입 : N이 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입된다.

2. RR타입 : N이 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 삽입된다.

3. RL타입 : N이 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 삽입된다.

4. LR타입 : N이 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입된다.

 

재균형시키는 방법도 각 경우에 따라 달라진다.

아래는 각 각의 경우에 대하여 균형 트리로 다시 만드는 방법이다.

 

1. LL회전 : A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다.

2. RR회전 : A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다.

3. RL회전 : A부터 N까지의 경로상의 노드들을 오른쪽 - 왼쪽으로 회전시킨다.

4. LR회전 : A부터 N까지의 경로상의 노드들을 왼쪽 - 오른쪽으로 회전시킨다.

 

4. 시뮬레이션

위의 알고리즘 대로 시뮬레이션을 진행해보자.

{7,8,9,2,1,5,3,6,4} 가 있다고 하자.

데이터를 하나씩 삽입해보자.

 

(1). 숫자 7 삽입

현재 아무것도 추가된 데이터 없이 숫자7이 삽입이 되었으므로, 아래와 같은 그림이 된다.

 

(2). 숫자 8 삽입

 

(3). 숫자 9 삽입

위에서 균형 인수가 -2가 됐으므로, 트리의 재조정이 필요하며 RR회전을 해야 한다.

RR회전을 하자.

 

(4). 숫자 2 삽입

 

(5). 숫자 1 삽입

위에서 균형 인수가 2가 되었으므로, LL회전을 한다.

 

(6). 숫자 5 삽입

위의 경우는 LR회전을 해야 한다. 아래의 그림이 LR회전 후의 그림.

 

(7). 숫자 3을 삽입

 

(8). 숫자 6 삽입

 

(9). 숫자 4 삽입

그리고 RL회전을 해야 한다.

최종적인 형태는 위의 그림이다.