(C/C++) 검색 - AVL 트리 - 균형잡힌 트리 탐색 (Balanced Tree Search)

검색 알고리즘은 검색 로직뿐만 아니라 삽입 삭제 로직도 같이 구현했습니다.

1. AVL 트리

앞서 설명해드린 이진 트리 탐색 (Binary Tree Search)에는 단점이 있습니다.

이진 트리 탐색은 O(log²n) 의 시간 복잡도를 가지지만 균형이 잡히지 않은 트리일수록 O(n)에 가까워 진다는 것 입니다.

트리의 균형을 잡기위한 여러가지 특성의 트리(균형잡힌 트리)가 있으며 

그중에 오늘 소개 드릴 트리는 AVL 입니다.  (AVL 은 이 트리를 개발한 사람의 이름 약자입니다.)

 

2. 구현 방법

검색, 삽입, 삭제는 앞서 구현한 이진 트리 탐색 (Binary Tree Search)과 동일합니다!

다만 삽입과 삭제시 트리의 균형을 검사하여 리밸런싱을 해주는 작업이 추가되었을 뿐입니다.

우선 트리가 균형을 검사하는 방법에 대해서 설명해 드리겠습니다.

AVL 트리는 트리의 균형을 '균형도(혹은 균형인자 등)' 으로 판단하는데

균형도는 다음과 같이 계산됩니다.

균형도 = 왼쪽 트리의 높이 - 오른쪽 트리의 높이 

균형도

이렇게 균형도를 계산했을 때 -1, 0, 1 은 균형이 잘 잡혀 있다는 것이 되고

-2 이하 혹은 2 이상일때 트리는 균형이 잡혀있지 않다고 판단하여 리밸런싱 작업을 합니다.

위 그림에서는 F 가 리밸런싱의 대상이 되게 되는 것이죠.

이제 리밸런싱의 대상을 알았으니 리밸런싱을 하는 4가지 방법에 대해서 알려드리겠습니다.

LL 회전

B 가 L 회전에서 C 위로 올라온다!

RR 회전

B 가 R 회전 해서 A 위로 올라온다!

LR 회전

B가 R 회전으로 A 위로 올라온뒤 다시 B 가 L 회전으로 C 위로 올라온다!

RL 회전

B 가 L 회전으로 C 위로 올라온뒤 다시 B 가 R 회전으로 A 위로 올라온다!

이렇게 4가지 방법이 있는데요

LR 회전과 RR 회전은 한번 LL 상태 RR 상태로 만든뒤 LL 회전 RR 회전을 한다고 보시면 됩니다.

이제 맨 처음 보셧던 그림에서 F 가 RR 회전을 하면 균형이 잡히는 것을 아실수 있습니다.

 

3. 링크드리스트를 이용한 AVL 트리 구현

#pragma once
#include <iostream>

struct Data
{
	int key;
	int phone;
};

class AVLTreeList
{
	struct Node
	{
		Data data;
		Node* left;
		Node* right;
	};

	enum RotateDir
	{
		NONE,
		LL,
		RR,
		LR,
		RL,
	};

	class NodeStack
	{
		struct StackNode
		{
			Node* data;
			StackNode* next;
		};

	private:
		StackNode head;
		StackNode tail;
	public:
		NodeStack()
		{
			head.next = &tail;
			tail.next = &tail;
		}
		bool Push(Node* value)
		{
			StackNode* newStackNode = new StackNode;
			newStackNode->data = value;
			newStackNode->next = head.next;
			head.next = newStackNode;
			return true;
		}
		bool Pop(Node** pop)
		{
			if (head.next == &tail)
				return false;

			StackNode* deleteStackNode = head.next;
			head.next = deleteStackNode->next;
			*pop = deleteStackNode->data;
			delete deleteStackNode;

			return true;
		}
	};

private:
	Node root;			//root 는 더미노드, 실직적 root 는 root.left

	void Traverse(Node* node);


	NodeStack stack;

	void Rebalance();
	void RebalancingPivot(Node* node);
	bool RebalancingNode(Node* node, Node** rotatedNode);
	int GetHeight(Node* node);
	bool Rotate(Node* node, RotateDir dir, Node** rotatedNode);

public:
	AVLTreeList();

	bool Search(int key, Data& data);
	bool Insert(Data data);
	bool Delete(int key);

	void PrintAll();
};

이진 트리 탐색의 헤더 입니다.

대부분의 코드는 이진 트리 탐색 (Binary Tree Search) 코드와 동일합니다.

