[자료구조] AVL 트리 특징 및 로테이션 기준

AVL 트리 특징 및 로테이션 기준

AVL 트리는 이진탐색트리(Binary Search Tree, BST)의 한 종류입니다.

이진 탐색 트리(BST)는 이진트리(Binary Tree)의 한 종류이죠.

따라서 AVL 트리는 이진트리와 이진탐색트리의 특징들을 모두 갖고 있습니다.

그렇다면 그 특징들이 무엇일까요?

 

- 이진트리(Binary Tree)의 특징

a. 각 노드는 최대 2개의 자식 노드를 가질 수 있다.

b. 자식 노드는 보통 왼쪽과 오른쪽으로 구분한다 -> left child, right child

c. 각 노드는 데이터를 가지고 있다. (데이터를 저장하기 위한 자료구조 중 하나이니 당연한 말이다)

 

- 이진탐색트리(Binary Search Tree, BST)의 특징

a. 이진트리이므로 이진트리의 특성을 기본적으로 갖고 있다.

b. 각 노드의 값은 왼쪽 서브트리에 존재하는 모든 값들 보다 크고 오른쪽 서브트리에 존재하는 모든 값들 보다 작다.

c. 따라서 이진탐색트리는 정렬된 이진트리(sorted binary tree)라고도 한다. 

 

자, 그리고 여기에 추가로 아래와 같은 특징을 갖는 트리를 AVL 트리라고 부릅니다.

- AVL 트리의 특징

a. 어떤 노드라도 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크지 않다. (최대 높이 차이는 1 이다.)

=> Binary Tree이면서 최대 높이 차이가 1이라는 말은 height = O(log N) 이라는 것과 같다.

b. 만약 특정 노드를 추가하거나 삭제했을 때 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 커지는 노드가 생긴다면, re-balancing을 통해 a 규칙에 어긋나지 않도록 한다.

=> 이 말은 AVL 트리는 자가 균형 이진 탐색 트리(self-balancing BST) 라는 말과 같다.

c. 균형 트리(balanced tree)이다. (좀더 정확히는 높이 균형 트리이다.)

=> 균형 트리는 아래 세 가지 조건을 모두 만족하는 트리이다.

   i. 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이다.

  ii. 왼쪽 서브트리가 균형 트리이다.

 iii. 오른쪽 서브트리가 균형 트리이다.

d. 각 노드는 균형값(균형인수, balance factor)을 가지고 있으며 이 균형값은 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값이다. 이 값은 항상 {-1, 0, 1 } 셋 중 하나의 값이어야 한다.

e. 균형값(균형인수, balance factor)이 마이너스(-)이면 left-heavy, 플러스(+) 값을 가지면 right-heavy 라고 한다.

f. pivot 노드는 새로운 노드가 추가되었을 때 균형값에 변동이 발생하여 unbalanced 된 노드들 중 신규노드와 가장 가까운 노드를 말한다. 

 

자, 위와 같은 특징을 갖고 있는 AVL 트리에 노드를 추가 또는 삭제를 하게되면 스스로 균형을 맞추기 위해 트리의 회전(rotation)을 필요로 할 수도 있습니다. 노드가 추가 또는 삭제 되면서 일부 노드들의 균형값에 변동이 발생하기 때문입니다. 회전을 필요로 하는 경우는 크게 2가지(single rotation과 double rotation) 좀 더 세분화하면 아래와 같이 4가지로 나눌 수 있습니다.

• 왼왼 (Left - Left) : 부모 노드와 pivot 노드의 균형값이 모두 left-heavy인 경우
  => Single Right rotation (오른쪽으로 1회전)
• 오오 (Right - Right) : 부모 노드와 pivot 노드의 균형값이 모두 right-heavy인 경우
  => Single Left rotation (왼쪽으로 1회전)
• 왼오 (Left - Right) : 부모 노드와 pivot 노드의 균형값이 각각 right-heavy, left-heavy, 인 경우
  => Double Left-Right rotation (왼쪽으로 한번, 오른쪽으로 한번 총 두 번의 회전)
• 오왼(Right - Left) : 부모 노드와 pivot 노드의 균형값이 각각 left-heavy, right-heavy인 경우
  => Double Right-Left rotation (오른쪽으로 한번, 왼쪽으로 한번 총 두 번의 회전)

 

각각의 로테이션에 대한 그림은 wiki에 매우 간단하게 나와있어 gif 이미지를 첨부합니다.

AVL 트리의 4가지 로테이션 예제 (출처: https://en.wikipedia.org/wiki/AVL_tree)

로테이션 예제 그림이 너무 간단해서 위 4가지 케이스에 대해 설명이 잘 될지 모르겠습니다.

 

로테이션에 대한 추가 설명은 다음 포스팅을 기다려주세요~

 

추가로 AVL 트리에 새로운 노드를 추가하거나 삭제하는 동작은 최악의 상황에서도 O(log N) 의 시간복잡도를 보이며 검색 또한 O(log N) 으로 빠른 자료구조입니다.