4-2. 이진 탐색 트리(BST ; Binary Search Tree)

1. 기본 구조

(1) 트리 형태로 출력하기

트리 형태로 출력하기 위해 콘솔 창의 커서 위치를 지정할 수 있는 함수를 사용한다.

#include <windows.h>
using namespace std;

void SetCursorPosition(int x, int y)
{
	HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE);
	COORD pos = { static_cast<SHORT>(x), static_cast<SHORT>(y) };
	::SetConsoleCursorPosition(output, pos);
}

BinarySearchTree.cpp

SetCursorPosition 함수에 x와 y값을 입력하여 출력되는 값의 위치를 조정할 수 있다.

 

(2) 노드

struct Node
{
	Node* left = nullptr;
	Node* right = nullptr;
	Node* parent = nullptr;
	int   key = { }; //data
};

BinarySearchTree.h

부모 노드의 좌측과 우측에 다음 노드가 올 수 있도록 left, right 포인터를 선언한다.

추적할 수 있도록 parent 포인터를 선언한다.

데이터를 저장하는 int형 key 배열을 저장한다.

 

(3) 함수

class BinarySearchTree
{
public:
	void Print() { Print(_root, 10, 0); }
	void Print(Node* node, int x, int y);
	void Print_Inorder() { Print_Inorder(_root); }
	void Print_Inorder(Node* node);

	// 데이터 탐색
	Node* Search(Node* node, int key);
	Node* Min(Node* node);
	Node* Max(Node* node);
	Node* Next(Node* node);

	// 데이터 추가, 삭제
	void Insert(int key);
	void Delete(int key);
	void Delete(Node* node);

	void Replace(Node* u, Node* v);

private:
	Node* _root = nullptr;
};

BinarySearchTree.h

class BinarySearchTree
{
public:
	void Print() { Print(_root, 10, 0); }
	void Print(Node* node, int x, int y);
	void Print_Inorder() { Print_Inorder(_root); }
	void Print_Inorder(Node* node);

- 루트부터 출력하는 Print() 함수를 선언한다. 이어 출력할 노드와 커서의 위치 좌표를 받을 수 있는 오버로딩된 Print 함수를 선언한다.

- 트리를 전위 순회하는 Print_Inorder 함수를 선언한다.

 

	// 데이터 탐색
	Node* Search(Node* node, int key);
	Node* Min(Node* node);
	Node* Max(Node* node);
	Node* Next(Node* node);

- 데이터를 탐색하기 위한 Search 함수, 최댓값 Max 함수, 최소값 Min 함수, 입력된 노드 다음으로 큰 값을 가진 노드를 출력하는 Next 함수를 선언한다.

 

	// 데이터 추가, 삭제
	void Insert(int key);
	void Delete(int key);
	void Delete(Node* node);

	void Replace(Node* u, Node* v);

- 데이터를 입력받아 트리에 삽입하는 Insert 함수를 선언한다.

- 노드를 값으로 받는 Delete 함수를 선언한다. 

- 키 값을 받는 Delete 함수를 선언한다. 입력된 값을 루트에서부터 탐색 후에 매개변수를 노드를 받는 Delete 함수에 전달한다.

- Delete 함수를 구현하기 전에, 서브 트리 간의 위치를 바꿔주는 Replace 함수를 구현한다.

 

2. 코드 분석

#include "BinarySearchTree.h"
#include <iostream>
#include <windows.h>
using namespace std;

void SetCursorPosition(int x, int y)
{
	HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE);
	COORD pos = { static_cast<SHORT>(x), static_cast<SHORT>(y) };
	::SetConsoleCursorPosition(output, pos);
}

void BinarySearchTree::Print(Node* node, int x, int y)
{
	if (node == nullptr)
		return;

	SetCursorPosition(x, y);
	cout << node->key;
	Print(node->left, x - (5 / (y + 1)), y + 1);
	Print(node->right, x + (5 / (y + 1)), y + 1);
}

