[자료구조] AVL 트리

AVL 트리란?

이번글은 https://cjbworld.tistory.com/25 의 코드에 기반을 두고 확장하여 작성한 버젼입니다.

기존의 이진 탐색트리에서 탐색의 경우 "로그 시간복잡도를 보장해준다"라고 알고있는데 예외가 존재합니다.

바로 BST애 데이터를 삽입할 때 데이터들을 오름차순으로 삽입할 경우 트리의 모양이 

요런식으로 되어 버려 탐색시 로그 시간복잡도가 안나온다는 것입니다... 선형시간 복잡도가 나오겠지용

 

그래서 이러한 문제점을 해결해주는 도구들이 바로 AVL 트리, 2-3-4트리, B트리, 2-3트리, Red-Black트리 등등이 있습니다.

이중에서도 AVL트리에 대해서 다뤄볼 것인데요. 이 AVL트리에는 위의 그림판 그림처럼 "균형"이 안맞는 상황을 위해 몇가지 개념이 추가가 됩니다.

바로 "균형 인수"와 "회전"의 개념입니다.

균형인수는 그냥 트리의 균형이 현재 맞는지 안 맞는지를 값으로 표현한 것이구요 

회전의 경우 회전행렬과 같은 것과는 상관없는 약간 다른 의미의 회전입니다.(근데 회전이기는 한거같습니다...ㅎㅎ)

 

균형인수는 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이 를 통해서 구할 수 있습니다.

회전의 경우 LL회전, LR회전, RR회전, RL회전이 있습니다.

 

RR회전의 말뜻은 아래처럼 1이 Root라 가정할 때 Right Child가 두번 연속해서 있을 때 하는 회전이라는 의미입니다.

RL의 경우에는 Root에서 Right Child가 있고 Right Child의 Left Child가 있을 경우를 말합니다.

LL회전의 경우에도 마찬가지 입니다. 자식이 왼쪽으로만 두개가 달려있을 경우에 하는 회전을 의미합니다.

핵심은 AVL트리는 균형인수값에 따라 현재 트리의 균형이 맞는지 안 맞는지 판단하여 균형이 맞지 않다면 트리의 구조를 확인해서 LL회전을 해야하는지 LR회전을 해야하는지 RR회전을 해야하는지 ,RL회전을 해야하는지 보고 회전을 시켜 트리의 균형을 맞추는 트리입니다.

 

구현

일단 필요한 함수들을 정리해보자면 균형인수를 구하기 위해 현재 트리의 높이를 구해주는 함수가 필요할 거같습니다.

해당 함수를 GetHegith라고 하겠습니다.

그리고 실제로 구한 높이값을 기반으로 균형인수값을 셋팅해주는 함수가 필요할거같습니다.

해당함수를 GetHeightDiff라고 하겠습니다.

저는 균형인수값이 2이상의 양수라면은 LL회전 또는 LR회전을 해야하는 상황이라고 하겠습니다.

만약 균형인수 값이 -2이하의 음수값이라면은 RR회전 또는 RL회전을 해야하는 상황이라고 하겠습니다.

 

먼저 GetHeight함수부터 보도록 하겠습니다.

// 트리 높이를 계산하여 반환
int GetHeight(BTNP bst)
{
	int leftHeight = 0;
	int rightHeight = 0;

	if (bst == nullptr) return 0;

	leftHeight = GetHeight(GetLeftSubTree(bst)); // 왼쪽 서브 트리 높인 계산
	rightHeight = GetHeight(GetRightSubTree(bst)); // r 서브 트리 높이 계산

	// 큰 값의 높이를 반환
	if (leftHeight > rightHeight) return leftHeight + 1;
	else return rightHeight + 1;
}

BTNP는 BTN타입의 포인터를 typedef로 제가 재정의한 형식입니다. (밑에 전체코를 올려두었습니다)

아무튼 포인터를 얻어와서 높이를 구하기 위해 GetHeight함수를 "재귀적"으로 호출하여 bst로부터 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이를 구해옵니다.

