1. 개요

• BST는 탐색의 효율을 담보하기 위한 자료구조이지만, tree의 현재 형태에 따라 탐색 효율이 다르다. 평균적으로, 이론적으로는 O(log n)이지만, 형태가 좋지 못한 경우 O(n)으로 크게 효율이 감소한다.

• AVL은 height와 balance factor개념을 도입하여, tree의 형태를 최대한 탐색 효율을 담보할 수 있도록 유지하는 특수한 BST이다.

2. Rotation

• Leaf node의 height를 0, null node의 height를 -1로 한 상태에서, node의 height와 balance factor계산은 다음과 같다.

  	1. Height = max(left child's height, right child's height) + 1
  	2. Balance factor = left child's height - right child's height

• 이때, balance factor의 절대값이 1을 초과한다면, unbalanced한 상태로 보고 이를 조정해주어야 한다. 조정 동작을 rotation이라 하는데, 경우에 따라 2회 연속 해야할 수도 있다. Pseudo code와 경우의 수는 다음과 같다.

A - B - C - 4 
|   |	|
1   2	3

이상의 Tree의 경우

leftRotation(Node A):
	Node B = A's right child
    A's right child = B's left child
    B's left child = A
    Update height & BF of A
    Update height & BF of B
    return B
    
결과

B - C - 4
|	|
A-2	3
|
1

한편
C - 4
|
B - 3
|
A - 2
|
1

이상의 tree의 경우

rightRotation(Node C):
	Node B = C's left child
    C's left child = B's right child
    B's right child = C
    Update height & BF of C
    Update height & BF of B
    return B
    
결과

B - C - 4
|	|
A-2 3
|
1

Parent BF	Heavier child	Child BF	Rotation type
2	Left	0, 1	Right
2	Left	-1	Left-Right
-2	Right	-1, 0	Left
-2	Right	1	Right-Left

• AVL tree가 tree의 형태를 최대한 유지함을 통해 탐색의 시간 효율성을 담보하는 것은 맞지만, 그 과정에서 tree의 형태를 유지하기 위한 동작의 시간이 추가된다는 사실을 간과해서는 안된다. 예를들어, tree의 모든 node를 remove하는 동작은 binary tree에서는 O(n)이 들겠으나, AVL은 O(n)은 물론 매번 tree를 검사하고 재조정하는 시간이 추가되기때문에, 상황에 따라 시간이 더 오래걸리는 결과를 초래한다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xII+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.