AVL 트리 (Adelson-Velsky and Landis Tree)

이진 탐색 트리의 단점을 극복할 수 있는 자료구조이다. 이름은 발명자의 이름을 따와서 AVL트리이다.

그냥 이진 탐색 트리는 노드가 한쪽으로 치우치는 현상이 발생할 수 있다.

(이진 탐색 트리는 현재 노드에서 왼쪽 자식이 자신보다 낮은 값, 큰값이 오른쪽 자식으로 가지는 특성을 가지기 때문이다.)

이렇게 되면 특정 값을 찾기 위해 트리 전체를 탐색해야 하는 경우가 생길 수 있는데, 이렇게 되면 이진 탐색 트리의 장점을 활용하지 못한다.

그러한 단점을 해결하기 위해 나온 트리 자료구조이다.

AVL 트리는 다음과 같이 설명할 수 있다.

스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어느 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다.

• 특징
  1. 이진 트리의 속성을 가진다.
  2. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
  3. 어떤 시점에서 높이 차이가 1보다 커지면 회전연산을 통하여 균형을 잡아 차이를 줄인다.
  4. AVL 트리는 높이를 $logN$으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 $O(logN)$이다.

트리 불균형 문제.

이는 4 가지로 나뉜다.

• LL problem : Left - Left로 서브 트리가 비대해지는것.
• LR problem : Left - Right로 서브 트리가 비대해지는것.
• RR problem : Right - Right로 서브 트리가 비대해지는것.
• RL problem : Right - Lefe로 서브 트리가 비대해지는것.

🌲 LL 문제.

🌲 RR 문제.