12. 탐색 2

※ 해당 글은 C언어에 대한 이해를 필요로 합니다. C 언어에 대해 알고 싶으신 분들은 다음 글을 참고하세요

https://ward.tistory.com/category/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20%EC%96%B8%EC%96%B4/C

'프로그래밍 언어/C' 카테고리의 글 목록

 

(1) 균형 잡힌 이진 탐색 트리: AVL 트리의 이해

 

* 이진 탐색 트리의 문제점과 AVL 트리

이진 탐색 트리의 탐색 연산은 O(logn)의 시간 복잡도를 가진다. 그런데 이러한 이진 탐색 트리는 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다. 이러한 이진 탐색 트리의 단점을 해결한 트리를 가리켜 균형 잡힌 이진 탐색 트리라 하며 여러 종류가 있다. 그중 AVL 트리에 대해 알아보자.

 

* 자동으로 균형을 잡는 AVL 트리와 균형 인수

AVL 트리는 노드가 추가되거나 삭제될 때 트리의 균형 상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리이다.  AVL 트리에서는 균형의 정도를 표현하기 위해서 균형 인수를 사용하는데, 이 균형인수는 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이의 차이다. AVL 트리는 균형 인수의 절댓값이 2 이상인 경우 균형을 잡기 위한 트리의 재조정을 진행한다.

 

* AVL 트리의 리밸런싱

LL 회전

RR 회전

LR 회전

RL 회전

 

(2) 균형 잡힌 이진 탐색 트리: AVL 트리의 구현

 

* AVL 트리의 구현

이전에 구현한 이진 탐색 트리에 리밸런싱 기능을 추가한다. 이진 탐색 트리의 삽입과 삭제를 약간 수정한다.

리밸런싱

#include <stdio.h>
#include "BinaryTree3.h"

int GetHeight(BTreeNode* bst) {
	int leftH;
	int rightH;

	if (bst == NULL)
		return 0;
	leftH = GetHeight(GetLeftSubTree(bst));
	rightH = GetHeight(GetRightSubTree(bst));
	if (leftH > rightH)
		return leftH + 1;
	else
		return rightH + 1;
}

int GetHeightDiff(BTreeNode* bst) {
	int lsh, rsh;

	if (bst == NULL)
		return 0;
	lsh = GetHeight(GetLeftSubTree(bst));
	rsh = GetHeight(GetRightSubTree(bst));
	return lsh - rsh;
}

BTreeNode* RotateLL(BTreeNode* bst) {
	BTreeNode* pNode;
	BTreeNode* cNode;

	pNode = bst;
	cNode = GetLeftSubTree(bst);

	ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
	ChangeRightSubTree(cNode, pNode);

	return cNode;
}

BTreeNode* RotateRR(BTreeNode* bst) {
	BTreeNode* pNode;
	BTreeNode* cNode;

	pNode = bst;
	cNode = GetRightSubTree(bst);

	ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
	ChangeLeftSubTree(cNode, pNode);

	return cNode;
}

BTreeNode* RotateLR(BTreeNode* bst) {
	BTreeNode* pNode;
	BTreeNode* cNode;

	pNode = bst;
	cNode = GetLeftSubTree(pNode);

	ChangeLeftSubTree(pNode, RotateRR(cNode));
	return RotateLL(pNode);
}

BTreeNode* RotateRL(BTreeNode* bst) {
	BTreeNode* pNode;
	BTreeNode* cNode;

	pNode = bst;
	cNode = GetRightSubTree(pNode);

	ChangeRightSubTree(pNode, RotateLL(cNode));
	return RotateRR(pNode);
}

BTreeNode* Rebalance(BTreeNode** pRoot) {
	int hDiff = GetHeightDiff(*pRoot);

	if (hDiff > 1) {
		if (GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)
			*pRoot = RotateLL(*pRoot);
		else
			*pRoot = RotateLR(*pRoot);
	}
	if (hDiff < -1) {
		if (GetHeightDiff(GetRightSubTree(*pRoot)) < 0)
			*pRoot = RotateRR(*pRoot);
		else
			*pRoot = RotateRL(*pRoot);
	}
	return *pRoot;
}

AVL 트리

#include <stdio.h>
#include <stdlib.h>
#include "Rebalance.h"
#include "BinaryTree3.h"

typedef BTData BSTData;

void BSTMakeAndInit(BTreeNode** pRoot) {
	*pRoot = NULL;
}

BSTData BSTGetNodeData(BTreeNode* bst) {
	return GetData(bst);
}

void BSTInsert(BTreeNode** pRoot, BSTData data) {
	if (*pRoot == NULL)
	{
		*pRoot = MakeBTreeNode();
		SetData(*pRoot, data);
	}
	else if (data < GetData(*pRoot))
	{
		BSTInsert(&((*pRoot)->left), data);
		*pRoot = Rebalance(pRoot);
	}
	else if (data > GetData(*pRoot))
	{
		BSTInsert(&((*pRoot)->right), data);
		*pRoot = Rebalance(pRoot);
	}
	else
	{
		return NULL;
	}
	return *pRoot;
}

BTreeNode* BSTSearch(BTreeNode* bst, BSTData target) {
	BTreeNode* cNode = bst;
	BSTData cd;

	while (cNode != NULL) {
		cd = GetData(cNode);
		if (target == cd)
			return cNode;
		else if (target < cd)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}
	return NULL;
}

BTreeNode* BSTRemove(BTreeNode** pRoot, BSTData target) {
	BTreeNode* pVRoot = MakeBTreeNode();
	BTreeNode* pNode = pVRoot;
	BTreeNode* cNode = *pRoot;
	BTreeNode* dNode;

	ChangeRightSubTree(pVRoot, *pRoot);

	while (cNode != NULL && GetData(cNode) != target) {
		pNode = cNode;
		if (target < GetData(cNode))
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	if (cNode == NULL)
		return NULL;

	dNode = cNode;

	if (GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL) {
		if (GetLeftSubTree(pNode) == dNode)
			RemoveLeftSubTree(pNode);
		else
			RemoveRightSubTree(pNode);
	}
	else if (GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL) {
		BTreeNode* dcNode;

		if (GetLeftSubTree(dNode) != NULL)
			dcNode = GetLeftSubTree(dNode);
		else
			dcNode = GetRightSubTree(dNode);
		if (GetLeftSubTree(pNode) == dNode)
			ChangeLeftSubTree(pNode, dcNode);
		else
			ChangeLeftSubTree(pNode, dcNode);
	}
	else {
		BTreeNode* mNode = GetRightSubTree(dNode);
		BTreeNode* mpNode = dNode;
		int delData;

		while (GetLeftSubTree(mNode) != NULL) {
			mpNode = mNode;
			mNode = GetLeftSubTree(mNode);
		}

		delData = GetData(dNode);
		SetData(dNode, GetData(mNode));

		if (GetLeftSubTree(mpNode) == mNode)
			ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
		else
			ChangeRightSubTree(mpNode, GetRightSubTree(mNode));

		dNode = mNode;
		SetData(dNode, delData);
	}

	if (GetRightSubTree(pVRoot) != *pRoot)
		*pRoot = GetRightSubTree(pVRoot);

	free(pVRoot);

	*pRoot = Rebalance(pRoot);

	return dNode;
}

 

참조자료: 윤성우의 열혈 자료구조