AVL 트리 (AVL tree)

이진 트리의 문제점

이진 트리의 문제점은 한쪽으로 치우친 형태로 트리 구조가 만들어질 수 있다는 것이다. 이렇게 되면 트리 구조가 아니라 일반적인 연결 리스트와 별 차이가 없는 구조가 되어 이진 트리의 장점을 전혀 발휘할 수 없게 된다.

 

최악의 경우에 해당하는 쏠린 트리

위와 같이 이진 트리가 구성되면 실제 이진 트리의 장점인 노드 검색 시 성능이 O(logN)이 된다는 것을 보장할 수 없다. 만약 위 그림처럼 트리가 구성되어 있다면 14를 찾기 위해서는 트리의 맨 밑까지 내려가야 한다. 즉, 9번의 노드 검사가 필요하게 된다. 이처럼 위 트리 구조는 최악의 경우에 성능이 O(N)이다.

 

이러한 문제를 해결하기 위한 방법 중 하나인 AVL 트리에 대해서 본격적으로 알아보도록 하자.

 

AVL 트리

AVL 트리는 전체 트리의 구조가 균형이 맞도록 하는 트리이다. 즉, 트리 구조가 한쪽으로 쏠리는 것을 막자는 것이 가장 기본적인 개념이다. 1962년 G.M Adelson-Velski와 E.M Landi 두 사람이 발표한 논문에서 유래되었고 발표한 사람의 이름 첫 글자를 모아 AVL 트리라고 이름 지어졌다.

 

AVL 트리는 다음과 같은 특징이 있다.

 

1. 균형도(Balance Factor)라는 개념이 있다.

2. 리프 노드의 균형도는 0이다.

3. 균형도는 '왼쪽 자식 트리의 높이 - 오른쪽 자식 트리의 높이'로 계산한다.

4. 왼쪽 자식 노드와 오른쪽 자식 노드의 균형도는 -1, 0, 1의 세 가지 값만 갖는다.

균형도는 무엇일까? 이는 각 노드의 왼쪽 노드와 오른쪽 노드의 차이를 말하는 것이다.

 

다음 트리가 있을때 노드 0은 리프 노드로 균형도는 0이다. 노드 2는 왼쪽에 자식 노드가 없고 오른쪽에 높이 1의 자식 노드가 있으므로 균형도는 -1이다. 부모 노드는 왼쪽에 자식 노드가 없고 오른쪽에 높이 2의 자식 노드가 있으므로 0 - 2 = -2 의 균형도를 가진다. 따라서 AVL 트리 구조가 되려면 균형도를 맞춰야 하는 대상이 된다.

다음과 같이 변경하여 AVL 트리의 구조를 만족하게 되었다. 각 노드의 균형을 -1, 0, 1로 맞추면 어떤 장점이 있을까? 트리 노드들이 더욱 균등하게 분포되어 이진 트리의 성능인 O(logN)을 만족시킬 수 있다는 장점이 있다.

 

이처럼 AVL 트리는 균형도라는 개념을 사용하여 트리의 노드 각각이 최대한 균형감 있게 분포되도록 만드는 트리다. 

 

AVL 트리의 구성 및 구현

앞에서 AVL 트리가 무엇이고 어떤 특징을 가지는지 대략적으로 살펴보았다. 이제는 구체적으로 어떤 상황에서 어떻게 균형을 맞추게 되는지 알아보고 구현까지 해보겠다.

 

우선 회전하게 되는 경우에 대해서 먼저 정의를 해보자. 총 4가지 타입으로 나눌 수 있다. 새로 삽임된 노드 N으로부터 가장 가까우면서 균형 인수가 +-2가 된 조상 노드를 A라고 하자. 

 

• LL 타입 : N이 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입된다. (Left Left)

• LR 타입 : N이 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. (Left Right)

• RR 타입 : N이 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. (Right Right)

• RL 타입 : N이 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 삽입된다. (Right Left)

