[C++] Binary Search Tree

  Binary Search Tree(이진 검색 트리)는 널리 사용되는 형태의 이진 트리이다. 

 

부모 노드와 자식 노드 간의 관계는 아래와 같다.

 

왼쪽 노드 <= 부모 노드 <= 오른쪽 노드

 

즉, 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 된다. 

 

따라서 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어든다. 

 

다시 말해, BST가 마지막 레벨을 제외한 모든 노드에서 2개의 자식 노드를 가지고 있는 경우에 트리의 높이는 Log2N, 검색 및 삽입의 경우 logN의 시간 복잡도를 가질 수 있다는 것이다.

 

형태를 그림으로 나타내면 아래와 같다.

 

---

BST에서 원소의 검색

위 트리에서 숫자 7을 검색하려면, 아래 그림과 같이 4번의 이동만 하면 된다.

---

BST에서 원소의 삽입

마찬가지로 원소의 삽입 또한 동일하게 각 노드를 확인하면서 새로운 원소가 들어갈 자리를 찾는다.

 

18을 예제 트리에 넣어보면, 아래와 같이 삽입할 수 있다.

---

BST에서 원소의 삭제

원소를 삭제하는 과정은 단순히 해당 노드를 삭제하는 것으로 끝나는 것이 아니라, 노드 삭제 후 전체 트리가 다시 한번 BST 속성을 만족하도록 다른 적절한 노드로 삭제한 노드를 대체해야 하기 때문에 삽입이나 검색보다는 조금 더 복잡하다.

 

삭제의 첫 번째 단계는 삭제할 노드를 찾는 것이다.

 

그 후에는 아래의 3가지 경우를 따져봐야 한다.

 

- 자식 노드가 없는 경우: 단순히 해당 노드를 삭제

- 자식 노드가 하나만 있는 경우: 노드 삭제 후, 부모 노드의 포인터가 해당 자식 노드를 가리키도록 조정한다.

- 자식 노드가 두 개가 있는 경우: 노드 삭제 후, 현재 노드를 후속 노드로 대체한다. 이때, 후속 노드란 현재 노드 다음으로 큰 숫자를 가진 노드를 말한다. 

 

즉, 후속 노드는 삭제 대상 노드보다 큰 원소들 중 가장 작은 값의 노드를 찾으면 된다.

 

후속 노드를 찾은 뒤에는 삭제 대상 노드의 위치에 후속 노드를 위치 시킨다.

 

이를 그림으로 나타내면 아래와 같다.

 

1. 원소 삭제

 

2. 후속 노드 찾기

위와 같이 삭제된 12의 자식 노드인 10과 20 사이에 들어갈 노드 중, 가장 작은 노드를 찾아서 넣어야 BST 속성을 만족한다.

 

3. 대체하기

---

이제, 직접 한번 코드로 구현해보자.

#include <iostream>

using namespace std;

struct node {
	int data;
	node* left;
	node* right;
};

struct bst {
	node* root = nullptr;

public:
	node* find(int value) {
		return find_impl(root, value);
	}

	void insert(int value) {
		if(!root) root= new node{value, NULL, NULL};
		else insert_impl(root, value);
	}

	void inorder() {
		inorder_impl(root);
	}

	void deleteValue(int value) {
		root = delete_impl(root, value);
	}

	/* 후속 노드 찾기 */
	node* successor(node* start) {
		/* 삭제 대상 노드의 오른쪽 노드에서 검색 시작 */
		auto current = start->right;

		/* 왼쪽 노드(값이 작은 노드)가 없을 때까지 검색 */
		while(current && current->left)
			current = current->left;

		/* 가장 작은 노드 반환 */
		return current;
	}

private:
	/* 원소 검색/삽입은 재귀적으로 동작하기 때문에 실제 구현을 impl에서 하고, private으로 지정하여 외부에서 직접 호출을 막는다. */
	node* find_impl(node* current, int value) {
		if(!current) {
			cout << endl;
			return NULL;
		}

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

		if(current->data > value) {
			cout << current->data <<"에서 왼쪽으로 이동" << endl;
			return find_impl(current->left, value);
		}

		cout << current->data << "에서 오른쪽으로 이동" << endl;
		return find_impl(current->right, value);
	}

	void insert_impl(node* current, int value) {
		if(value < current->data) {
			if(!current->left)current->left = new node{value, NULL, NULL};
			else insert_impl(current->left, value);
		} else {
			if(!current->right) current->right = new node{value, NULL, NULL};
			else insert_impl(current->right, value);
		}
	}

	void inorder_impl(node* start) {
		if(!start) return;
		inorder_impl(start->left);
		cout<<start->data<<" ";
		inorder_impl(start->right);
	}

	node* delete_impl(node* start, int value) {
		if(!start) return NULL;

		if(value < start->data)
			start->left = delete_impl(start->left, value);
		else if(value > start->data)
			start->right = delete_impl(start->right, value);
		else {
			/* 자식 노드가 전혀 없거나, 왼쪽 자식 노드만 없는 경우 */
			if(!start->left) {
				auto tmp = start->right;
				delete start;
				return tmp;
			}

			/* 오른쪽 자식 노드만 없는 경우 */
			if(!start->right) {
				auto tmp = start->left;
				delete start;
				return tmp;
			}

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

			/* 오른쪽 서브 트리에서 후속 노드를 찾아 삭제 */
			start->right = delete_impl(start->right, succNode->data);
		}

		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(9);
	tree.insert(14);
	tree.insert(17);
	tree.insert(30);
	tree.insert(7);
	tree.insert(2);

	cout << "중위 순회: ";
	tree.inorder();
	cout << endl;

	tree.deleteValue(12);
	cout << "12를 삭제한 후 중위 순회: ";
	tree.inorder();
	cout << endl;

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

 

 

output:

 

중위 순회: 2 4 7 8 9 10 11 12 14 15 17 20 28 30
12를 삭제한 후 중위 순회: 2 4 7 8 9 10 11 14 15 17 20 28 30
14에서 왼쪽으로 이동
10에서 오른쪽으로 이동
11에서 오른쪽으로 이동

원소 12는 트리에 없습니다.