GetLeftSubTree만을 얻어온다음에 GetHeight함수를 호출하는 이유는 이진탐색트리 특성상 가장 작은 값은 Root로 부터 시작하여 가장 왼쪽자식에 저장되기 때문입니다. 오른쪽 서브트리의 높이를 구하기 위해서 현재 노드로부터 오른쪽 자식을 얻어오는 이유도 이와 같습니다.

혹시 위의 말과 "왼쪽자식을 얻어와서 높이를 구하는게 왼쪽서브트리의 높이를 구하는 것과 일치한다"라는 말이 이해가 안가신다면 https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/ 해당 블로그 글을 참고해주시면 되겠습니다.

 

이후 어떤 서브트리의 높이가 더 높은지를 if문으로 비교하여 큰 높이를 반환합니다.

 

그리고 균형인수값을 판단하는 함수를 구현해보도록 하겠습니다.

int GetHeightDiff(BTNP bst)
{
	int lsh = 0; // left sub tree height;
	int rsh = 0; // right sub tree height;

	if (bst == nullptr) return 0;
	lsh = GetHeight(GetLeftSubTree(bst)); // left 서브트리 높이
	rsh = GetHeight(GetRightSubTree(bst)); // 오른쪽 서브트리 높이
	return lsh - rsh; // 균형 인수 계산결과 반환
}

위 함수는 GetHeight함수를 호출하는 함수입니다. lsh, rsh는 제가 정한 방식대로 두값을 빼서 return하도록 하였습니다.

이 값은 Rebalance라는 함수안에서 받게 되는데 Rebalance함수는 AVL트리의 삽입과 삭제부분에서 각각 호출하게됩니다.

균형이 깨지는 경우는 삽입과 삭제 부분에서 발생하기 때문이죠.

 

그러면 Rebalance함수를 보도록 하겠습니다.

// 트리의 균형을 
BTNP Rebalance(BTNP* pRoot)
{
	int heightDiff = GetHeightDiff(*pRoot); // 균형인수 계산

	// 균형 인수가 +2이상이라면 LL상태 또는 LR상태이다.
	if (heightDiff > 1) // Left 서브 트리 방향으로 높이가 2 이상 크다면,
	{
		if (GetHeightDiff(GetLeftSubTree(*pRoot)) > 0) *pRoot = RotateLL(*pRoot);
		else *pRoot = RotateLR(*pRoot);
	}

	// 균형인수가 -2 이하이면 RR상태 또는 RL상태이다.
	if (heightDiff < -1)
	{
		if (GetHeightDiff(GetRightSubTree(*pRoot)) < 0) *pRoot = RotateRR(*pRoot);
		else RotateRL(*pRoot);
	}

	return *pRoot;
}

위에서 설명한대로 GetHeightDiff함수를 호출하영 균형인수값(heightDiff)를 얻어온다음에 이 값이 2이상이라면은 왼쪽서브트리가 균형이 맞지 않다는 말이고 반대로 -2이상이라면은 오른쪽에 균형이 무너졌다라는 말입니다.

2이상인경우 LL회전 또는 LR회전을 해야하는 상태이고 -2이상이라면은 RR회전 또는 RL회전을 해야하는 상황이라고 말씀드렸습니다.

 

그래서 heightDiff > 1 이상인 블록에서 보면은 다시 pRoot를 대상으로 GetLeftSubTree를 가져와서 균형인수를 구해오는데 이번에는 계산한 균형인수 값이 0보다 크다면 LL회전을 합니다.

그림으로 표현하면 이런 모양이겠죠.

 

루트로 부터 L을 얻어와서 GetHeightDiff 함수를 통해 L의 왼쪽 서브트리와 오른쪽 서브트리의 높이를 가져와 계산하여 균형인수 값을 구합니다. 이또한 0이상인 경우 L의 왼쪽 서브트리가 높다는 말이기 때문에 LL회전을 해야한다는 말이고 반대로 0보다작으면 LR회전을 해야합니다.(L의 오른쪽 서브트리의 높이가 높다는 말이기 때문에)

 

