AVL Tree : Balancing 작업을 통해 최대 Height를 조절하는 BST

AVL Tree

https://casterian.net/archives/217

AVL 트리는 아래의 성질을 만족하는 BST(Binary Search Tree)의 한 종류다

Tree 상의 모든 Node p에 대해 p의 left subtree와 right subtree의 height 차이가 최대 1을 넘을 수 없다

 

이러한 성질을 AVL 트리의 Balanced Property라고 하며, 

일반적인 BST와 비교했을 때, Search 연산은 완전히 동일하지만 Insert/Delete 연산을 할 때 이 성질이 깨지지 않도록 추가적인 연산을 수행한다

 

위의 그림에서 12라는 노드를 추가했을 때, 해당 노드를 자손으로 가지는 노드들(4, 8, 15, 10, 12)의 height가 변한다

그리고 노드 15를 봤을 때 왼쪽 서브트리의 height가 2, 오른쪽 서브트리의 height가 0이므로 balance가 깨진 상태로 변한다

따라서 rotation을 통한 balancing 작업을 수행해야 한다

 

Balancing

이 때, 

w: 새로 추가한 node
z: w의 ancestor 중 balanced property를 만족하지 않으면서 height가 최소인 node
y: z의 두 child 중 height가 큰 child node(heavy child)
x: y의 두 child 중 height가 큰 child node(heavy child)

라고 정의하면 balanced 성질이 깨졌을 경우 아래와 같은 네 가지 형태가 나올 수 있다

Case1 & 2의 경우에는 트리를 한 번 회전시키는 Single Rotation, 3 & 4의 경우에는 트리를 두 번 회전시키는 Double Rotation을 적용하면 Balanced Property를 만족할 수 있다.

(Tree Rotation에 대해서는 아래의 글 참고) https://2jinishappy.tistory.com/341

Binary Tree에서 Height를 조절하기 위한 Tree Rotation

 

 

Case 1 & 2

y를 기준으로 Tree를 회전한다.

Case1

• y의 left subtree T2를 임시로 저장한다
• y의 left child를 z로 연결한다
• z의 right child를 T2로 연결한다

Case 2

Case1과 동일하지만 반대 방향으로 진행하면 된다

• y의 right subtree T3를 임시로 저장한다
• y의 right child를 z로 연결한다
• z의 left child를 T3로 연결한다

 

Case 3 & 4

Case 3

• y를 기준으로 right rotate한다
• case1과 동일한 모양이 되어, case1의 rotate연산을 수행한다

Case 4

case 3과 동일하지만 반대 방향으로 수행한다

• y를 기준으로 left rotate한다
• case2와 동일한 모양이 되어, case2의 rotate연산을 수행한다

 

아래의 링크에서 AVL Tree의 Search/Insert/Delete를 직접 체험해볼 수 있다 😮👏

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL Tree Visualzation