AVL 트리

AVL 트리의 개요

- AVL 트리는 G . M. Adelson-Velskii와 E.M. Landis에 의해 1960년대에 고안되었다.

- AVL 트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형 상태를 파악해서 스스로 그 

  구조를 변경하여 균형을 잡는 멋진 트리이다.

이진 탐색 트리의 문제점과 AVL 트리

이진 탐색 트리의 탐색 연산은  을 가진다.

하지만 이진 탐색 트리는 균형이 맞지 않을수록 의 시간복잡도를 보인다.

따라서 이진 트리 탐색은 저장 순서에 따라서 탐색의 성능에 큰 차이를 보인다.

그래서 이진 탐색 트리의 단점을 보완한 트리는 밑에 열거한 트리등이 있다.

* AVL 트리

* 2-3 트리

* 2-3-4 트리

* Red-Black 트리

* B트리 

AVL트리와 균형 인수(Balance Factor)

균형인수의 계산

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

리밸런싱이란?

- 균형을 잡기 위한 트리 구조의 재조정

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

- 따라서 AVL 트리는 균형 인수의 절대값이 2 이상인 경우에 균형을 잡기 위한 트리의 재조정

  을 진행한다.

AVL 트리에서의 회전

AVL 회전에서는 4가지의 회전이 있다.

- LL( Left-Left) 회전

- LR( Left-Right) 회전

- RR( Right-Right ) 회전

- RL( Right-Left ) 회전