[자료구조] AVL트리란? AVL트리 쉽게 이해하기, AVL트리 시뮬레이터

AVL 트리란?

예전에 이진탐색트리에 대해 알아본적이 있다.

[자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현

 

[그림 1] 편향 트리(Skewed Tree)

 

이진탐색트리는 큰 문제점이 있으니, 위 그림과 같이 한쪽으로 노드가 쏠릴 수가 있다. 10,9,8,7,6을 순서대로 삽입한다고 생각해보면 저런 형태의 트리가 만들어진다는 것을 알 수 있을 것이다.

 

위와 같은 형태의 트리에서 특정 값을 찾으려면 O(N)의 시간이 필요할 것이다. 예를 들어 6을 찾으려면 모든 노드를 탐색해야지 찾을 수 있다. 따라서 성능이 매우 나빠지게 된다. 

 

[그림 2] "그림 1"을 AVL트리로 만든 그림

 

이런 단점을 극복할 수 있는 자료구조가 AVL트리이다. 예를 들어 [그림 1]의 편향트리를 [그림 2]처럼 AVL 트리로 재구성하면 어떤 노드를 탐색하든 O(log N)에 탐색할 수 있다. AVL트리는 다음과 같은 특징을 가진다.

1. 이진 탐색 트리의 속성을 가진다.
2. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
3. 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다.
4. 삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다. (N : 노드의 개수)

그렇다면, AVL트리가 어떻게 균형을 잡는지 회전 과정을 알아보자.

 

Balance Factor(BF)

회전 과정에 대해 알아보기 전에 알아야 할 것이있다. AVL트리는 균형이 무너졌는지에 대해 판단할 때 Balance Factor라는 것을 활용한다. 이는 아래와 같은 공식으로 구한다.

 

BF(K) = K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이

 

 

[그림 3] Balance Factor(BF)

 

예를 들어 위 그림을 보면 BF를 어떻게 구할지 감이 잡힐 것이다. 

AVL트리는 모든 노드의 BF가 -1,0,1 중 하나여야 한다. 만약 이를 벗어나면 균형이 깨졌다는 것을 의미하고, 이때 회전이 필요한 것이다.

 

회전에 대해 설명하기 전에 T1, T2..등은 서브트리를 의미하고, 회전의 기준은 z노드라고 가정하자.

 

우회전 (Right Rotation) 

[그림 4] 우회전(Right Rotation)

우회전의 수행과정은 다음과 같다.

 

1. y노드의 오른쪽 자식 노드를 z노드로 변경한다.
2. z노드 왼쪽 자식 노드를 y노드의 오른쪽 서브트리(T2)로 변경한다.

 

좌회전(Left Rotation)

[그림 5] 좌회전(Left Rotation)

좌회전의 수행과정은 다음과 같다.

 

1. y노드의 왼쪽 자식 노드를 z노드로 변경한다.
2. z노드 오른쪽 자식노드를 y노드의 왼쪽 서브트리(T2)로 변경한다.

 

이렇게 좌회전과 우회전에 대해 알아보았다.

AVL트리는 LL, LR, RL, RR 4가지의 균형이 무너진 경우가 존재한다. 각각 해결법을 알아보자.

 

LL(Left Left) Case

[그림 6] LL Case 해결법

위 그림처럼 BF가 -1~1을 벗어난 노드를 기준으로 왼쪽, 왼쪽 노드가 존재한다면 LL Case이다.

이때 해당 노드를 기준으로 우회전을 적용하면 불균형이 해소된다.

 

RR(Right Right) Case

[그림 7] RR Case 해결법

 

위 그림처럼 BF가 -1~1을 벗어난 노드를 기준으로 오른쪽, 오른쪽 노드가 존재한다면 RR Case이다.

이때 해당 노드를 기준으로 좌회전을 적용하면 불균형이 해소된다.

 

LR(Left Right) Case

[그림 8] LR Case 해결법

 

위 그림처럼 BF가 -1~1을 벗어난 노드를 기준으로 왼쪽, 오른쪽 노드가 존재한다면 LR Case이다.

이때 먼저 BF에 이상이 있는 노드(값이 4인노드)의 왼쪽 자식노드(값이 2인 노드)를 기준으로 좌회전을 진행한다.

이후 BF에 이상이 있는 노드(값이 4인 노드)를 기준으로 우회전을 진행하면 불균형이 해소된다.

 

RL(Right Left) Case

[그림 9] RL Case 해결법

 

위 그림처럼 BF가 -1~1을 벗어난 노드를 기준으로 오른쪽(Right), 왼쪽(Left) 노드가 존재한다면 RL Case이다.

이때 먼저 BF에 이상이 있는 노드(값이 4인노드)의 오른쪽 자식노드(값이 4인 노드)를 기준으로 우회전을 진행한다.

이후 BF에 이상이 있는 노드(값이 4인 노드)를 기준으로 좌회전을 진행하면 불균형이 해소된다.

 

AVL 트리 시뮬레이터

사실 설명을 봐도 이해가 잘 안될 수 있다. 이해하면 쉬운 개념이지만 처음 접하면 이해하기 까다롭다.

AVL Tree Visualzation

위 사이트는 AVL트리의 삽입과 삭제 과정을 눈으로 확인 할 수 있다. 한 번 이용해보면서 AVL트리에 대해 완벽히 이해해보도록 하자.

 

 

---