이진 검색 트리(BTS, Binary Search Tree)

이진 검색 트리는 일반적인 이진 트리와 같이 하나의 부모 노드에 최대  두개의 자식 노드를 가지는 트리이다.

일반적인 이진 트리와 다른 점은 왼쪽 자식 노드의 값은 부모 노드의 값보다 작거나 같고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 크거나 같다.

 

이러한 구조 덕분에 부모 노드보다 작은 원소는 항상 왼쪽에 위치하고, 큰 노드는 오른쪽에 위치한다. 따라서 원소를 검색 할 때 한 단계마다 이론적으로 검색 범위가 절반으로 줄게 된다.

 

#include <iostream>

struct node{
	int value;
	node* first;
	node* second;
};

struct bst {
	node* root = nullptr;

	node* find(int input) {
		return find_impl(root, input);
	}

private:
	node* find_impl(node* current, int input) {
		if (!current) {
			std::cout << std::endl;
			return NULL;
		}

		if (current->value == input) {
			std::cout << input << "을 찾았습니다." << std::endl;
			return current;
		}

		if (input < current->value) {
			std::cout << current->value << "에서 왼쪽으로 이동: ";
			return find_impl(current->first, input);
		}

		std::cout << current->value << "에서 오른쪽으로 이동: ";
		return find_impl(current->second, input);
	}

	// 노드 삽입 함수
public:
	void insert(int input) {
		if (!root)
			root = new node{ input, NULL, NULL };
		else
			insert_impl(root, input);
	}

private:
	void insert_impl(node* current, int input) {
		if (input < current->value) {
			if (!current->first)
				current->first = new node{ input, NULL, NULL };
			else
				insert_impl(current->first, input);
		}
		else {
			if (!current->second)
				current->second = new node{ input, NULL, NULL };
			else
				insert_impl(current->second, input);
		}
	}

	// 중위 순회 함수
public:
	void inorder() {
		inorder_impl(root);
	}

private:
	void inorder_impl(node* start) {
		if (!start)
			return;

		inorder_impl(start->first);
		std::cout << start->value << " ";
		inorder_impl(start->second);
	}

	// 후손 노드를 찾는 함수
public:
	node* successor(node* start) {
		auto current = start->second;		// 오른쪽으로 한번 이동
		while (current && current->first)	// 오른쪽 서브트리에서 가장 작은(가장 왼쪽인) 값으로 이동
			current = current->first;
		return current;
	}

	// 원소 삭제
public:
	void deleteValue(int input) {
		root = delete_impl(root, input);
	}

private:
	node* delete_impl(node* start, int input) {
		if (!start)
			return NULL;

		if (input < start->value)
			start->first = delete_impl(start->first, input);
		else if (input > start->value)
			start->second = delete_impl(start->second, input);
		else {
			if (!start->first) {
				auto tmp = start->second;
				delete start;
				return tmp;
			}

			if (!start->second) {
				auto tmp = start->first;
				delete start;
				return tmp;
			}

			// 자식 노드가 둘 다 있는 경우
			auto succNode = successor(start);
			start->value = succNode->value;

			// 오른쪽 서브 트리에서 후속을 찾아 삭제
			start->second = delete_impl(start->second, succNode->value);
		}

		return start;
	}
};

int main()
{
	bst tree;
	tree.insert(12);
	tree.insert(10);
	tree.insert(20);
	tree.insert(8);
	tree.insert(11);
	tree.insert(15);
	tree.insert(28);
	tree.insert(4);
	tree.insert(2);

	std::cout << "중위 순회: ";
	tree.inorder(); // BST의 모든 원소를 오름차순으로 출력합니다.
	std::cout << std::endl;

	tree.deleteValue(12);
	std::cout << "12를 삭제한 후 중위 순회: ";
	tree.inorder(); // BST의 모든 원소를 오름차순으로 출력합니다.
	std::cout << std::endl;

	if (tree.find(12))
		std::cout << "원소 12는 트리에 있습니다." << std::endl;
	else
		std::cout << "원소 12는 트리에 없습니다." << std::endl;

}