그러면 이제 여기서 회전을 알아보도록 하겠습니다.

먼저 LL회전부터 알아보도록 하겠습니다.

LL회전은 Left Child가 연달아서 있는 경우에 회전해야 하는 경우를 LL회전이라고 말씀드렸는데요.

그러면 어떤식으로 회전을 해야 균형이 맞을까요??

요런식으로 L을 내려주시면 됩니다. L의 왼쪽 자식의 오른쪽 자식으로 L을 이동시켜 주시면됩니다.

그리고 L의 부모가 된 노드를 Root의 왼쪽 자식으로 이어주면됩니다.

그러면 위처럼 Root를 기준으로 왼쪽 서브트리의 높이와 오른쪽 서브 트리의 높이를 구하여 균형인수를 구했을때 2이상의 양수값이나 -2이하의 값이 안나오고 균형이 맞겠죠?

 

그러면 L을 기존의 L의 왼쪽 자식의 오른쪽 자식으로 옮겨도 문제가 없냐? 라고 물어보시면 AVL트리는 이진탐색트리에 기반을 두고 있기 때문에 L의 왼쪽 자식의 오른쪽 자식으로 이동하기 전에 L의 값을 보면 L의 왼쪽 자식보다는 무조건 큰값이고 Root보다는 무조건 작습니다. 오른쪽 자식에는 자기자신보다 큰 값만 올 수 있기때문에 L은 이동하기전의 L의 왼쪽자식보다는 값이 크고 Root보다는 값이 작기 때문에 L의 왼쪽 자식의 오른쪽 자식의 위치로 옮겨져도 괜찮습니다.

(RR회전의 경우는 LL회전과 반대로 진행하시면됩니다)

 

LR의 경우에도 보도록 하겠습니다.

위와 같은 상황이 LR회전을 해야하는 상황입니다. Root를 기준으로 GetHeightDiff를 통해 균형인수 값을 구해오면 2이상의 양수값이 나와 균형이 파괴된 모습입니다.

그래서 다시 Root의 왼쪽 자식을 가져와 균형인수를 구해보니 음수값이 나오게 된 상황입니다.

이때 LR회전을 통해서 균형을 맞추어야 하는데 LR회전의 경우 회전을 두번을 거쳐야 합니다.

가령 위처럼 LR회전 상태라고 가정할 경우 먼저 "부분적 RR회전"을 진행한뒤에 "LL회전"을 진행하면됩니다.

여기 이렇게 3의 오른쪽 자식이 빈 노드가 있다고 가정을 하고 1을 기준으로 부분 RR회전을 하게되면 

이런식이 되겠지요. 그리고 다시 트리를 보면은 

위와 같은 다시 LL회전을 진행해야하는 상황입니다. 여기서 LL회전을 진행해서 5를 3의 오른쪽 자식으로 보내고 3을 Root의 왼쪽 자식으로 바꿔치기 해주면됩니다.

RL회전의 경우에도 마찬가지 입니다. 부분 LL회전을 시킨다음에(쭉 펴주고) RR 회전을 진행하시면 됩니다.

 

---

코드를 보시기 전에 AVLTree는 BST에 기반한 것이고 Binary SearchTree는 BinaryTree에 기반한 알고리즘입니다.

하지만 저는 AVLTree에 관한 코드를 이진탐색트리에 균형을 잡기위한 도구로써 사용하였습니다.

그래서 BinarySearchTree파일의 코드는 BinaryTree3.h에 기반을 두고 이진탐색트리를 구현하였고 이곳에서 AVLTree의 로직을 사용하여 AVLTree를 구현하였기에 코드를 올리는 순서를

 

BinaryTree3.h => AVLRebalance.h => BinarySearchTree3.h 순으로 올리도록 하겠습니다.

BinaryTree

BinaryTree3.h

#pragma once

namespace BT3
{
	typedef int BTData;

	typedef struct _bTreeNode
	{
		BTData data;
		struct _bTreeNode* left;
		struct _bTreeNode* right;
	} BTN;

