(C/C++) 검색 - 이진 트리 탐색 (Binary Tree Search)

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

1. 이진 트리 탐색 (이진 탐색 트리) (Binary Tree Search)

이진 트리를 사용하는 검색 방법 입니다.

이진 트리 자체가 매우 효율적인 검색 방법입니다.

자료형이 많이 늘어도 검색 횟수가 크게 늘지 않습니다.

 

2. 구현 방법

키값은 고유하며, 자식 < 부모 < 오른쪽 이라는 공식이 성립해야합니다.

검색은 찾는 값이 같으면 반환, 노드보다 작으면 왼쪽, 크면 오른쪽으로 이동하며 키값을 찾습니다.

삽입은 검색과 마찬가지로 찾는 값이 같으면 실패(키값은 고유하다.),

노드보다 작으면 왼쪽, 크면 오른쪽으로 이동하며 삽입 위치를 찾습니다.

삭제는 조금 복잡합니다. 이진트리 삭제의 경우 크게 3가지 경우로 나뉩니다.

자식이 하나도 없는 경우, 자식이 하나만 있는 경우, 자식이 둘 있는 경우

자식이 없는 경우 지우면 되고, 하나만 있는 경우 지우고 자식 노드를 부모노드에 연결하고 지우면 됩니다.

자식이 둘 있는 경우 왼쪽자식 노드 중에서 가장 큰 노드 혹은

오른쪽 자식 중에서 가장 작은 노드가 삭제할 노드의 위치를 대신해야합니다.

저는 오른쪽 자식중에서 가장 작은 자식을 삭제할 노드의 위치에 넣었습니다.

 

3. 링크드리스트를 이용한 이진 트리 탐색 구현

#pragma once
#include <iostream>

struct Data
{
	int key;
	int phone;
};

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

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

	void Traverse(Node* node);
public:
	BinaryTreeList();

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

	void PrintAll();
};

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

링크드 리스트를 사용하기에 Node 구조체를 선언해 주었습니다.

#include "BinaryTreeList.h"

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

bool BinaryTreeList::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 BinaryTreeList::Insert(Data data)
{
	Node* parentNode = &root;
	Node* currentNode = root.left;
	bool isLeft = true;
	while (currentNode != nullptr)		//(왼쪽 혹은 오른쪽 자식이 비어있는)부모 노드를 찾는 과정
	{
		if (data.key == currentNode->data.key)
			return false;

		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;

	return true;

}

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

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

		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;
		return true;
	}
	return false;
}

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

void BinaryTreeList::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;
}

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

삭제할 노드가 맨처음노드일 경우를 대비해 루트노드를 더미로 사용합니다. 처음 데이터는 root.left 부터 저장됩니다.

지울 노드가 있으면 그 노드의 자식이 둘 인지 하나인지 없는지 판단합니다.

자식이 하나가 있는 경우 지울노드의 부모노드가 그 하나있던 자식 노드를 가르키게 합니다.

자식이 없는 경우 지울노드의 부모노드가 nullptr 을 가르키게 합니다.

( currentNode = deleteNode->left != nullptr ? deleteNode->left : deleteNode->right; ) 

자삭이 둘 있는 경우 지울노드의 오른쪽노드가 가장 작은 값인지 판단합니다.

가장 작은 값이라면 지울노드의 위치로 옮기고(부모노드가 가장 작은 값 노드를 가르키게 합니다.)

가장 작은 값이 아니라면 가장 작은 값 노드는 찾고 기존 연결은 끊고 지울노드 자리로 옮겨 다른 노드와 연결을 합니다.

 

순회는 전방순회로 제일 먼저나오는 값이 루트노드, 루트노드기준 루트노드보다 작으면 왼쪽, 크면 오른쪽에 있습니다.

 

감사합니다.