AVL 트리

이진 탐색 트리의 탐색 연산은 O(log2n)의 시간 복잡도를 가진다. 이러한 이진 탐색 트리는 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다. 이것이 이진 탐색 트리의 단점이며, 이 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라 불리운다. 

그 종류는 다음과 같이 5가지가 된다.

1.AVL 트리

2.2-3 트리

3.2-3-4 트리

4.Red-Black 트리

5.B트리

AVL트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 멋진 트리다.

AVL트리에서는 균형의 정도를 표현하기 위해서 균형 인수라는 것을 사용하며 이 균형 인수는 다음과 같이 계산된다.

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

AVL 트리는 균형 인수의 절댓값이 2 이상인 경우에 균형을 잡기 위한 트리의 재조정을 진행한다.