[ch 12] AVL 트리

[주제]

- 균형 잡힌 이진 탐색 트리인 AVL 트리의 개념

[정의]

- 이진 탐색 트리는 '저장 순서에 따라 탐색의 성능 차이가 커지는 단점'이 존재

- 위 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라고 함

- 종류(AVL 트리, 2-3 트리, 2-3-4 트리, Red-Black 트리, B 트리)

- 'G. M. Adelson-Velskii와 E. M. Landis'에 의해 고안되었으며, 이름의 앞글자를 따서 AVL 트리라고 함

■ 그림(균형 잡힌 이진 탐색 트리 예시)

■ 그림(균형 인수)

- 균형 인수: 균형의 정도를 표현하는 단위

- 균형 인수의 절대값이 크면 클수록 그만큼 트리의 균형이 무너진 상태

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

- AVL 트리는 균형 인수의 절대값이 '+2(-2)' 이상인 경우에 위치 재조정을 진행

■ 그림(균형 잡는 과정)

- LL 상태: 균형 인수 '+2'가 존재하는 상태

- LL 회전: 'LL 상태'의 데이터를 균형 잡기 위해 회전하는 방법

- RR 상태: 균형 인수 '-2'가 존재하는 상태

- RR 회전: 'RR 상태'의 데이터를 균형 잡기 위해 회전하는 방법

※ LL(Left Left), RR(Right Right)

- 'T3'의 부모 노드인 '4'는 LL 회전으로 인해 루트 노드가 되어야 하기 때문에 위치를 이동시킬 필요가 있음

- 'T3'는 '4 보다 크고 5보다 작은 값'이기 때문에 LL 회전을 통해 '5'의 왼쪽 자식 노드로 붙을 수 있음

※ T1~4: 모든 노드가 서브 트리가 있는 상태를 가정하기 위한 가상의 데이터. 'NULL'값으로 봐도 됨

- 반대의 상황도 동일

- 노드가 'LR 상태'로 있을 경우 우선 'RR 회전'을 진행하여 'LL 상태'로 변환(값의 위치도 변경)

- LL 상태가 되면 LL 회전을 진행하여 균형을 맞춤

※ LR(Left Right), RL(Right Left)

- 반대의 상황도 동일