[자료구조] BST(Binary Search Tree, 이진탐색트리)

BST

 - 이진탐색과 연결 리스트를 결합한 자료구조이다.

 - 트리형태이며 하나의 노드는 left, value, right를 가진다.

 - value는 unique이다.

 - 어떤 노드를 기준으로 왼쪽노드의 value는 더 작은 값이 들어간다

 - 어떤 노드를 기준으로 오른쪽노드의 value는 더 큰 값이 들어간다

 - 루트 노드를 기준으로 왼쪽의 노드들의 value는 루트 노드의 value보다 작다.

 - 루트 노드를 기준으로 오른쪽의 노드들의 value는 루트 노드의 value보다 크다.

 - 현재 노드를 기준으로 큰 값은 오른쪽 작은 값은 왼쪽에 있으므로 time complexity는 O(logn)이다

2진 탐색 트리 예시

1. 삽입 알고리즘

 - root node부터 검색하여 큰값이면 오른쪽 작은값이면 왼쪽으로 위치시킬 수 있도록 한다.

2. 삭제 알고리즘

 - child node가 없을 경우

    -> parent 노드의 링크를 제거

 - child node가 1개 있을 경우

    -> parent 노드의 링크를 child node와 연결

 - child node가 2개 있을 경우 

   -> 현재 node를 기준으로 왼쪽 node의 가장 큰 값을 지울 node의 자리로 올 수 있도록 자리를 옮긴다.

 

c++ 풀이

template<typename T>
struct Node {
	Node* left;
	Node* rigth;
	T value;
};

template<typename T>
class BST{
public:
	BST() {};
	~BST() {};
	void addNode(T _value);
	void removeNode(T _value);
	void print();
	bool searchNode(T _value);
private:
	Node<T>* root;
	Node<T> tail;

	void Inorder(Node<T>* current) {
		if (current != nullptr) {
			Inorder(current->left);
			cout << current->value << " ";
			Inorder(current->rigth);
		}
	}
	Node<T>* searchMaxNode(Node<T>* node) {
		if (node == nullptr) {
			return nullptr;
		}
		while (node->rigth != nullptr) {
			node = node->rigth;
		}
		return node;
	}
	Node<T>* searchMinNode(Node<T>* node) {
		if (node == nullptr) {
			return nullptr;
		}
		while (node->left != nullptr) {
			node = node->left;
		}
		return node;
	}
	Node<T>* removeConnect(Node<T>* node, T _value) {
		if (node == nullptr) return node;
		else if (node->value > _value) node->left = removeConnect(node->left, _value);
		else if (node->value < _value) node->rigth = removeConnect(node->rigth, _value);
		else {
			//삭제 알고리즘의 3가지 상황
			//1. no chlid
			//2. one child
			//3. 2 child
			Node<T>* ptr = node;
			if (node->rigth == nullptr && node->left == nullptr) {
				delete node;
				node = nullptr;
			}
			else if (node->rigth == nullptr) {
				node = node->left;
				delete ptr;
			}
			else if (node->left == nullptr) {
				node = node->rigth;
				delete ptr;
			}
			else {
				ptr = searchMaxNode(node->left);
				node->value = ptr->value;
				node->left = removeConnect(node->left, ptr->value);
			}
		}
		return node;
	}
};

template<typename T>
void BST<T>::addNode(T _value){
	if (searchNode(_value)) return;

	Node<T>* node = new Node<T>();
	Node<T>* tmp = nullptr;

	node->value = _value;
	if (root == nullptr) root = node;
	else {
		Node<T>* ptr = root;
		while (ptr != nullptr) {
			tmp = ptr;
			if (node->value < ptr->value) ptr = ptr->left;
			else ptr = ptr->rigth;
		}
		if (node->value < tmp->value) tmp->left = node;
		else tmp->rigth = node;
	}

	
}

template<typename T>
void BST<T>::removeNode(T _value){
	removeConnect(root, _value);
}

template<typename T>
void BST<T>::print(){
	Inorder(root);
}

template<typename T>
bool BST<T>::searchNode(T _value){
	Node<T>* ptr = root;
	Node<T>* tmp = nullptr;

	while (ptr != nullptr) {
		if (ptr->value == _value) return true;
		else if (ptr->value > _value) ptr = ptr->left;
		else ptr = ptr->rigth;
	}

	return false;
}