	BTN* MakeBTreeNode(void);
	BTData GetData(BTN* bt);
	void SetData(BTN* bt, BTData data);
	BTN* GetLeftSubTree(BTN* bt);
	BTN* GetRightSubTree(BTN* bt);

	void MakeLeftSubTree(BTN* main, BTN* sub);
	void MakeRightSubTree(BTN* main, BTN* sub);

	typedef void (*VisitFuncPtr) (BTData data);

	void PreorderTraverse(BTN* bt, VisitFuncPtr action);
	void InorderTraverse(BTN* bt, VisitFuncPtr action);
	void PostorderTraverse(BTN* bt, VisitFuncPtr action);

	BTN* RemoveLeftSubTree(BTN* bt);
	BTN* RemoveRightSubTree(BTN* bt);
	void ChangeLeftSubTree(BTN* main, BTN* sub);
	void ChangeRightSubTree(BTN* main, BTN* sub);
};

BinaryTree3.cpp

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

BT3::BTN* BT3::MakeBTreeNode(void)
{
	BT3::BTN* NewNode = (BT3::BTN*)malloc(sizeof(BT3::BTN));
	NewNode->left = nullptr;
	NewNode->right = nullptr;
	return NewNode;
}

BT3::BTData BT3::GetData(BTN* bt)
{
	return bt->data;
}

void BT3::SetData(BTN* bt, BTData data)
{
	bt->data = data;
}

BT3::BTN* BT3::GetLeftSubTree(BTN* bt)
{
	return bt->left;
}

BT3::BTN* BT3::GetRightSubTree(BTN* bt)
{
	return bt->right;
}

void BT3::MakeLeftSubTree(BTN* main, BTN* sub)
{
	if (main->left != nullptr) free(main->left);
	main->left = sub;
}

void BT3::MakeRightSubTree(BTN* main, BTN* sub)
{
	if (main->right != nullptr) free(main->right);
	main->right = sub;
}

void BT3::PreorderTraverse(BTN* bt, VisitFuncPtr action)
{
	if (bt == nullptr) return;
	action(bt->data);
	PreorderTraverse(bt->left, action);
	PreorderTraverse(bt->right, action);
}

void BT3::InorderTraverse(BTN* bt, VisitFuncPtr action)
{
	if (bt == nullptr) return;
	InorderTraverse(bt->left, action);
	action(bt->data);
	InorderTraverse(bt->right, action);
}

void BT3::PostorderTraverse(BTN* bt, VisitFuncPtr action)
{
	if (bt == nullptr) return;
	PostorderTraverse(bt->left, action);
	PostorderTraverse(bt->right, action);
	action(bt->data);
}

BT3::BTN* BT3::RemoveLeftSubTree(BTN* bt)
{
	BT3::BTN* deleteNode = nullptr;
	if (bt != nullptr)
	{
		deleteNode = bt->left;
		bt->left = nullptr;
	}
	return deleteNode;
}

BT3::BTN* BT3::RemoveRightSubTree(BTN* bt)
{
	BT3::BTN* deleteNode = nullptr;
	if (bt != nullptr)
	{
		deleteNode = bt->right;
		bt->right = nullptr;
	}
	return deleteNode;
}

void BT3::ChangeLeftSubTree(BTN* main, BTN* sub)
{
	main->left = sub;
}

void BT3::ChangeRightSubTree(BTN* main, BTN* sub)
{
	main->right = sub;
}

AVLTree

AVLRebalance.h

#pragma once
#include "BinaryTree3.h"

typedef BT3::BTN BTN;
typedef BT3::BTN* BTNP;
typedef BT3::BTData Data;

BTNP Rebalance(BTNP* pRoot);

AVLRebalance.cpp

#include "AVLRebalance.h"

// LL 회전
BTNP RotateLL(BTNP bst)
{
	BTNP parentNode = nullptr;
	BTNP currentNode = nullptr;

	// parentNode가 currentNode로 LL회전을 위해 적절한 위치를 가르키게 한다.
	parentNode = bst;
	currentNode = GetLeftSubTree(parentNode);

	// 실제 LL회전을 담당하는 두 개의 문장
	ChangeLeftSubTree(parentNode, GetRightSubTree(currentNode));
	ChangeRightSubTree(currentNode, parentNode);

	// LL회전으로 인해서 변경된 루트 노드의 주소 값 반환
	return currentNode;
}

