[알고리즘] AVL 트리란? AVL 트리 개념 요약

🎄 AVL 트리란?

• Adelson-Velskii and Landis의 약어
• 균형 잡힌 높이를 갖는 이진 탐색 트리
  다음과 같은 한 쪽으로 치우쳐진 이진 트리를 방지하기 위해 사용한다!
  

---

🎄 Balance Factor

• Balance factor란 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다.
  BF는 -1, 0, 1 중에 값을 갖고, 이 값을 벗어나면 Rotation을 통해 균형을 잡는다.

BF = 1, 왼쪽 서브트리가 오른쪽 서브트리보다 한 단계 높음.
BF = 0, 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같음.
BF = -1, 왼쪽 서브트리가 오른쪽 서브트리보다 한 단계 낮음.

---

🎄 AVL 트리의 연산

 

 

그림처럼 4가지 경우가 있다!

• Outside Cases(single rotation) - 한 번의 Rotation만 필요한 경우
  1. left-left
  2. right-right
• Inside Cases(double rotation) - 두 번의 Rotation이 필요한 경우
  1. left-right
  2. right-left

---

1. Left-Left Case

y가 z의 왼쪽 자식 노드이고, x가 y의 왼쪽 자식 노드인 경우

2. Right-Right Case

y가 z의 오른쪽 자식 노드이고, x가 y의 오른쪽 자식 노드인 경우

3. Left-Right Case

y가 z의 왼쪽 자식 노드이고, x가 y의 오른쪽 자식 노드인 경우

4. Right-Left Case

y가 z의 오른쪽 자식 노드이고, x가 y의 왼쪽 자식 노드인 경우

---

🎄 AVL트리의 장점과 단점

장점

• 삽입, 검색, 삭제 속도 = O(log n)
• 높이 균형 조절 할 때에도 삽입 속도에 상수항만 추가됨. O(1)

단점

• 프로그래밍과 디버깅에 어려움이 있음.
• O(n)의 추가 공간을 필요로 함.