7. AVL Tree

AVL Tree란?

BST(Binary Search Tree, 이진 탐색 트리)는 검색, 삽입, 삭제에 모두 O(h)의 시간이 소요된다.

6. Binary Search Tree

BST의 높이는 데이터의 삽입 순서에 따라 매우 높아질 수 있고 이는 BST의 효율을 낮추는 원인이 된다.

 

이 때문에 BST를 사용하면서 높이를 최소화하는 방법이 고안되게 되었다.

높이를 최소화하기 위해서는 트리의 left와 right에 골고루 데이터가 삽입되어야 한다.

데이터가 골고루 분포할수록 포화 이진 트리에 가까워지며, 높이는 logn에 가까워진다.

즉, 균형 잡힌(balanced) 트리일 수록 BST의 효율이 올라간다는 것이다.

 

이렇게 삽입, 삭제 시에 균형을 유지하도록 만들어낸 balanced BST가 AVL Tree이다.

 

AVL Tree에서는 노드의 left sub-tree의 높이에서 right sub-tree의 높이를 뺀 값을 Balance Factor(BF)라 한다.

그리고 이 BF 값이 항상 1보다 크지 않고, -1보다 작지 않도록 유지한다.

즉, 모든 internal 노드의 left sub-tree와 right sub-tree의 높이 차이가 최대 1을 넘지 않는다.

 

그렇다면 어떤 삽입, 삭제 과정을 통해 균형을 유지하는지 알아보자.

 

 

Rotation

AVL Tree에서는 데이터를 삽입, 삭제하는 과정에서 노드를 이동시키는 rotation을 통해 균형을 유지한다.

rotation은 노드를 이동시키는 방향에 따라 left rotation, right rotation으로 나뉜다.

 

left rotation

왼쪽 tree에서 노드 a에 left rotation을 수행하면, 오른쪽 처럼 노드 b가 올라오고 a가 b의 left child가 된다.

이 때 노드 b의 left child 자리에 노드 a가 와야 하기 때문에 기존 b의 left sub-tree는 a의 right sub-tree가 된다.

 

right rotation

right rotation은 left rotation과 반대로 a의 left child인 노드 b가 parent 노드가 되고, a는 b의 right child 노드가 된다.

또한 마찬가지로 b의 right sub-tree는 a의 left sub-tree가 된다.

 

 

Insertion & Deletion

기본적으로 삽입과 삭제 과정은 BST와 동일하다.

하지만 삽입과 삭제 후 트리의 균형이 깨질 경우 rotation을 통해 균형을 맞추는 restructing 작업이 추가된다.

 

restructing 작업은 다음과 같이 진행된다.

 

먼저 노드가 삭제, 삽입됨으로써 균형이 깨졌을 때, leaf 노드부터 올라가면서 처음으로 균형이 깨진 노드를 찾는다.

이렇게 처음으로 균형이 깨진 노드를 z, z의 child 중 높이가 높은 노드를 y, y의 child 중 높이가 높은 노드를 x라 하자.

 

이 때, y가 z의 left child인지 right child인지에 따라, x가 y의 left child인지 right child인지에 따라 경우를 나누어보자.

그러면 left-left, left-right, right-right, right-left 총 4가지 경우로 나눌 수 있다.

 

이제 각각의 경우에 어떻게 rotation을 통해 무너진 balance를 복원하는지 알아보자.

 

left-left case

left-left case는 z 노드를 right rotation 해주면 트리의 균형을 맞출 수 있다.

 

left-right case

left-right case는 먼저 y 노드를 left rotation 하여 left-left case로 만들어준다.

그 다음 left-left case처럼 z 노드를 right rotation 해주면 된다.

 

이제 나머지 두 경우는 위 두 경우를 대칭하여 수행하면 된다.

 

right-right case

right-right case는 z 노드를 left rotation 하면 된다.

 

right-left case

right-left case는 y 노드를 right rotation 하여 right-right case로 만들어준 뒤,

이제 right-right case처럼 z 노드를 left rotation 해주면 된다.

 

 

Summary

삽입과 삭제를 통해 균형이 깨진 경우 다음과 같이 rotation을 수행한다.

 

left-left case - right rotate z

left-right case - left rotate y, right rotate z

right-right case - left rotate z

right-left case - right rotate y, left rotate z

 

또한 삽입, 삭제의 시간복잡도는 BST의 삽입, 삭제 시간복잡도 O(h) + restruct 시간복잡도 O(1) = O(h) 이다.