[자료구조] 12. AVL 트리(AVL Tree)

이전 시간에 살펴보았던 이진탐색트리는 O(h)의 시간 복잡도를 가지기에, 높이의 균형을 유지하여야 O(log n)의 효율을 유지할 수 있었다. 이렇게 밸런스를 유지하는 방법으로는 height-balanced와 weight-balanced의 방식이 있는데 그중 height-balanced 트리는 대표적으로 AVL 트리와 레드-블랙 트리가 존재한다. 이번 글에서는 이 중 AVL 트리에 대해서 다루어 보려 한다.

 

AVL 트리

AVL 트리의 정의는 모든 노드 v에 대하여 v 양옆의 자식들의 높이(height) 차이가 1 이하인 이진탐색트리를 의미한다.

AVL트리의 효율 증명

이러한 방식으로 AVL트리를 제작했을 때 이 효율이 O(log n)인 것의 증명을 서술...나중에 한다.

---

ADT

search(key)
insert(key)
delete(key)

이진탐색트리와 같다.

---

구현

힙이 삽입과 삭제 후에 heapify를 하듯이 삽입/삭제 후 규칙에 맞게 restructing 해주는 것이 핵심이다.

삽입

삽입은 삽입 후 AVL 트리에 맞게 restructing 해주는 방식으로 진행된다. 삽입 자체는 이진탐색트리와 동일하게 진행된다.

1. 이진탐색트리 규칙에 맞게 삽입한다.

2. AVL 트리 규칙에 맞는지 확인 후 맞다면 넘어가고, 규칙에서 벗어나면 restructing 해준다.

Trinode Restructing

Restructing의 과정을 설명한다. 노드 삽입시에 AVL 트리 규칙에 벗어나는 경우는 크게 2가지 경우가 있다.

~~~ 작성 중

제거

제거는 삽입과 유사하나 하나의 경우의 수가 더 늘어난다.

~~~ 작성 중

---

효율

작업	시간 복잡도
find()	O(log n)
put()	O(log n)
erase()	O(log n)

AVL트리는 이진탐색트리의 효율을 따라가는데 이진탐색트리는 O(h)의 시간 복잡도를 가진다. 이때 AVL트리는 h = log n 수준으로 맞춰주는 작업을 추가한 특수한 이진탐색트리임으로, O(log n)의 시간 복잡도를 가진다.