// RR 회전
BTNP RotateRR(BTNP bst)
{
	BTNP parentNode = nullptr;
	BTNP currentNode = nullptr;

	// parentNode가 currentNode로 RR회전을 위해 적절한 위치를 가르키게 한다.
	parentNode = bst;
	currentNode = GetRightSubTree(parentNode);
	
	// 실제 RR회전을 담당하는 두 개의 문장
	ChangeRightSubTree(parentNode, GetLeftSubTree(currentNode));
	ChangeLeftSubTree(currentNode, parentNode);

	// RR회전으로 인해서 변경된 루트 노드의 주소 값 반환
	return currentNode;
}

// RL 회전
BTNP RotateRL(BTNP bst)
{
	BTNP parentNode = nullptr;
	BTNP currentNode = nullptr;

	// parentNode와 currentNode가 RL회전을 위해 적절한 위치를 가르키게 한다.
	parentNode = bst;
	currentNode = GetRightSubTree(parentNode);

	// 실제 RL회전을 담당하는 두 개의 문장
	ChangeRightSubTree(parentNode, RotateLL(currentNode)); // 부분 LL회전
	return RotateRR(parentNode); // RR회전
}

// LR 회전
BTN* RotateLR(BTNP bst)
{
	BTNP parentNode = nullptr;
	BTNP currentNode = nullptr;

	// parentNode와 currentNode가 LR회전을 위해 적절한 위치를 가르키게 한다.
	parentNode = bst;
	currentNode = GetLeftSubTree(parentNode);

	// 실제 LR회전을 담당하는 두 개의 문장
	ChangeLeftSubTree(parentNode, RotateRR(currentNode)); // 부분 RR회전
	return RotateLL(parentNode); // LL회전
}

// 트리 높이를 계산하여 반환
int GetHeight(BTNP bst)
{
	int leftHeight = 0;
	int rightHeight = 0;

	if (bst == nullptr) return 0;

	leftHeight = GetHeight(GetLeftSubTree(bst)); // 왼쪽 서브 트리 높인 계산
	rightHeight = GetHeight(GetRightSubTree(bst)); // r 서브 트리 높이 계산

	// 큰 값의 높이를 반환
	if (leftHeight > rightHeight) return leftHeight + 1;
	else return rightHeight + 1;
}

int GetHeightDiff(BTNP bst)
{
	int lsh = 0; // left sub tree height;
	int rsh = 0; // right sub tree height;

	if (bst == nullptr) return 0;
	lsh = GetHeight(GetLeftSubTree(bst)); // left 서브트리 높이
	rsh = GetHeight(GetRightSubTree(bst)); // 오른쪽 서브트리 높이
	return lsh - rsh; // 균형 인수 계산결과 반환
}

// 트리의 균형을 
BTNP Rebalance(BTNP* pRoot)
{
	int heightDiff = GetHeightDiff(*pRoot); // 균형인수 계산

	// 균형 인수가 +2이상이라면 LL상태 또는 LR상태이다.
	if (heightDiff > 1) // Left 서브 트리 방향으로 높이가 2 이상 크다면,
	{
		if (GetHeightDiff(GetLeftSubTree(*pRoot)) > 0) *pRoot = RotateLL(*pRoot);
		else *pRoot = RotateLR(*pRoot);
	}

	// 균형인수가 -2 이하이면 RR상태 또는 RL상태이다.
	if (heightDiff < -1)
	{
		if (GetHeightDiff(GetRightSubTree(*pRoot)) < 0) *pRoot = RotateRR(*pRoot);
		else RotateRL(*pRoot);
	}

	return *pRoot;
}

Binary Search Tree

BinarySearchTree3.h

#pragma once
#include "BinaryTree3.h"

