[자료구조] AVL 트리 개념 및 특성, (9-3-2-4-6-7) 삽입

AVL 트리의 개념과 특성

AVL 트리는 Adelson-Velsky와 Landis가 1962년에 개발한 이진 검색 트리(Binary Search Tree, BST)의 일종으로, 자기 균형을 유지하는 특성을 가지고 있습니다. AVL 트리는 이진 검색 트리에서 발생할 수 있는 불균형을 해결하기 위해 **균형 인수(balance factor)**를 사용합니다.

• 균형 인수(Balance Factor): 특정 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 나타냅니다. AVL 트리는 모든 노드에 대해 균형 인수가 -1, 0, 1인 경우만 허용됩니다.
  • balance factor = height(left subtree) - height(right subtree)
• 특성:
  1. 자기 균형: 트리의 높이가 커지면서 발생할 수 있는 불균형을 해결하기 위해 노드 삽입이나 삭제 후 트리의 균형을 유지하는 회전(rotation) 작업이 수행됩니다.
  2. 높이 제한: AVL 트리의 높이는 O(log n)으로 유지되며, 이진 검색 트리에서 발생할 수 있는 불균형으로 인해 성능 저하를 방지합니다.
  3. 회전: 불균형이 발생하면 트리를 균형 상태로 되돌리기 위해 **단일 회전(single rotation)**과 **이중 회전(double rotation)**을 사용합니다.
     • LL 회전(왼쪽-왼쪽 불균형)
     • RR 회전(오른쪽-오른쪽 불균형)
     • LR 회전(왼쪽-오른쪽 불균형)
     • RL 회전(오른쪽-왼쪽 불균형)

4-2. (9-3-2-4-6-7) 삽입, AVL 트리 그리기

이제 주어진 값들(9, 3, 2, 4, 6, 7)을 AVL 트리에 차례대로 삽입하고 균형을 맞추는 과정을 통해 트리 구조를 그려보겠습니다.

Step 1: 9 삽입

9

Step 2: 3 삽입

9 / 3

Step 3: 2 삽입 (LL 회전 필요)

9 3 / => / \ 3 2 9 / 2

   9          3
   /     =>   / \
  3          2   9
 /
2

Step 4: 4 삽입

3 / \ 2 9 / 4

   3
  / \
 2   9
    /
   4

Step 5: 6 삽입 (RL 회전 필요)

3 3 / \ => / \ 2 9 2 6 / / \ 4 4 9 \ 6

    3             3
   / \     =>    / \
  2   9        2   6
     /              / \
    4              4   9
      \
       6

Step 6: 7 삽입 (RR 회전 필요)

3 3 / \ / \ 2 6 => 2 6 / \ / \ 4 9 4 9 / / 7 7

이 과정을 통해 최종적으로 균형 잡힌 AVL 트리는 다음과 같습니다:

3 / \ 2 6 / \ 4 9 / 7

이 트리는 AVL 트리의 특성을 만족하며, 각 노드의 균형 인수는 -1, 0, 1 범위 내에 있습니다.

    3              3
   / \            / \
  2   6    =>    2   6
     / \            / \
    4   9          4   9
         /              /
        7              7

    3
   / \
  2   6
     / \
    4   9
         /
        7