[알고리즘] 이진탐색트리 BST(Binary Search Tree)

이진탐색트리 (Binary Search Tree)

BST - https://noguen.com/54

이진탐색트리는 이진탐색의 특징인 정렬된 데이터를 기반으로 빠른 탐색 을 장점으로 가지고 있는 트리구조입니다.

• 각 노드는 2개의 자식을 가질 수 있다.
• 왼쪽 서브트리에는 항상 해당 노드보다 작은 값을 가지고 있다.
• 오른쪽 서브트리에는 항상 해당 노드보다 큰 값을 가지고 있다.
• 중복된 값을 허용하지 않는다.
• 조회 시 평균적으로 O(log N)의 시간 복잡도를 가질 수 있다.
  • 정렬이 균형잡혀있지 않은 경우(최악) O(N)의 시간복잡도를 가지고 있다. 
• C++ : set, multiset, map, multimap 등이 내부적으로 이진 탐색중 하나인 R-BT로 구현되어있다.

 

탐색 수행 과정

1. 데이터의 중앙 요소를 고른다.
2. 중앙값과 목표값을 비교한다.
3. 목표값 < 중앙값이면 중앙을 기준으로 왼쪽, 목표값 > 중앙값이면 중앙을 기준으로 오른쪽으로 이진 탐색을 수행한다.
4. 찾는 값이 나올때까지 1~3단계를 반복한다.
5. 찾는값이 나오지 않는다면 null을 반환한다.

 

삽입 수행 과정

• 루트 노드의 값과 삽입 노드의 값을 비교한다.
• 삽입값 < 루트값이면 왼쪽, 삽입값 > 루트값이면 오른쪽 서브트리로 이동한다.
• 리프 노드에 도달한 후 삽입값과 리프 노드값을 비교하여 왼쪽 또는 오른쪽에 삽입한다.

 

 

삭제 수행 과정

1. 삭제할 노드가 리프노드일 경우
   1. 해당 리프노드를 삭제한다.
2. 삭제할 노드에 자식이 하나 있는 경우
   1. 해당 노드를 삭제한다.
   2. 해당 노드의 부모 노드와 자식 노드를 연결한다.
3. 삭제할 노드에 자식이 둘 있는 경우
   1. 삭제할 노드를 찾는다.
   2. 삭제할 노드의 successor 노드를 찾는다
      1. succesor : 오른쪽 서브트리의 최소값.
   3. 삭제할 노드와 successor 노드의 값을 바꾼다.
   4. 바뀐 successor 노드를 삭제한다.

 

구현

BinarySearchTree.h

struct Node {
	int data;
	Node* left;
	Node* right;

	Node(int value) : data(value), left(nullptr), right(nullptr) {}
};
class BinarySearchTree
{
public:
	BinarySearchTree() : root(nullptr) {}

	void insert(int value);
	bool search(int value);
	void remove(int value);
	void inorderTraversal() const;
	int inorderTraversal(int value) const;

private:
	Node* root;

	Node* insertNode(Node* node, int value);
	bool searchNode(Node* node, int value);
	Node* removeNode(Node* node, int value);
	Node* findMin(Node* node);
	void inorder(Node* node) const;
	int inorder(Node* node, int value) const;

};

 

 

BinarySearchTree.cpp

void BinarySearchTree::insert(int value)
{
	root = insertNode(root, value);
}

bool BinarySearchTree::search(int value)
{
	return searchNode(root, value);
}

void BinarySearchTree::remove(int value)
{
	root = removeNode(root, value);
}

void BinarySearchTree::inorderTraversal() const
{
	inorder(root);
}

int BinarySearchTree::inorderTraversal(int value) const
{
	return inorder(root, value);
}

Node* BinarySearchTree::insertNode(Node* node, int value)
{
	if (node == nullptr) {
		return new Node(value);
	}

	if (value < node->data){
		node->left = insertNode(node->left, value);
	}
	else if (value > node->data) {
		node->right = insertNode(node->right, value);
	}


	return node;
}

bool BinarySearchTree::searchNode(Node* node, int value)
{
	if (node == nullptr){
		return false;
	}
	if (value == node->data){
		return true;
	}
	if (value < node->data){
		return searchNode(node->left, value);
	}
	else {
		return searchNode(node->right, value);
	}
}

Node* BinarySearchTree::removeNode(Node* node, int value)
{
	if (node == nullptr) {
		return nullptr;
	}


	if (value < node->data) {
		node->left = removeNode(node->left, value);
	}
	else if (value > node->data) {
		node->right = removeNode(node->right, value);
	}
	else {
		if (node->left == nullptr) {
			Node* temp = node->right;
			delete node;
			return temp;
		}
		else if (node->right == nullptr) {
			Node* temp = node->left;
			delete node;
			return temp;
		}

		Node* minNode = findMin(node->right);
		node->data = minNode->data;
		node->right = removeNode(node->right, minNode->data);
	}

	return node;
}

Node* BinarySearchTree::findMin(Node* node)
{
	while (node->left != nullptr) {
		node = node->left;
	}
	return node;
}

void BinarySearchTree::inorder(Node* node) const
{
	if (node == nullptr) {
		return;
	}
	inorder(node->left);
	std::cout << node->data << " ";
	inorder(node->right);
}

int BinarySearchTree::inorder(Node* node, int value) const
{
	if (node == nullptr) {
		std::cout << "Node Data : Can't Found." << std::endl;
		return NULL;
	}
	if (value < node->data) {
		inorder(node->left, value);
	}
	else if (value > node->data) {
		inorder(node->right, value);
	}

	if (value == node->data) {
		std::cout << "Node Data : " << node->data << std::endl;
	}
	return node->data;
}