LL과 RR은 대칭이고 역시 LR과 RL도 대칭이다. 이제 각 타입별로 알맞게 트리의 균형을 맞추자. 다음은 각각의 경우 대하여 균형 트리로 다시 만드는 방법이다.

 

• LL 회전 : A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다.

• LR 회전 : A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전시킨다.

• RR 회전 : A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다.

• RL 회전 : A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시킨다.

한번만 회전시키는 것을 단순 회전(Single rotation)이라고 하는데 LL 회전, RR 회전이 여기에 속한다. 이 경우, 탐색 순서를 유지하면서 부모와 자식의 위치를 교환하면 된다. 두 번의 회전이 필요한 것은 이중 회전(Double rotation)이라고 하며 LR회전, RL 회전이 여기에 속한다.

 

LL 회전

LL 회전

위 그림의 왼쪽 트리는 LL 타입의 경우로, 노드 6은 균형 인수가 2로서 불균형하다. 오른쪽으로 "회전"을 시키면(6과 5를 바꾸면) 다시 균형 트리를 만들 수 있다. "회전"은 루트와 자식 노드를 바꾸는 것을 의미한다.

 

보다 일반적인 경우를 생각해 보자. 일반적인 LL 타입은 조상 노드의 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가됨으로 해서 발생한다. 다음 그림처럼 LL 회전은 노드들을 오른쪽으로 회전시키면 된다.

 

이 연산을 코드로 구현하면 다음과 같다.

NODE* AVL_Tree::Rotate_LL(NODE* A)
{
	NODE* B = A->left;
	A->left = B->right;
	B->right = A;
	return B;
}

 

RR 회전

왼쪽 회전의 경우 트리를 왼쪽으로 한번 회전하면 균형을 맞추게 된다.

 

RR 타입은 조상 노드 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 노드가 추가됨으로 해서 발생한다. 일반적인 경우의 RR 타입은 다음 그림처럼 노드 A와 B의 위치를 바꾸어 주고 서브 트리들을 정리하면 균형 트리가 된다.

 

코드로 표현하면 다음과 같다.

NODE* AVL_Tree::Rotate_RR(NODE* A)
{
	NODE* B = A->right;
	A->right = B->left;
	B->left = A;
	return B;
}

 

RL 회전

RL 타입은 그림처럼 조상 노드 A의 오른쪽 자식의 왼쪽 서브 트리에 노드가 추가됨으로 인해 발생한다. RL 회전은 균형 트리를 만들기 위해 2번의 회전이 필요하다. RL 회전은 LL 회전을 한 후, RR 회전을 하면 된다.

 

다음은 RL 회전 함수이다. 앞에서 구현한 단순 회전 함수를 호출하여 사용한다.

NODE* AVL_Tree::Rotate_RL(NODE* A)
{
	NODE* B = A->right;
	A->right = Rotate_LL(B);
	return Rotate_RR(A);
}

 

LR 회전

LR 타입은 그림과 같이 A의 왼쪽 자식의 오른쪽 서브 트리에 노드가 추가됨으로 해서 발생한다. LR 회전은 균형 트리를 만들기 위하여 2번의 회전이 필요하다. LR 회전은 RR 회전을 한 다음, LL회전을 하면 된다. 

 

다음은 LR 회전 함수이다. 

NODE* AVL_Tree::Rotate_LR(NODE* A)
{
	NODE* B = A->left;
	A->left = Rotate_RR(B);
	return Rotate_LL(A);
}

AVL 트리의 원리를 살펴보았으니 이제 구현을 할 차례이다.

 

우선 전체적인 트리 프레임은 이전에 봤던 이진탐색트리를 기반으로 한다.

https://lipcoder.tistory.com/71

이진탐색트리

AVL_Tree 클래스

// AVL_Tree.h

