[자료구조] 균형 이진 트리 (AVL)

균형 이진 트리란 모든 노드 간의 높이 차이가 1 이하인 이진 트리를 의미한다. 

 

도입의 필요성

균형 이진 트리의 필요성은 무엇일까? 이진 트리 탐색은 시간 복잡도가 낮다. 그러나 항상 시간 복잡도가 낮을까? 아니다. 만약 부모 노드 값이 말도 안되게 크다면 즉 그림 1과 같은 상황이 되고 그러한 경우 시간 복잡도는 O(log n)에서 O(n)이 된다.

그림 1. 이진 트리가 최악의 시간 복잡도를 가지는 경우

이런 균형이 꺠진 이진 트리를 다시 균형 잡히게 만들기 위해 AVL 기법이 등장하였다.

 

 

균형 이진 트리란

균형 이진 트리란 어떠한 노드를 부모 노드라 간주했을 때 부모 노드 기준으로 왼쪽 노드들과 오른쪽 노드들의 개수의 차이가 1 이하가 된 상태를 말한다. 가령 위의 그림1 에서 10은 균형이 잡힌 상태이다. 왼쪽 노드의 개수: 0, 오른쪽 노드의 개수: 0 이기에 둘을 뺴도 1 이하기 떄문이다. 비슷한 논리로 100 역시 균형이 잡힌 상태이다. 왼쪽 노드의 개수: 1, 오른쪽 노드의 개수: 0 이기에 둘을 뺴도 1이하기 떄문이다. 그러나 1만, 1억 노드는 균형이 깨진 상태이다.

 

 

균형이 꺠진 경우의 일반화

균형이 꺠진 상태인 경우들은 어떤 것들이 있을까. 다음 4가지 경우로 일반화가 가능하다. 

 

구현이 완료됐을떄 작동 과정.

Height = 1
     9J

Height = 2
         9J
     8I

Height = 2
         8I
     7H       9J

Height = 3
                 8I
         7H               9J
     6G

Height = 3
                 8I
         6G               9J
     5F       7H

Height = 3
                 6G
         5F               8I
     4E               7H       9J

Height = 3
                 6G
         4E               8I
     3D       5F       7H       9J

Height = 4
                                 6G
                 4E                               8I
         3D               5F               7H               9J
     2C

Height = 4
                                 6G
                 4E                               8I
         2C               5F               7H               9J
     1B       3D

 트리가 만들어지는 과정에서 균형이 맞춰지는 방식으로 만들어진다. 

 

 

균형이 꺠진 경우 구현

i) 첫번째 경우는 왼쪽으로 균형이 꺠진 경우이다. 이 경우에는 노드 3의 오른쪽 노드를 노드 5가 가르키게 하고 노드 3의 오른쪽 노드가 노드 5를 가르키게 하면 된다.

cf) 기존 노드 3의 오른쪽 노드에는 아무것도 없는데 어떻게 가르킬 수 있나요? nullptr 가르키는 겁니다. 

// LL -> Right Rotation
// Insert 함수에서 구현됨.
if (balance > 1 && Balance(node->left) >= 0)
	return RotateRight(node);

// RotateRight 함수
Node* RotateRight(Node* parent)
{
    Node* child = parent->left;
    parent->left = child->right;
    child->right = parent;
    return child;
}

if문은 1번 경우로 불균형을 이룬다는 조건 식이다. RotateRight는 정말 방금 내가 설명한 코드 그대로이다. 

 

 

ii) 두번쨰 경우에 대한 코드를 작성해보자. 어떻게 하면 되겠는가. 비슷할 것 같지 않은가? 정말 그러하다. 7 노드의 왼쪽 노드를 5 노드가 가르키게 하고 7 노드의 왼쪽 노드가 5 노드를 가르키게 하면 된다.

// RR -> Left Rotation
if (balance < -1 && Balance(node->right) <= 0)
	return RotateLeft(node);
    
Node* RotateLeft(Node* parent)
{
    Node* child = parent->right;
    parent->right = child->left;
    child->left = parent;
    return child;
}

조건 식은 ii) 경우로 불균형을 이룬다는 조건식이다. 이거는 i) 경우의 정반대인 것을 금방 확인 가능하다.

 

 

iii) 세번째 경우에 대한 구현을 해보자. 어떻게 하면 될까? 이번에는 4 노드의 왼쪽 노드를 3노드가 가르키게 하고 4 노드의 왼쪽 노드가 3 노드를 가르키게 한다. (RR) 그러면 순서대로 5 -> 4 -> 3 상태가 된다. 이 경우에서 다시 부모 노드를 5로 간주하고 (LL) 회전을 한다. 그러면 3 <- 4 -> 5가 된다. 즉 시작 노드의 왼쪽 노드를 부모 노드로 간주하고 RR 회전을 하고 시작 노드를 부모 노드로 간주하고 LL 회전을 한다.

// RL -> Right-Left Rotation
if (balance < -1 && Balance(node->right) > 0)
{
    node->right = RotateRight(node->right);
    return RotateLeft(node);

}

따라서 iii) 의 경우는 새로 함수를 만들어줄 필요가 없다 !! 발상은 솔직히 어려운 거 인정한다....

 

 

ix) 네번째 경우는 세번쨰 경우를 반대로 하면 된다. 

// LR -> Left-Right Rotation
if (balance > 1 && Balance(node->left) < 0)
{
    node->left = RotateLeft(node->left);
    return RotateRight(node);
}

 

마치며

이렇게 이진 균형 트리를 만들어보는 시간을 가져보았따.