namespace BST3
{
	typedef BT3::BTData Data;
	typedef BT3::BTN BTN;
	typedef BT3::BTN* BTNP;

	// 이진 탐색 트리의 생성 및 초기화
	void BSTMakeAndInit(BTNP* pRoot);

	// 노드에 저장된 데이터 반환
	Data BSTGetNodeData(BTNP bt);

	// 이진 탐색 트리를 대상으로 데이터 저장(노드의 생성 과정 포함)
	// 예외 존재하는 Insert함수
	void BSTInsert(BTNP* pRoot, Data data);

	// 예외 처리가 된 재귀적 Insert함수
	BTNP BST3Insert(BTNP* pRoot, Data data);

	// 이진 탐색 트리를 대상으로 데이터 탐색
	BTNP BSTSearch(BTNP bst, Data target);

	// 트리에서 노드를 제거하고 제거된 노드의 주소값을 반환한다.
	BTNP BSTRemove(BTNP* pRoot, Data target);

	void ShowIntData(int data);

	// 이진 탐색 트리에 저장된 모든 노드의 데이터를 출력한다.
	void BSTShowAll(BTNP bst);
};

BinarySearchTree3.cpp

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

void BST3::BSTMakeAndInit(BTNP* pRoot)
{
	*pRoot = nullptr;
}

BST3::Data BST3::BSTGetNodeData(BTNP bt)
{
	return BT3::GetData(bt);
}

void BST3::BSTInsert(BTNP* pRoot, Data data)
{
	BTNP parentNode = nullptr;
	BTNP currentNode = *pRoot;
	BTNP newNode = nullptr;

	// 새로운 노드가 (새 데이터가 담긴 노드가) 추가될 위치를 찾는다.
	while (currentNode != nullptr)
	{
		// 데이터의 중복을 허용하지 않는다.
		if (data == BT3::GetData(currentNode)) return;

		parentNode = currentNode;

		if (BT3::GetData(currentNode) > data) currentNode = BT3::GetLeftSubTree(currentNode);
		else currentNode = BT3::GetRightSubTree(currentNode);
	}

	// parentNode의 자식노드로 추가할 새 노드의 생성
	newNode = BT3::MakeBTreeNode(); // 새 노드 생성
	SetData(newNode, data);			// 새노드에 데이터 저장

	// parentNode의 자식 노드로 새 노드르 추가
	if (parentNode != nullptr)
	{
		if (data < BT3::GetData(parentNode)) BT3::MakeLeftSubTree(parentNode, newNode);
		else BT3::MakeRightSubTree(parentNode, newNode);
	}
	// 새 노드가 루트 노드라면은
	else
	{
		*pRoot = newNode;
	}

	// 노드 추가후 Rebalance
	*pRoot = Rebalance(pRoot);
}

BTNP BST3::BST3Insert(BTNP* pRoot, Data data)
{
	if (*pRoot == nullptr)
	{
		*pRoot = BT3::MakeBTreeNode();
		BT3::SetData(*pRoot, data);
	}
	else if (data < BT3::GetData(*pRoot))
	{
		BST3Insert(&((*pRoot)->left), data);
		*pRoot = Rebalance(pRoot);
	}
	else if (data > BT3::GetData(*pRoot))
	{
		BST3Insert(&((*pRoot)->right), data);
		*pRoot = Rebalance(pRoot);
	}
	else return nullptr;

	return *pRoot;
}

BST3::BTNP BST3::BSTSearch(BTNP bst, Data target)
{
	BTNP currentNode = bst;
	Data cd; // currentData

	while (currentNode != nullptr)
	{
		cd = BT3::GetData(currentNode);

		if (target == cd) return currentNode;
		else if (target < cd) currentNode = BT3::GetLeftSubTree(currentNode);
		else currentNode = BT3::GetRightSubTree(currentNode);
	}

	return nullptr;
}

