Binary search tree(BST)는 이진 트리의 일종으로, 모든 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드는 현재 노드보다 작은 값을, 오른쪽 자식 노드는 현재 노드보다 큰 값을 가지는 트리 자료구조이다. 이러한 특성으로 인해 탐색, 삽입, 삭제 등의 연산에 효율적으로 사용될 수 있다.
BST의 주요 특징은 다음과 같다.
하지만 BST의 단점도 존재한다.
BST는 주로 데이터를 정렬하거나, 탐색과 관련된 문제를 해결하는데 활용된다. 예를 들어, 디스크나 메모리 같은 저장장치에 데이터를 저장하고, 이를 검색하는 파일 시스템이나 데이터베이스 시스템에서 사용된다. 또한, 중위 순회(Inorder Traversal)를 사용해 정렬된 상태로 데이터를 출력할 수 있어 유용하게 활용된다.
BST Implementation Code
#include <iostream>
#include <queue>
using namespace std;
template<class K, class E>
struct Node{
Node(K ky, E el, Node<K, E> *left=0, Node<K, E> *right = 0)
: key(ky), element(el), leftChild(left), rightChild(right){}
Node<K,E> *leftChild;
K key;
E element;
Node<K, E> *rightChild;
int leftSize;
};
template<class K, class E>
class BST{
public:
BST(){root = 0;}
void Insert(K &newkey, E &el){Insert(root, newkey, el);}
void Preorder() {Preorder(root);}
void Inorder() {Inorder(root);}
void Postorder() {Postorder(root);}
void Levelorder();
bool Get(const K&, E&);
bool Print();
bool RankGet(int r, K &k, E &e);
void Delete(K &oldkey){Delete(root, oldkey);}
void ThreeWayJoin(BST<K, E>& small, K midkey, E midel, BST<K, E>& big);
void TwoWayJoin(BST<K, E>& small, BST<K, E>& big);
private: //helper 함수들
void Visit(Node<K, E> *);
void Insert(Node<K, E>* &, K &, E &);
void Preorder(Node<K, E> *);
void Inorder(Node<K, E> *);
void Postorder(Node<K, E> *);
void Delete(Node<K, E>* &, K &);
Node<K, E> *root;
};
template <class K, class E>
void BST<K, E>::Insert(Node<K, E>* &ptr, K &newkey, E &el){//Insert의 helpler 함수
if(ptr==0) {ptr = new Node<K, E>(newkey, el); ptr->leftSize = 1;}//아무것도 없으면
else if(newkey < ptr->key) {ptr->leftSize++; Insert(ptr->leftChild, newkey, el);}
else if(newkey > ptr->key) Insert(ptr->rightChild, newkey, el);
else if(newkey == ptr->key) ptr->element = el;//같은 key가 있으면
else ptr->element = el;//Update element
}
template <class K, class E>
void BST<K, E>::Delete(Node<K, E>* &ptr, K &oldkey){
Node<K, E>*tmpptr; Node<K, E> *tmpdaddyptr;
if(ptr == 0) return;//그런 노드가 없으면 그냥 return
if(oldkey < ptr->key) Delete(ptr->leftChild, oldkey);
else if(oldkey>ptr->key){//우측 아들을 루트로 하는 트리에서 지우시오
Delete(ptr->rightChild, oldkey);
}
else{//ptr노드가 바로 지울 노드인 경우임
if(!ptr->leftChild && !ptr->rightChild)//아들이 없다면
{delete ptr; ptr = 0; return;}
else if(ptr->leftChild && !ptr->rightChild)
//그 아들을 ptr가 가리키게 하고 현재 ptr가 가리키는 노드 지움
{ tmpptr = ptr; ptr = ptr->leftChild; delete tmpptr; return;}
else if(ptr->rightChild && !ptr->leftChild)
{ tmpptr = ptr; ptr = ptr->rightChild; delete tmpptr; return;}
else{//두 아들있음:루트가 rc인 우측트리에서 '제일 작은 노드'찾자
Node<K, E> *rc = ptr->rightChild;//rc가 루트인 subtree
if(!rc->leftChild)//rc가 왼쪽아들이 없으면 rc가 그 노드!
{ptr->key = rc->key; ptr->element = rc->element;
ptr->leftChild = rc->rightChild; delete rc;
}
else{
while(rc->leftChild){
rc = rc->leftChild;
}
ptr->key = rc->key; ptr->element = rc->element;
ptr->leftChild = rc->rightChild; delete rc;
}
}
}
}
트리 자료구조에서 노드를 탐색하는 방법 중 세 가지인 전위 순회(pre-order traversal), 중위 순회(in-order traversal), 후위 순회(post-order traversal)에 대해 간단하게 설명해보겠습니다.
template <class K, class E>
void BST<K, E>::Preorder(Node<K, E> *currentNode){//Preorder의 helper 함수
if(currentNode){
Visit(currentNode);
Preorder(currentNode->leftChild);
Preorder(currentNode->rightChild);
}
}
template <class K, class E>
void BST<K, E>::Postorder(Node<K, E> *currentNode){
if(currentNode){
Postorder(currentNode->leftChild);
Postorder(currentNode->rightChild);
Visit(currentNode);
}
}
template <class K, class E>
void BST<K, E>::Inorder(Node<K, E> *currentNode){
if(currentNode){
Inorder(currentNode->leftChild);
Visit(currentNode);
Inorder(currentNode->rightChild);
}
}