AVL 트리(AVL Tree)

 이전 포스팅에서 완전 이진 탐색 트리에 대해 설명했지만 이 포스팅을 통해 들어온 사람들을 위해 다시 설명한 후 AVL트리를 설명하겠다.

 

완전 이진 탐색 트리(Complete Binary Search Tree)

---

 이진 탐색 트리는 자료를 탐색하는데 최적화된 트리이다. 하지만 자료가 오름차순이나 내림차순과 같은 순서대로 입력되면 트리가 한쪽으로만 만들어지는 형태가 된다. 이는 연결 리스트와 다를 바 없는 형태로 이진 탐색 트리의 장점인 빠른 검색 속도를 이용하지 못한다. 이를 해결하기 위해 나온 것이 완전 이진 탐색 트리이다. 

 

 완전 이진 탐색 트리(Complete binary search tree)는 완전 이진 트리의 성질을 가지는 이진 탐색 트리이다. 완전 이진 탐색 트리는 편향된 이진 탐색 트리와는 다르게 항상 O(log n)의 검색 속도를 보장한다. 그러나 완전 이진 탐색 트리의 단점은 트리에 자료가 삽입될 때마다 완전 이진 탐색 트리의 형태를 유지하기 위해 트리의 모양을 바꾸어야 한다. 즉, 삽입할 때 많은 시간이 소요된다는 것이다. 삽입이 적고 탐색이 많은 경우에는 유리할 수 있으나 삽입하는 빈도수가 높아지면 높아질수록 효율성이 떨어진다. 이런 불편함을 해결한 것이 AVL트리이다.

 

AVL 트리란?(What is an AVL tree?)

---

 AVL트리(AVL tree)는 1962년 아델슨 벨스키(Adelson-Velskii)와 랜디스(Landis)에 의해 제안된 트리로서, 트리 내의 모든 노드에 대해 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이가 1 이상 차이 나지 않는 높이 균형 이진 트리(height balanced binary tree)를 말한다. 아델슨 벨스키와 랜디스의 이름의 앞 글자를 따서 AVL트리라고도 부른다.

 AVL트리의 검색 속도는 O(log n)의 탐색 시간을 가지며, 완전 이진 탐색 트리에 비하면 검색 시간이 더 걸리지만 유의미할 정도의 차이가 나지 않는다. 삽입 삭제 연산에 걸리는 시간 또한 검색 시간에 의해 좌우되기 때문에 삽입 삭제 연산 시간도 O(log n)의 시간 복잡도를 갖는다.

 AVL트리에서 중요한 것은 균형 인수인데 균형 인수는 왼쪽 서브트리의 높이와 오른쪽 서브 트리의 차를 말한다. 균형 인수는 BF(T)로 나타내며 이는 트리 T의 양쪽 서브 트리에 대한 높이의 차이며, BF(T) = h(left tree) - h(right tree)로 나타낼 수 있다. 여기서 h는 트리의 높이를 말한다. 

정의
이진 탐색 트리 내의 임의의 노드 N에 대해서 균형 인수 BF(N)가 -1, 0, 또는 1만의 값을 갖는다면 이 이진 탐색 트리를 AVL트리라 한다.

 

 

AVL 트리의 회전 연산(AVL tree rotation operation)

---

AVL트리에서의 삽입, 삭제 과정은 이진 탐색 트리에서의 삽입, 삭제 과정과 같다. 여기서 추가적으로 AVL트리에서는 삽입, 삭제후 균형 인수에 따라 트리를 재조정하는 과정이 추가된다. AVL트리에서 트리를 재조정하는 경우는 균형 인수의 절댓값이 2를 넘어가는 경우이다. 다시말해서 균형인수가 -2이하이거나 2이상인 경우 트리에 적절한 조절을 통해 균형 인수를 -1이상에서 1이하로 맞추어 준다. 트리의 재조정은 회전 연산을 통해 이루어진다. 다음 그림은 트리의 재조정이 필요한 경우이다.

 

 

회전에 대한 대략적인 내용을 표로 나타내면 다음과 같다.

회전을 하는 노드의 기준은 삽입의 경우는 삽입된 노드를 기준으로 균형인수가 깨진 가장 조상노드이고 삭제의 경우, 삭제하기 전 삭제로 인해 균형인수가 깨지는 가장 가까운 조상 노드이다.

 

LL회전(LL rotation or Single Right Rotation)

LL회전(LL rotation)은 왼쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가되면서 불균형이 발생했을 떄 사용한다. 아래 그림을 보면 왼쪽 A 노드가 삽입되면서 C 노드의 균형인수가 깨졌다. 이를 해결하기위해 LL회전을 하여 다시 균형인수를 맞춘게 된다.

 

RR회전(RR rotation or Single Left Rotation)

RR회전(RR rotation)은 오른쪽 서브 트리의 오른쪽 서브 트리에 노드가 추가되면서 불균형이 발생했을 때 사용한다. 아래 그림을 보면 오른쪽 G 노드가 삽입되면서 D 노드의 균형인수가 깨졌다. 이를 해결하기위해 RR회전을 하여 다시 균형인수를 맞춘게 된다.

LR회전(LR rotation or Double(Left Right) Rotation)

LR회전(LR rotation)은 오른쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가되면서 불균형이 발생했을 때 사용한다. 아래 그림을 보면 L 노드가 삽입되면서 G 노드의 균형인수가 깨졌다. 이를 해결하기위해 LR회전을 하여 다시 균형인수를 맞춘게 된다. LL회전과 RR회전을 순서대로 하면 LR회전이 된다.

RL회전(RL rotation or Double(Right Left) Rotation)

RL회전(RL rotation)은 왼쪽 서브 트리의 오른쪽 서브 트리에 노드가 추가되면서 불균형이 발생했을 때 사용한다. 아래 그림을 보면 B 노드가 삽입되면서 G 노드의 균형인수가 깨졌다. 이를 해결하기위해 RL회전을 하여 다시 균형인수를 맞춘게 된다. RR회전과 LL회전을 순서대로 하면 RL회전이 된다.

 

AVL트리의 구현(AVL tree implementation)

---

AVL트리 같은 경우는 필자가 구현할 때 proqk라는 분의 블로그 글을 참고하였다. 필자의 코드보다 좀더 자세하고 깔끔한 코드를 원한다면 이분의 블로그를 참조하길 바란다.

[자료구조] 자가 균형 이진 탐색 트리: AVL트리 (나이 기준으로 사람 찾는 AVL트리 구현)

 

아래는 필자의 깃허브이다.

GitHub - LimeTree0/Data-Structure