Chap 09. AVL(균형 잡힌 이진 트리)

<AVL - 균형 잡힌 이진 탐색 트리>

이진 탐색 트리의 시간 복잡도는 O(log2N)이다.
하지만 균형이 맞지 않다면 O(N)에 가까워진다.

==>> 높이가 중요함. 시간 복잡도는 애초에 높이에 의해 결정되었기 때문이다.

따라서, '균형 잡힌 이진 트리'를 AVL이라고 한다.

* 노드가 추가될 때, 노드가 삭제될 때 스스로 그 구조를 변경하여 균형을 잡는다.

---

 

균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

'균형 인수'의 절댓값이 2 이상 ==>> 균형이 무너졌다.

 

---

'균형 인수'가 무너진 경우

 

LL상태
자식 노드 두 개가 왼쪽으로 연이어 연결되어 '균형 인수'가 2이상이다.

---

RR상태
자식 노드 두 개가 오른쪽으로 연이어 연결되어 '균형 인수'의 절댓값이 2 이상이다.

---

LR상태
자식노드가 왼쪽으로 하나, 그 자식 노드의 오른쪽에 하나 연결되었다.
한번의 회전으로 균형 잡기 불가능

---

RL 상태
자식노드가 오른쪽으로 하나, 그 자식 노드의 왼쪽에 하나 연결되었다.