[자료구조] AVL 트리

목차

• AVL 트리의 개념
• Balance Factor
• AVL 트리의 균형 유지
• AVL 트리의 삽입/삭제
• AVL 트리의 시간 복잡도
• AVL 트리의 장단점

 

AVL 트리란 무엇인가?

AVL 트리는 자가 균형을 유지하는 이진 탐색 트리의 한 종류이다.

이진 탐색 트리의 성능이 편향된 트리로 인해 저하될 수 있는 문제를 해결하기 위해 도입되었다.

AVL 트리는 트리의 모든 노드가 균형 상태를 유지하도록 Balance Factor를 사용하여 노드 간 높이 차이를 관리한다.

 

AVL 트리의 구조와 Balance Factor

 

AVL 트리는 각 노드에 대해 Balance Factor(BF)를 정의하여 균형을 유지한다.

이는 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이를 나타내며, 이 값은 -1, 0, 1 중 하나여야 한다.

• Balance Factor 공식: BF(x) = h(lSubtree(x)) - h(rSubtree(x))
• 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1 이하로 유지되도록 트리를 관리한다.

 

 AVL 트리의 균형 유지 방법

출처: https://www.interviewkickstart.com/blogs/learn/data-structures-and-algorithms-avl-trees

 

삽입 또는 삭제 후, 트리의 균형이 깨진 노드의 Balance Factor가 -1, 0, 1 이외의 값이 될 경우, AVL 트리는 균형을 유지하기 위해 회전(Rotation)이라는 과정을 수행한다. 회전은 높이 차이를 줄여 트리를 균형 상태로 복구하는 방식이다.

 

균형을 맞추는 회전 방식

1. 단일 회전(Single Rotation): LL 회전, RR 회전
2. 이중 회전(Double Rotation): LR 회전, RL 회전

 

AVL 트리의 삽입과 삭제

• 삽입: 새로운 노드를 추가한 후, 해당 노드로부터 루트까지 거슬러 올라가면서 Balance Factor를 확인하고, 균형이 깨진 경우 회전을 통해 균형을 맞춘다.
• 삭제: 노드를 삭제한 후에도 마찬가지로 루트까지 거슬러 올라가며 균형을 확인하고 필요한 경우 회전을 수행한다.

 

AVL 트리의 시간 복잡도

• 탐색, 삽입, 삭제: AVL 트리는 높이를 균형 있게 유지하므로 트리의 높이는 O(log n)에 해당하며, 삽입, 삭제, 검색의 시간 복잡도는 O(log n)이다.

 

AVL 트리의 장점

1. 균형 유지: 트리가 스스로 균형을 유지하여 탐색, 삽입, 삭제 연산에서 일관된 성능을 제공한다.
2. 최악의 경우에도 효율적: 편향된 트리가 발생하지 않으므로, 이진 탐색 트리에서 최악의 경우 시간 복잡도가 O(n)이 되는 문제를 방지한다.

 

AVL 트리의 단점

1. 높은 유지 비용: 트리의 균형을 유지하기 위해 삽입이나 삭제 시 매번 Balance Factor를 확인하고 필요한 경우 트리를 회전시켜야 한다. 이로 인해 삽입, 삭제 연산에서 추가적인 연산이 발생하여 유지 비용이 증가한다.

 

AVL 트리 vs 레드-블랙 트리

레드-블랙 트리는 AVL 트리의 유지 비용 문제를 해결하기 위해 개발된 자료구조이다.

레드-블랙 트리는 AVL 트리만큼 엄격하게 균형을 유지하지 않지만, 균형을 적당히 유지하여 삽입/삭제 시 성능을 개선한다.

이로 인해 레드-블랙 트리가 AVL 트리보다 효율적으로 동작하는 경우도 많다.

---