Chapter 12. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

이진 탐색 트리의 탐색 연산은 다음과 같은 시간 복잡도를 가집니다.

위의 빅-오는 자료구조에서 가장 이상적인 형태입니다. 그런데 이런 이진 탐색 트리는 다음과 같이 균형이 맞지 않을수록 다음과 같은 시간 복잡도를 보입니다.

위의 트리는 1부터 8까지의 숫자를 순서대로 입력했을 경우의 이진 탐색 트리입니다. 분명 트리이지만 그 형태는 차라리 연결 리스트와 같습니다. 똑같은 데이터를 입력하지만 5부터 시작해서 순서대로 입력할 경우 트리는 다음과 같은 구조를 가지게 됩니다.

똑같은 데이터를 똑같은 순서로 입력했고, 오로지 첫 시작 데이터만 바뀌었을 뿐입니다. 그런데 이로 인해 만들어지는 트리의 구조는 그전 트리와는 매우 다릅니다. 트리의 레벨이 거의 절반 수준으로 줄었습니다.

 

이렇듯이 이진 탐색 트리는 저장 순서에 따라서 탐색의 성능에 큰 차이를 보입니다. 그리고 이것이 이진 탐색 트리의 단점입니다. 이런 이진 탐색 트리의 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라고 하며, 그 종류는 다음과 같습니다.

• AVL 트리
• 2-3 트리
• 2-3-4 트리
• Red-Black 트리
• B 트리

 

우리는 위의 균형 잡힌 이진 트리 중에서 AVL 트리에 대해 배우게 됩니다.

---

AVL 트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형 상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리입니다. AVL 트리에서는 규형의 정도를 파악하기 위해 '균형 인수'라는 것을 사용합니다. 균형 인수는 다음과 같이 계산됩니다.

이를 그림으로 표현하면 다음과 같습니다.

각 노드의 위에 적힌 숫자는 균형 인수입니다. 이 균형 인수의 절댓값이 크면 클수록 트리의 균형이 무너진 상태를 의미하고, 균형 인수의 부호로 어느 쪽으로 트리가 쏠려있는지를 알 수 있습니다. 균형 인수의 이러한 특징 때문에 균형 인수는 트리 구조를 리밸런싱 하는 기준으로 사용됩니다. 리밸런싱이란, 균형을 잡기 위한 트리 구조의 재조정을 의미합니다. AVL 트리는 균형 인수의 절댓값이 2 이상인 경우에 균형을 잡기 위한 리밸런싱을 진행합니다.

---

AVL 트리의 균형이 무너지는 상태는 4가지로 정리가 됩니다. 그리고 각 상태 별 리밸런싱 방법에도 차이가 있습니다. 그중 첫 번째 상태는 다음과 같습니다.

위 그림을 보면 자식 노드 두 개가 연이어 왼쪽으로 연이어 연결되어서 루트 노드의 균형 인수가 +2가 되었습니다. 이처럼 균형 인수가 +2로 연출된 이런 상태를 가리켜 'Left Left 상태', 줄여서 'LL상태'라고 합니다. 그리고 LL상태에서 발생한 불균형의 해소를 위해 사용하는 리밸런싱 방법을 'LL회전'이라고 합니다. LL회전은 아래의 트리를,

위의 트리를 다음과 같이 재배치합니다.

pNode가 균형 인수 2인 노드를 가리키고, cNode가 그의 자식 노드를 가리킨다고 할 때, 위와 같은 LL회전은 다음과 같은 함수 하나로 구현할 수 있습니다.

void ChangeRightSubTree(cNode, pNode)
{
	cNode->right = pNode;
}

물론 자세하게 말하면 정말로 위 함수 하나만으로 구현할 수 있는 것은 아닙니다. 왜냐하면 pNode가 왼쪽 자식 노드로서 여전히 cNode를 가리키고 있게 될 것이기 때문입니다. 이는 다음과 같은 상황을 예로 구현하면서 해결합니다.

위와 같이 각각의 노드에 서브 트리가 연결되어 있을 경우에는 pNode를 cNode의 오른쪽 자식 노드로 바로 옮길 수 없습니다. 만약 pNode를 cNode의 오른쪽 자식 노드로 옮기게 되면 다음과 같이 서브 트리 T2는 트리에서 완전히 분리되어 접근할 수 없게 되기 때문입니다.

위 트리를 보면 pNode를 cNode의 오른쪽 자식 노드로 연결하기만 했을 뿐이므로 pNode는 여전히 왼쪽 자식 노드로서 cNode를 가리키고 있습니다. 그리고 서브 트리 T2는 전체 트리에서 완전히 분리되었습니다. 따라서 이런 경우에는 pNode가 왼쪽 자식 노드로서 서브 트리 T2를 가리키도록 합니다.

이런 방법이 언뜻 보기에는 아무런 근거 없이 그저 자리가 나니까 이렇게 하는 것으로 보입니다. 그리고 이런 방법이 이진 탐색 트리의 구조를 해치지는 않는지 궁금할 것입니다. 하지만 그런 걱정은 하지 않아도 됩니다. 이런 방법은 이진 탐색 트리의 구조를 절대 해치지 않고, 충분히 논리적인 방법입니다. 어떻게 그렇게 되는 것인지는 스스로 한 번 생각해 보면 재밌습니다.

 

위에서 든 예처럼 LL상태이고, 각 노드가 서브 트리를 가지고 있을 경우에는 cNode의 오른쪽 서브 트리를 pNode의 왼쪽 서브 트리로 옮기고, cNode의 오른쪽 자식 노드로서 pNode를 가리키게 합니다. 이 과정을 다음과 같이 함수로 간단히 표현해 봤습니다.