void BinarySearchTree::Print_Inorder(Node* node)
{
	// 전위 순회(preorder traverse)
	// 부모 -> 왼쪽 서브트리 -> 오른쪽 서브트리
	if (node == nullptr)
		return;

	cout << node->key << endl;
	Print_Inorder(node->left);
	Print_Inorder(node->right);


	// 중위 순회(inorder)
	// 후위 순회(postorder)

}

Node* BinarySearchTree::Search(Node* node, int key)
{
	if (node == nullptr || key == node->key)
		return node;

	// 재귀 함수 구조
	if (key < node->key)
		return Search(node->left, key);
	else
		return Search(node->right, key);

}

Node* BinarySearchTree::Min(Node* node)
{ // 왼쪽에 있는 노드가 더 작다, nullptr까지
	while (node->left)
		node = node->left;

	return node;
}

Node* BinarySearchTree::Max(Node* node)
{ // 오른쪽에 있는 노드가 더 크다, nullptr까지
	while (node->right)
		node = node->right;

	return node;
}

Node* BinarySearchTree::Next(Node* node)
{ // 이 노드 다음으로 큰 노드
	if (node->right) // 서브 노드의 최소값
		return Min(node->right);

	Node* parent = node->parent;

	// 부모가 유효하고 이 노드가 부모의 우측에 있다면
	while (parent && node == parent->right)
	{	// 위로 역행하며 올라감
		node = parent; // 이 노드의 부모로 올라감
		parent = parent->parent; // 부모의 부모를 parent로 설정
	}

	return parent;
}

void BinarySearchTree::Insert(int key)
{
	Node* newNode = new Node();
	newNode->key = key;

	if (_root == nullptr)
	{
		_root = newNode;
		return;
	}

	Node* node = _root;
	Node* parent = nullptr;

	while (node)
	{
		parent = node; // 초기화
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}
	// 부모의 왼쪽 or 오른쪽에 붙임
	newNode->parent = parent;

	if (key < parent->key)
		parent->left = newNode;
	else
		parent->right = newNode;
}

void BinarySearchTree::Delete(int key)
{
	Node* deleteNode = Search(_root, key);
	Delete(deleteNode);
}