#pragma once
class AVL_Tree
{
public:
	AVL_Tree();
	~AVL_Tree();
public:
	bool IsEmpty() { return (nullptr == m_Root); }
	NODE* GetRoot() { return m_Root; }
public:
	int CalcHeight(NODE* root);
	int Diff(NODE* root);
public:
	NODE* Search(NODE* n, int key);
	void Search_AVL(int key);
	bool Insert(NODE* r, NODE* n);
	void Insert_AVL(int key);
	NODE* Banlance(NODE* n);

public:
	NODE* Rotate_LL(NODE* A);
	NODE* Rotate_RR(NODE* A);
	NODE* Rotate_RL(NODE* A);
	NODE* Rotate_LR(NODE* A);

private:
	void ClearAll(NODE* root);
private:
	NODE* m_Root = nullptr;
	int m_searchCount = 0;
};

 AVL 트리의 원리에 맞게 트리가 제대로 균형을 맞추는지만 확인하면 되기 때문에 이진 탐색 트리에서 그것을 위한 함수들만 남겨놓았고, 앞에서 봤던 회전 함수들과 2개의 함수가 추가되었는데 다음과 같다. 

 

• Diff() : 루트 노드에서의 균형도를 측정해주는 함수이다.

• Balance() : 노드의 균형을 맞춰주는 함수이다.

그리고 균형이 맞는지 확인하기 위해 탐색시 몇 번 안에 찾는지에 대해 기록하는 멤버 변수 하나를 (m_searchCount) 추가하였다.

// AVL_Tree.cpp

#include "pch.h"
#include "AVL_Tree.h"

AVL_Tree::AVL_Tree()
{
}

AVL_Tree::~AVL_Tree()
{
	ClearAll(m_Root);
}

int AVL_Tree::CalcHeight(NODE* root)
{
	// 높이 구하기
	if (nullptr == root)
		return 0;
	return 1 + max(CalcHeight(root->left), CalcHeight(root->right));
}

int AVL_Tree::Diff(NODE* root)
{
	int left = CalcHeight(root->left);
	int right = CalcHeight(root->right);
	return left - right;
}

NODE* AVL_Tree::Search(NODE* n, int key)
{
	++m_searchCount;
	if (nullptr == n)                   // 노드에 동일한 키가 없으므로 탐색에 실패
		return nullptr;
	else if (n->data == key)            // 노드에 키와 동일하다면 값을 찾은것
		return n;
	else if (n->data > key)
		return Search(n->left, key);    // 키가 노드보다 작은경우 왼쪽서브트리에서 찾는다.
	else
		return Search(n->right, key);    // 키가 노드보다 큰경우 오른쪽서브트리에서 찾는다.
}

void AVL_Tree::Search_AVL(int key)
{
	NODE* n = Search(m_Root, key);
	if (nullptr != n)
		cout << "[탐색 연산] : 성공, 찾은 횟수 : " << m_searchCount
		<< " [" << n->data << "] = " << std::hex << n << endl;
	else
		cout << "[탐색 연산] : 실패, No " << key << endl;

	cout << std::dec;
	m_searchCount = 0;
}

bool AVL_Tree::Insert(NODE*& r, NODE* n)
{
	// 밸런스 조정 후의 노드위치(주소)를 m_Root에 덮어써야 하기 때문에
	// 레퍼런스 포인터형을 매개변수로 받는다.

	if (n->data == r->data)
		return false;               // 이미 동일한 키가 존재하므로 삽입불가능(탐색 성공)
	else if (n->data < r->data)
	{
		if (nullptr == r->left)
			r->left = n;            // 탐색에 실패한 위치에 새로운 노드 삽입
		else
		{
			Insert(r->left, n);     // 아직 찾아야 할 서브트리가 남아있음
			r = Banlance(r);        // 노드추가가 된 상태라면 트리의 밸런스를 맞춘다.
			                        // 그리고 밸런스를 맞춘 후 루트노드 위치를 재조정한다.
		}
	}
	else
	{
		if (nullptr == r->right)
			r->right = n;           // 탐색에 실패한 위치에 새로운 노드 삽입
		else
		{
			Insert(r->right, n);    // 아직 찾아야 할 서브트리가 남아있음
			r = Banlance(r);        // 노드추가가 된 상태라면 트리의 밸런스를 맞춘다.
			                        // 그리고 밸런스를 맞춘 후 루트노드 위치를 재조정한다.
		}
	}
	return true;
}

