[Data Structure] AVL Tree

AVL Tree

• 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조
• 이진 탐색 트리가 평균 저장, 삭제, 탐색 시간 복잡도가 평균 O(logN)을 갖지만, 한 쪽으로 편향될 경우(최악의 경우)  시간 복잡도가 O(N)이 될 수 있다.
  이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 AVL 트리가 고안됨.
• 특징
  • AVL 트리는 이진 탐색 트리의 속성을 가진다.
  • 왼쪽, 오른쪽 서브 트리의 높이 차이(Banlance Factor)가 최대 1이다.
  • Balance Factor가 1보다 커지면 회전(rotation)을 통해 균형을 잡는다.
  • AVL 트리의 높이(h)는 logN을 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다.

출처: https://yoongrammer.tistory.com/72

회전(Rotation)

삽입, 삭제 시 노드의 배열에 따라 4가지(LL, LR, RR, RL) 불균형이 발생할 수 있으며, 각 상황마다 rotation을 달리하여 트리의 균형을 맞춘다.

 

LL(Left Left) case

• x < y < z
• y노드의 오른쪽 자식 노드를 z노드로 변경한다.
• z노드 왼쪽 자식 노드를 y노드 오른쪽 서브트리(T2)로 변경한다.
• y는 새로운 루트 노드가 된다.

출처: https://yoongrammer.tistory.com/72

RR(Right Right) case

• x > y > z
• y노드의 왼쪽 자식 노드를 z노드로 변경한다.
• z노드 오른쪽 자식 노드를 y노드 왼쪽 서브트리(T2)로 변경한다.
• y는 새로운 루트 노드가 된다.

출처: https://yoongrammer.tistory.com/72

LR(Left Right) case

• z > x > y
• y 기준으로 RR rotation(left rotation)하고 z 기준으로 LL rotation(right rotation)을 한다.

출처: https://yoongrammer.tistory.com/72

RL(Right Left) case

• y > x > z
• y 기준으로 LL rotation(right rotation)하고 z 기준으로 RR rotation(left rotation)을 한다.

출처: https://yoongrammer.tistory.com/72

---

Reference

https://yoongrammer.tistory.com/72