void BinarySearchTree::Delete(Node* node)
{
	if (node == nullptr)
		return;

	if (node->left == nullptr) // 자식이 우측에 하나거나 없음
		Replace(node, node->right);
	else if (node->right == nullptr) // 자식이 좌측에 하나거나 없음
		Replace(node, node->left);
	else
	{ // 다음 데이터 찾기
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}

// u 서브트리를 v 서브트리로 교체
// u를 동적 할당 해제
void BinarySearchTree::Replace(Node* u, Node* v)
{	// 부모에서 자식으로 연결하기
	if (u->parent == nullptr) // null이면 루트 노드
		_root = v;
	else if (u == u->parent->left) // 이 노드가 부모 좌측에 위치
		u->parent->left = v;
	else
		u->parent->right = v;

	if (v) // 자식에서 부모로 연결하기
		v->parent = u->parent;

	delete u;
}

BinarySearchTree.cpp

 

(1) 출력 함수(Print, Print_Inorder)

void BinarySearchTree::Print(Node* node, int x, int y)
{
	if (node == nullptr)
		return;

	SetCursorPosition(x, y);
	cout << node->key;
	Print(node->left, x - (5 / (y + 1)), y + 1);
	Print(node->right, x + (5 / (y + 1)), y + 1);
}

void BinarySearchTree::Print_Inorder(Node* node)
{
	// 전위 순회(preorder traverse)
	// 부모 -> 왼쪽 서브트리 -> 오른쪽 서브트리
	if (node == nullptr)
		return;

	cout << node->key << endl;
	Print_Inorder(node->left);
	Print_Inorder(node->right);


	// 중위 순회(inorder)
	// 후위 순회(postorder)

}

(1-1) Print

Print 함수는 출력할 노드와 커서의 좌표를 받는다. 위에 제시된 좌표는 트리가 예쁘게 보이는 좌표의 예시이다.

 

(1-2) Print_Inorder(전위 순회 ; Preorder Traverse)

Print_Inorder 함수는 노드의 값을 출력하는 함수이다.

입력된 노드 -> 노드의 좌측 서브 트리 -> 노드의 우측 서브 트리 순서로 순회한다.

 

중위 순회 : 노드의 좌측 서브 트리 -> 입력된 노드 -> 노드의 우측 서브 트리 순서로 순회한다.

후위 순회 : 노드의 좌측 서브 트리 -> 노드의 우측 서브 트리 -> 입력된 노드

 

(2) 탐색 함수(Search, Min, Max, Next)

(2-1) Search

Node* BinarySearchTree::Search(Node* node, int key)
{
	if (node == nullptr || key == node->key)
		return node;

	// 재귀 함수 구조
	if (key < node->key)
		return Search(node->left, key);
	else
		return Search(node->right, key);

}

탐색을 시작할 노드와 값을 입력받고 트리를 탐색하는 함수이다. 노드가 nullptr 이거나 입력받은 node의 key를 값으로 넘겼다면 node를 반환하여 함수를 끝낸다.

재귀 함수 구조와 이진 트리의 특성(작은 값이 왼쪽 자식으로 온다)을 이용하여 입력된 값이 시작 노드의 값보다 작으면 왼쪽으로 탐색을 시작하고, 크면 오른쪽으로 탐색을 시작한다.

 

(2-2) Min

Node* BinarySearchTree::Min(Node* node)
{ // 왼쪽에 있는 노드가 더 작다, nullptr까지
	while (node->left)
		node = node->left;

	return node;
}

노드의 최소값을 찾기 위해서 이진 트리의 특성(작은 값이 왼쪽 자식으로 온다)을 이용한다.

트리의 좌측 끝에 도달(노드의 왼쪽 자식이 nullptr)할 때 까지 노드의 왼쪽 자식을 계속 탐색한다.

 

(2-3) Max

Node* BinarySearchTree::Max(Node* node)
{ // 오른쪽에 있는 노드가 더 크다, nullptr까지
	while (node->right)
		node = node->right;

	return node;
}

노드의 최댓값을 찾기 위해서 이진 트리의 특성(큰 값이 오른쪽 자식으로 온다)을 이용한다.

트리의 우측 끝에 도달(노드의 오른쪽 자식이 nullptr)할 때 까지 노드의 오른쪽 자식을 계속 탐색한다.

 

(2-4) Next (Delete 구현을 위한 함수)

Node* BinarySearchTree::Next(Node* node)
{ // 이 노드 다음으로 큰 노드
	if (node->right) // 서브 노드의 최소값
		return Min(node->right);

	Node* parent = node->parent;

	// 부모가 유효하고 이 노드가 부모의 우측에 있다면
	while (parent && node == parent->right)
	{	// 위로 역행하며 올라감
		node = parent; // 이 노드의 부모로 올라감
		parent = parent->parent; // 부모의 부모를 parent로 설정
	}

	return parent;
}

입력된 노드 다음으로 큰 노드를 찾기위한 함수이다.

 

(2-4-1) 오른쪽 탐색

입력된 노드가 오른쪽 서브 트리를 가지고 있다면(node->right가 NULL이 아니면), 다음 노드는 그 서브 트리에서 최소값인 노드이다. Min 함수를 호출하여 최소값을 찾는다.

 

(2-4-2) 왼쪽 탐색

입력된 노드가 오른쪽 서브 트리를 가지고 있지 않다면, 트리를 거슬러 올라가며 탐색한다.

왼쪽 서브트리에서 입력된 오른쪽 leaf 노드는 항상 부모보다 크므로, 결국 root가 노드 다음으로 큰 값이다.

부모 노드가 있으며 부모의 오른쪽 자식이면 계속 진행한다.

 

(3) 교체 함수(Replace)

void BinarySearchTree::Replace(Node* u, Node* v)
{	// 부모에서 자식으로 연결하기
	if (u->parent == nullptr) // null이면 루트 노드
		_root = v;
	else if (u == u->parent->left) // 이 노드가 부모 좌측에 위치
		u->parent->left = v;
	else
		u->parent->right = v;

	if (v) // 자식에서 부모로 연결하기
		v->parent = u->parent;

	delete u;
}

Delete 함수를 구현하기 위한 Repace 함수이다.

u 노드와 v 노드를 입력받아 u 서브트리를 v 서브트리로 교체한다. 이후에 u 서브트리를 메모리 할당 해제하는 역할도 수행한다.

u 노드의 부모가 존재하지 않다면 u 노드는 루트 노드라는 뜻이므로, v 노드로 덮어 씌우기만 하면 된다.

u 노드가 부모의 좌측에 위치하고 있다면 u 노드의 부모 노드의 좌측을 v와 연결한다. 그렇지 않다면 오른쪽을 v와 연결한다.

그리고 v 노드가 유효하다면(nullptr이 아니라면) v의 부모 또한 u의 부모로 대체시켜준다.

 

(4) 삽입, 삭제 함수(Insert, Delete)

(4-1) Insert (노드를 삽입하는 함수)

void BinarySearchTree::Insert(int key)
{
	Node* newNode = new Node();
	newNode->key = key;

	if (_root == nullptr)
	{
		_root = newNode;
		return;
	}

	Node* node = _root;
	Node* parent = nullptr;

	while (node)
	{
		parent = node; // 초기화
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}
	// 부모의 왼쪽 or 오른쪽에 붙임
	newNode->parent = parent;

	if (key < parent->key)
		parent->left = newNode;
	else
		parent->right = newNode;
}

입력된 값을 가지는 노드를 생성하는 함수이다.

동적 할당으로 새로운 노드를 만들고 값을 저장한다. 이후에 Delete로 인해서 root 노드가 없다면 추가된 노드를 root로 옮겨준다.

이어서 추가된 노드의 부모를 추적하기 위하여 루트 노드를 node로 지정하고 부모를 자기 자신으로 지정한다.

반복문을 이용하여 입력된 값과 루트 노드의 값을 비교하여 node에 루트 노드의 자식을 대입한다.

(루트에서부터 한 칸씩 내려가면서 newNode의 부모를 추적한다)

node가 null인 지점을 찾았다면 그 곳이 newNode의 추가될 위치이다. newNode의 부모는 바로 이전에 탐색한 node이다.

부모 노드의 값과 비교하여 왼쪽 또는 오른쪽에 연결한다.

 

(4-2) Delete (삭제 함수)

void BinarySearchTree::Delete(int key)
{
	Node* deleteNode = Search(_root, key);
	Delete(deleteNode);
}

void BinarySearchTree::Delete(Node* node)
{
	if (node == nullptr)
		return;

	if (node->left == nullptr) // 자식이 우측에 하나거나 없음
		Replace(node, node->right);
	else if (node->right == nullptr) // 자식이 좌측에 하나거나 없음
		Replace(node, node->left);
	else
	{ // 다음 데이터 찾기
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}

입력된 값을 가지는 노드를 제거하는 함수는 Search 함수를 이용하여 찾고, 오버로딩된 Delete 함수로 제거할 수 있다.

노드를 입력 값으로 가지는 Delete 함수에서 먼저 null check를 해준다.

이후에 제거할 노드(u)의 자식을 체크하고 자식이 있다면 자식과 제거할 노드의 위치를 서로 바꿔준다.

Replace 함수를 통해서 제거할 노드(u)의 부모의 좌측 자식(u->parent->left) 혹은 우측 자식(u->parent->right)이 제거할 노드(u)의 자식(v)가 된다.

만약에 제거할 노드(u)가 좌측 자식과 우측 자식 모두 가지고 있다면 제거할 노드(u) 다음으로 큰 노드(next, u의 우측 자식)을 제거할 노드(u)와 바꿔준다.