void AVL_Tree::Insert_AVL(int key)
{
	NODE* n = new NODE;
	n->data = key;
	n->left = nullptr; n->right = nullptr;

	if (IsEmpty())
		m_Root = n;
	else if (!Insert(m_Root, n))
		SAFE_DELETE(n);
}

NODE* AVL_Tree::Banlance(NODE* n)
{
	int factor = Diff(n);

	// 왼쪽 서브트리쪽으로 삽입되어 균형이 깨진 경우
	if (1 < factor)
	{
		// 왼쪽 서브트리의 왼쪽 자식노드 쪽에 불균형이 생겼으므로
		// LL 회전을 한다.
		if (0 < Diff(n->left))
			n = Rotate_LL(n);
		// 왼쪽 서브트리의 오른쪽 자식노드 쪽에 불균형이 생겼으므로
		// LR 회전을 한다.
		else
			n = Rotate_LR(n);
	}
	// 오른쪽 서브트리쪽으로 삽입되어 균형이 깨진 경우
	else if (-1 > factor)
	{
		// 오른쪽 서브트리의 왼쪽 자식노드 쪽에 불균형이 생겼으므로
		// RL 회전을 한다.
		if (0 < Diff(n->right) )
			n = Rotate_RL(n);
		// 오른쪽 서브트리의 오른쪽 자식노드 쪽에 불균형이 생겼으므로
		// RR 회전을 한다.
		else
			n = Rotate_RR(n);
	}

	return n;
}

NODE* AVL_Tree::Rotate_LL(NODE* A)
{
	NODE* B = A->left;
	A->left = B->right;
	B->right = A;
	return B;
}

NODE* AVL_Tree::Rotate_RR(NODE* A)
{
	NODE* B = A->right;
	A->right = B->left;
	B->left = A;
	return B;
}

NODE* AVL_Tree::Rotate_RL(NODE* A)
{
	NODE* B = A->right;
	A->right = Rotate_LL(B);
	return Rotate_RR(A);
}

NODE* AVL_Tree::Rotate_LR(NODE* A)
{
	NODE* B = A->left;
	A->left = Rotate_RR(B);
	return Rotate_LL(A);
}

void AVL_Tree::ClearAll(NODE* root)
{
	// 모두 삭제
	// 후위순회 순으로 삭제한다
	if (nullptr == root)
		return;

	ClearAll(root->left);
	ClearAll(root->right);
	SAFE_DELETE(root);
}

 

main()

다음과 같은 트리를 만들어보자. 만약 AVL트리로 계속해서 균형을 맞춰 나간다면 다음과 같은 트리로 변형될 것이다.

 

코드는 다음과 같다.

#include "pch.h"
#include "AVL_Tree.h"

int main()
{
	AVL_Tree tree;

	cout << "[삽입 연산] : 6 8 9 11 10";
	tree.Insert_AVL(6);
	tree.Insert_AVL(8);
	tree.Insert_AVL(9);
	tree.Insert_AVL(11);
	tree.Insert_AVL(10);

	cout << "\n 트리의 높이 = " << tree.CalcHeight(tree.GetRoot()) << endl;

	tree.Search_AVL(10);
	tree.Search_AVL(11);
}

만약 균형을 잡지 않는다면 트리의 높이는 5가 될 것이다. 그리고 10을 찾는 데에는 5번의 탐색이 11을 찾는데에는 4번의 탐색이 필요할 것이다. 

 

출력 값

 

균형을 맞춰주었기 때문에 트리의 높이가 5가 아닌 3이 되었고, 10을 찾는 데에는 5번이 아닌 2번만에, 11을 찾는데에는 4번이 아닌 3번의 탐색이 필요하게 되었다.