BST3::BTNP BST3::BSTRemove(BTNP* pRoot, Data target)
{
	// 삭제 대상이 루트 노드인 경우를 별도로 고려해야함.
	BTNP pvRoot = BT3::MakeBTreeNode(); // 가상 루트 노드
	BTNP parentNode = pvRoot; // parentNode
	BTNP currentNode = *pRoot;
	BTNP deleteNode = nullptr;

	// 루트 노드를 pvRoot가 가르키는 노드의 오른족 자식 노드가 되게한다.
	BT3::ChangeRightSubTree(pvRoot, *pRoot);

	// 삭제 대상인 노드를 탐색
	while (currentNode != nullptr && BT3::GetData(currentNode) != target)
	{
		parentNode = currentNode;
		if (target < BT3::GetData(currentNode)) currentNode = BT3::GetLeftSubTree(currentNode);
		else currentNode = BT3::GetRightSubTree(currentNode);
	}

	// 찾을 대상이 존재하지 않는다면
	if (currentNode == nullptr) return nullptr;

	// 삭제 대상을 deleteNode가 가르키게 한다.
	deleteNode = currentNode;

	// 첫번째 경우 : 삭제 대상이 단말 노드인경우
	if (BT3::GetLeftSubTree(deleteNode) == nullptr && BT3::GetRightSubTree(deleteNode) == nullptr)
	{
		if (BT3::GetLeftSubTree(parentNode) == deleteNode) BT3::RemoveLeftSubTree(parentNode);
		else BT3::RemoveRightSubTree(parentNode);
	}
	// 두번째 경우 : 삭제 대상이 하나의 자식 노드를 갖는경우
	else if (BT3::GetLeftSubTree(deleteNode) == nullptr || BT3::GetRightSubTree(deleteNode) == nullptr)
	{
		// 삭제 대상의 자식 노드를 가르킴
		BTNP deleteChildNode = nullptr;

		if (BT3::GetLeftSubTree(deleteNode) != nullptr) deleteChildNode = BT3::GetLeftSubTree(deleteNode);
		else deleteChildNode = BT3::GetRightSubTree(deleteNode);

		if (BT3::GetLeftSubTree(parentNode) == deleteNode) BT3::ChangeLeftSubTree(parentNode, deleteChildNode);
		else BT3::ChangeRightSubTree(parentNode, deleteChildNode);
	}
	// 세번째 경우 : 두 개의 자식 노드를 모두 갖는 경우
	else
	{
		// 대체 노드를 가르킴
		BTNP mNode = BT3::GetRightSubTree(deleteNode);

		// 대체 노드의 부모 노드를 가르킴
		BTNP mpNode = deleteNode;
		int delData = -1;

		// 삭제 대상의 대체 노드를 찾는다.
		while (BT3::GetLeftSubTree(mNode) != nullptr)
		{
			mpNode = mNode;
			mNode = BT3::GetLeftSubTree(mNode);
		}

		// 대체 노드에 저장된 값을 삭제할 노드에 대입한다.
		delData = BT3::GetData(deleteNode);				// 대입전 데이터 백업
		BT3::SetData(deleteNode, BT3::GetData(mNode));	// 대입 진행

		// 대체 노드의 부모노드와 대체 노드의 자식노드를 연결한다.
		if (BT3::GetLeftSubTree(mpNode) == mNode) BT3::ChangeLeftSubTree(mpNode, BT3::GetRightSubTree(mNode));
		else BT3::ChangeRightSubTree(mpNode, BT3::GetRightSubTree(mNode));

		deleteNode = mNode;
		BT3::SetData(deleteNode, delData); // 백업 데이터 복원
	}

	// 삭제된 노드가 루트 노드인 경우에 대한 추가적인 처리
	if (BT3::GetRightSubTree(pvRoot) != *pRoot) *pRoot = BT3::GetRightSubTree(pvRoot); // 루트 노드의 변경을 반영

	delete pvRoot;

	// 노드 제거후 Rebalance
	*pRoot = Rebalance(pRoot);

	return deleteNode;
}

void BST3::ShowIntData(int data)
{
	printf("%d ", data);
}

void BST3::BSTShowAll(BTNP bst)
{
	BT3::InorderTraverse(bst, ShowIntData);
}