AVL 트리에서는 리밸런싱을 해줄 노드를 담을 stack 을 하나 구현했고

(사실 템플릿으로 스택을 만들어 사용하는게 좋긴합니다.)

리밸런싱 관련 함수들을 추가해주었습니다.

#include "AVLTreeList.h"


AVLTreeList::AVLTreeList()
{
	root.left = nullptr;
	root.right = nullptr;
}

bool AVLTreeList::Search(int key, Data& data)
{
	Node* currentNode = root.left;
	while (currentNode != nullptr)
	{
		if (currentNode->data.key == key)
		{
			data = currentNode->data;
			return true;
		}
		if (currentNode->data.key > key)
			currentNode = currentNode->left;
		else if (currentNode->data.key < key)
			currentNode = currentNode->right;
	}
	return false;
}

bool AVLTreeList::Insert(Data data)
{
	Node* parentNode = &root;
	Node* currentNode = root.left;
	bool isLeft = true;

	while (currentNode != nullptr)		//(왼쪽 혹은 오른쪽 자식이 비어있는)부모 노드를 찾는 과정
	{
		if (data.key == currentNode->data.key)
			return false;

		stack.Push(parentNode);	//리밸런싱을 위해 저장
		parentNode = currentNode;

		if (data.key > currentNode->data.key)
		{
			isLeft = false;
			currentNode = currentNode->right;
		}
		else if (data.key < currentNode->data.key)
		{
			isLeft = true;
			currentNode = currentNode->left;
		}
	}
	currentNode = new Node;		//새로운 노드를 만들고
	currentNode->data = data;
	currentNode->left = nullptr;
	currentNode->right = nullptr;

	isLeft == true ? parentNode->left = currentNode : parentNode->right = currentNode;

	Rebalance();

	return true;
}

bool AVLTreeList::Delete(int key)
{
	Node* parentNode = &root;	//지울노드가 맨처음 노드 일경우를 대비해서 가상노드 루트가 있다.
	Node* deleteNode = root.left;
	bool isLeft = true;

	while (deleteNode != nullptr)	//지울 노드를 찾는 과정
	{
		if (deleteNode->data.key == key)
			break;

		stack.Push(parentNode);	//리밸런싱을 위해 저장
		parentNode = deleteNode;

		if (deleteNode->data.key < key)
		{
			isLeft = false;
			deleteNode = deleteNode->right;
		}
		else if (deleteNode->data.key > key)
		{
			isLeft = true;
			deleteNode = deleteNode->left;
		}
	}

	if (deleteNode == nullptr)	//지울 노드를 못찾았다면
	{
		return false;
	}
	else if (deleteNode->data.key == key)	//지울 노드를 찾았다면
	{
		Node* currentParentNode = nullptr;
		Node* currentNode = nullptr;
		if (deleteNode->left != nullptr && deleteNode->right != nullptr)	//지울 노드가 자식 둘 있는 노드
		{
			currentNode = deleteNode->right;
			if (currentNode->left != nullptr)				//오른쪽 노드가 제일 작은 값이 아닌 경우
			{
				while (currentNode->left != nullptr)
				{
					currentParentNode = currentNode;
					currentNode = currentNode->left;	//오른쪽 노드에서 가장 작은 값(가장 왼쪽 노드)을 찾는다.
				}
				currentParentNode->left = currentNode->right;	//작은 노드의 오른쪽 값을 작은노드 부모 노드가 받는다.
				currentNode->right = deleteNode->right;			//지울 노드의 오른쪽을 받는다.
			}

			currentNode->left = deleteNode->left;	//지울 노드의 왼쪽을 받는다.
		}
		else		//지울노드가 하나 혹은 없는 경우
		{
			//왼쪽 자식이 있으면 왼쪽, 오른쪽 자식이 있거나 자식이 하나도 없으면 오른쪽
			//있으면 (왼쪽 혹은 오른쪽)자식 노드가 들어가고 없으면 (자식 오른쪽에 있던)nullptr 값이 들어간다.
			currentNode = deleteNode->left != nullptr ? deleteNode->left : deleteNode->right;
		}

		isLeft == true ? parentNode->left = currentNode : parentNode->right = currentNode; //찾은 값을 지울 노드 위치로

		delete deleteNode;

		Rebalance();

		return true;
	}
	return false;
}

void AVLTreeList::PrintAll()
{
	Traverse(root.left);
}