void LLRotation(BTreeNode* bst)
{
	BTreeNode* pNode = bst;
	BTreeNode* cNode = pNode->left;

	pNode->left = cNode->right;
	cNode->right = pNode;
}

LL회전을 진행하고자 할 때 위와 같이 정의된 LLRotation 함수를 호출하며, 균형 인수가 +2인 노드를 인자로 줍니다. 

---

LL상태와 LL회전이 있으면 RR상태와 RR회전이 있습니다. LL과 RR은 방향만 다를 뿐 핵심은 똑같습니다. 즉, LL상태는 균형 인수가 +2로, 왼쪽으로 노드가 연이어 연결되는 경우를 말한다면, RR 상태는 오른쪽으로 노드가 연이어 연결되어 균형 인수가 -2가 되는 경우를 말합니다. 그리고 LL상태에서 리밸런싱을 하기 위한 방법을 LL회전이라고 한다면, RR상태에서 리밸런싱을 하기 위한 방법을 RR회전이라고 합니다.

 

따라서 RR상태와 RR회전은 자세한 설명 없이도 충분한 이해가 될 것으로 생각됩니다. RR회전을 구현한 함수만 간단히 소개하고 넘어가겠습니다.

void RRRotation(BTreeNode* bst)
{
	BTreeNode* pNode = bst;
	BTreeNode* cNode = pNode->right;

	pNode->right = cNode->left;
	cNode->left = pNode;
}

---

이번에는 AVL 트리의 4가지 불균형 상태 중 세 번째인 LR상태와 LR회전에 대해 설명합니다. 우선 LR상태란 다음과 같은 상태를 의미합니다.

균형 인수가 +2인 노드를 기준으로 왼쪽 자식 노드가 연결되어 있고, 그 자식 노드의 오른쪽 자식 노드가 또 연결되어 있습니다. 언뜻 보아도 위의 경우는 앞서 설명했던 LL상태나 RR상태에 비해 리밸런싱 방법이 까다로울 것 같다는 느낌이 듭니다. 물론 그렇긴 하지만, 의외로 쉽게 리밸런싱이 가능합니다.

 

LR상태는 RR회전을 한 번 수행하여 LL상태로 바꿀 수 있습니다. 어떻게 이것이 가능한지 RR회전의 부가적인 능력(?)에 대해 먼저 설명해 보겠습니다. 다음과 같은 상태가 RR 상태라는 것은 쉽게 알 수 있습니다.

만약 위 트리에서 노드 5가 NULL이라면?

위의 상태는 RR상태는 아니지만 RR회전을 적용할 수는 있습니다. 그리고 위의 트리에 RR회전을 수행하면 다음과 같이 됩니다.

즉, 다음의 트리가

다음의 트리로 바뀐 것입니다.

보면 부모와 자식의 위치가 서로 바뀌었습니다. 그리고 이진 탐색 트리의 구조를 여전히 유지하고 있습니다. 이것이 RR회전의 부가적인 능력(?)입니다. 다시 본론으로 돌아와서,

위의 LR상태의 트리에, 노드 1을 기준으로 RR회전을 수행하면 다음과 같이 됩니다.

물론 노드 5는 여전히 노드 1을 가리키고 있을 것입니다. 이에 노드 5가 노드 3을 가리키게 하면 다음과 같이 LL상태가 됩니다.

이제 LR상태가 LL상태로 바뀌었으므로 여기서는 LL회전을 수행하여 리밸런싱을 할 수 있습니다.

 

LR회전을 구현하는 함수를 간단하게 정의해 보겠습니다.

void LRRotation(BTreeNode* bst)
{
	BTreeNode* pNode = bst;
	BTreeNode* cNode = pNode->left;

	pNode->left = RRRotation(cNode);

	LLRotation(pNode);
}

위 함수를 보면 RR회전을 수행하는 함수 RRRotation과 LL회전을 수행하는 함수 LLRotation이 사용되었습니다. 앞서 정의했던 두 함수에는 반환형이 void입니다. 그런데 위 함수에서는 RRRotation 함수가 반환하는 것을 pNode의 왼쪽 자식으로 연결했습니다. 이에 RRRotation 함수와 LLRotation 함수를 다음과 같이 수정합니다.

BTreeNode* RRRotation(BTreeNode* bst)
{
	BTreeNode* pNode = bst;
	BTreeNode* cNode = pNode->right;

	pNode->right = cNode->left;
	cNode->left = pNode;
    
    return cNode;
}

BTreeNode* LLRotation(BTreeNode* bst)
{
	BTreeNode* pNode = bst;
	BTreeNode* cNode = pNode->left;

	pNode->left = cNode->right;
	cNode->right = pNode;
    
    return cNode;
}

LL회전이나 RR회전을 수행하면 pNode와 cNode의 위치가 바뀝니다. 따라서 회전 후에는 cNode를 반환하도록 했습니다. LRrotation 함수에서는 이 반환 값을 pNode가 왼쪽 자식 노드로서 가리키도록 합니다. 그리고 LL회전을 수행합니다.

---

AVL 트리의 마지막 불균형 상태는 RL상태입니다. 그리고 이를 리밸런싱 하는 방법을 RL회전이라고 합니다. 이 역시 LR상태 및 LR회전과 방향만 반대일 뿐 같은 개념을 가지고 있으므로 자세한 설명은 하지 않고 이를 구현한 함수만 간단하게 정의해 보고 넘어가겠습니다.

void RLRotation(BTreeNode* bst)
{
	BTreeNode* pNode = bst;
	BTreeNode* cNode = pNode->right;

	pNode->right = LLRotation(cNode);

	RRRotation(pNode);
}