void AVLTreeList::Traverse(Node* node)
{
	if (node == nullptr)
		return;

	printf("key : %d  phone : %d\n", node->data.key, node->data.phone);
	Traverse(node->left);
	Traverse(node->right);

	return;
}

void AVLTreeList::Rebalance()
{
	Node* balanceCheckNode = nullptr;
	while (stack.Pop(&balanceCheckNode))	//스택을 돌면서 
	{
		RebalancingPivot(balanceCheckNode);
	}
}

void AVLTreeList::RebalancingPivot(Node* node)
{
	Node* rotatedNode = nullptr;
	if (RebalancingNode(node->left, &rotatedNode))
	{
		node->left = rotatedNode;
	}
	else if (RebalancingNode(node->right, &rotatedNode))
	{
		node->right = rotatedNode;
	}
}

bool AVLTreeList::RebalancingNode(Node* node, Node** rotatedNode)
{
	if (node == nullptr)
		return false;

	int rootDif = GetHeight(node->left) - GetHeight(node->right);	//균형도를 검사한다.
	int childDif;

	if (rootDif >= 2)	//왼쪽이 더 많다.
	{
		childDif = GetHeight(node->left->left) - GetHeight(node->left->right);	//LL 회전인지 LR 회전인지 판단
		Rotate(node, childDif >= 1 ? LL : LR, rotatedNode);	//회전
	}
	else if (rootDif <= -2)	//오른쪽이 더 많다.
	{
		childDif = GetHeight(node->right->left) - GetHeight(node->right->right);	//RR 회전인지 RL 회전인지 판단
		Rotate(node, childDif <= -1 ? RR : RL, rotatedNode);	//회전
	}
	else				//균형도가 맞는다.
		return false;
	return true;
}

int AVLTreeList::GetHeight(Node* node)	//노드의 높이를 계산하는 함수
{
	if (node == nullptr)
		return 0;

	int left = GetHeight(node->left);
	int right = GetHeight(node->right);

	return (left > right ? left : right) + 1;
}

bool AVLTreeList::Rotate(Node* node, RotateDir dir, Node** rotatedNode)
{
	if (node == nullptr)
		return false;

	Node* childNode = nullptr;
	Node* grandChildNode = nullptr;

	switch (dir)
	{
	case LL:
		//node 기준 L 회전
		childNode = node->left;
		node->left = childNode->right;
		childNode->right = node;
		break;
	case RR:
		//node 기준 R 회전
		childNode = node->right;
		node->right = childNode->left;
		childNode->left = node;
		break;
	case LR:		//LR 의 경우 자식노드를 RR 회전통해 LL 상태로 만들어야한다.
		childNode = node->left;

		//node->right 기준 R 회전
		grandChildNode = childNode->right;
		childNode->right = grandChildNode->left;
		grandChildNode->left = childNode;
		node->left = grandChildNode;

		//node 기준 L 회전
		childNode = node->left;
		node->left = childNode->right;
		childNode->right = node;
		break;
	case RL:		//RL 의 경우 자식노드를 LL 회전통해 RR 상태로 만들어야한다.
		childNode = node->right;

		//node->left 기준 L 회전
		grandChildNode = childNode->left;
		childNode->left = grandChildNode->right;
		grandChildNode->right = childNode;
		node->right = grandChildNode;

		//node 기준 R 회전
		childNode = node->right;
		node->right = childNode->left;
		childNode->left = node;
		break;
	default:
		return false;
	}

	*rotatedNode = childNode;	//회전한 노드 (부모노드와 연결이 안된상태)
	return true;
}

이진 트리 탐색의 CPP 입니다.

이진 트리 탐색 (Binary Tree Search) 의 기존코드와 달라진 점이 있다면

Insert Delete 에서 노드를 찾아 이동할때 마다 노드를 스택에 저장하고

마지막 저장, 삭제 후에 스택에 있는 노드를 대상으로 리밸런싱 여부를 검사하여 리밸런싱을 진행합니다.

리밸런싱은 스택의 저장된 피벗을 기준으로 자식 노드를 검사합니다. //RebalancingPivot 함수 호출

(맨 처음 그림의 F 가 RR 회전이 필요했고 F의 부모노드인 E 가 피벗 노드입니다!)

피벗의 자식 노드 균형도를 검사하여 리밸런싱이 필요하다면 리밸런싱을 진행합니다. //RebalancingNode 함수 호출

리밸런싱을 했다면 피벗노드와 리밸런싱된 노드를 연결 시켜 줍니다. // RebalancingNode 함수 반환값을 연결

 

감사합니다.