C++ 이진탐색트리(Binary Search Tree) 구현 및 설명
Binary Search Tre
이번 포스팅에서는 이진 탐색 트리(Binary Search Tree) 에 대해 알아보겠습니다. 이 글은 직접 작성했기 때문에 내용에 오류가 있을 수있습니다. 따라서 잘못된 내용이 있거나, 레퍼런스에 관해서 피드백 주실 내용이 있다면 언제든지 댓글 달아주시면 감사하겠습니다.
1. Overview
이진 탐색 트리 는 몇 가지 속성을 만족시키는 이진트리입니다.
1. 각 노드에 값이 존재
2. 값이 중복된 노드가 없음
3. 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값들을 지닌 노드로 구성
4. 반대로 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값들을 지닌 노드로 구성
5. 좌우의 서브트리는 다시 각각 이진 탐색트리여야 함
이런 조건을 만족시키면, 그 트리는 이진 탐색 트리 라 볼 수 있습니다. 아래 이미지로 나와있는 트리도 이진 탐색트리입니다.
이진 탐색트리는 평균적으로 원소의 탐색, 삽입, 삭제에 있어서 O(logn) 의 성능을 보장합니다. 최악의 경우에는, 그러니까 한쪽으로만 치우친 트리에서는 O(n) 의 성능이 나옵니다. 재미있는 사실은, 힙소트처럼, 이진탐색트리도 정렬 알고리즘으로 사용할 수 있다는 점인데요. 이 경우 평균적으로는 O(nlogn) 의 성능을, 최악의 경우에는 O(n^2) 의 성능을 보입니다. 힙소트 와 마찬가지로 Building, Extraction 두 과정으로 이루어지구요. 자세한 내용은 여기를 참고하세요.
2. Implementation
이번 구현도 C++ 을 사용했습니다. Generic 하게 적용할 수 있게 템플릿 클래스 를 사용했고, 데이터간 비교를 위해 람다를 사용했습니다. 자세한 코드는 https://github.com/ansterd/algorithm/tree/master/cpp/binary-search-tree/src 여기를 참조해주세요. 이를테면 사용법은 아래와 같습니다.
#include <iostream>
#include "tree.h"
using namespace std;
int main(int argc, char *argv[])
{
BinarySearchTree<int> bst;
function<int(int&, int&)> comparator = [](int& lhs, int& rhs)->int{
if(lhs > rhs) {
return 1;
} else if (lhs < rhs) {
return -1;
} else {
return 0;
}
};
function<void(int& value)> printer = [](int& value)->void{
std::cout << value << std::endl;
};
bst.insert(3, comparator);
bst.insert(2, comparator);
bst.insert(5, comparator);
bst.insert(4, comparator);
bst.insert(6, comparator);
// std::cout << bst.search(1, comparator) << std::endl;
// bst.insert(1, comparator);
// std::cout << bst.search(1, comparator) << std::endl;
bst.remove(5, comparator);
bst.traverse_pre_order(printer);
return 0;
}Insert
삽입 은 구현이 어렵지 않습니다. 삽입할 값이 현재 값보다 작으면 좌측으로, 크면 우측으로 이동하다가 비어있는 지점에 삽입하면 되지요. 반복문으로도 쉽고, 재귀로도 쉬워서 어느걸 선택하셔도 됩니다. 아래는 재귀로 구현된 코드입니다. 재귀를 구현하기 위해 파라미터로 Node 를 넘겨주어야 했는데, 이부분을 사용자로부터 가리기 위해 insert 라는 Wrapper 함수 를 작성했습니다. 실제 로직은 internal_insert 에 담겨 있습니다. 코드를 보시지요.
template <typename T>
bool BinarySearchTree<T>::insert(T value, function<int(T&, T&)>& comp) {
return internal_insert(root, value, comp);
}
template <typename T>
bool BinarySearchTree<T>::internal_insert(Node<T>*& current, T value,
function<int(T&, T&)>& comp)
{
// recursive
if (current == nullptr) {
current = new Node<T>(value);
return true;
} else if (comp(current->data, value) == 1) {
// if the variable current is greater than value,
return internal_insert(current->left, value, comp);
} else if (comp(current->data, value) == -1) {
// if the variable current is less than value,
return internal_insert(current->right, value, comp);
}
// duplicated
return false;
}Traverse
이진 트리에서 구현하는 것은, 중위순회(in-order), 전위순회(pre-order), 후위순회(post-order) 를 공부하기 좋은 방법입니다. 아래 코드에서 함수 f 는 cout 라 보셔도 되겠습니다. 그리고 위와 마찬가지로 사용자로부터 재귀함수의 Node 파라미터를 감추기 위해서 Wrapper 함수 를 작성했습니다.
template <typename T>
void BinarySearchTree<T>::traverse_pre_order(function<void(T&)>& printer)
{
// depth-first traversal
internal_traverse_pre_order(root, printer);
}
template <typename T>
void BinarySearchTree<T>::internal_traverse_pre_order(Node<T>* current,
function<void(T&)>& f) {
if (current == nullptr) {
return;
}
f(current->data);
internal_traverse_pre_order(current->left, f);
internal_traverse_pre_order(current->right, f);
}
template <typename T>
void BinarySearchTree<T>::traverse_in_order(function<void(T&)>& printer)
{
// depth-first traversal
internal_traverse_in_order(root, printer);
}
template <typename T>
void BinarySearchTree<T>::internal_traverse_in_order(Node<T>* current,
function<void(T&)>& f) {
if (current == nullptr) {
return;
}
internal_traverse_in_order(current->left, f);
f(current->data);
internal_traverse_in_order(current->right, f);
}
template <typename T>
void BinarySearchTree<T>::traverse_post_order(function<void(T&)>& printer)
{
// depth-first traversal
internal_traverse_post_order(root, printer);
}
template <typename T>
void BinarySearchTree<T>::internal_traverse_post_order(Node<T>* current,
function<void(T&)>& f) {
if (current == nullptr) {
return;
}
internal_traverse_post_order(current->left, f);
internal_traverse_post_order(current->right, f);
f(current->data);
}사실 전위냐, 중위냐, 후위냐, 구현상의 큰 차이는 없습니다. 출력문이 어느 위치에 오느냐 그 차이입니다. 아래 그림에서 출력 결과의 차이를 확인하실 수 있습니다.
Remove
이진 탐색트리에서 구현이 가장 복잡한 부분이 삭제입니다. 크게 3가지 경우로 나눌 수 있습니다.
1. Leaf, 즉 자식이 없는 경우
2. 자식이 하나만 있는 경우
3. 좌측, 우측 자식을 모두 가진 경우
2번은 다시 왼쪽 자식을 가졌느냐, 오른쪽 자식을 가졌느냐로 나뉩니다. 그리고 3번의 경우, 현재 노드를 지우고 그 자리에 채워넣을 값을 찾기 위해 두 가지 방법을 사용할 수 있는데
1. 우측 서브트리에서 Leftmost, 즉 가장 좌측에 있는 값(가장 작은 값)
2. 좌측 서브트리에서 Rightmost, 즉 가장 우측에 있는 값(가장 큰 값)
이 두 가지 방법을 사용할 수 있습니다. 사실 이진 탐색 트리에는 중복 이 없기 때문에, 어느 방법을 사용해도 상관 없습니다. 아래 그림에서는 Rightmost 값을 사용하는걸 보실 수 있습니다.
저의 경우에는 우측 서브트리의 Leftmost 값을 사용했구요. 코드를 보시겠습니다.
template <typename T>
Node<T>*& BinarySearchTree<T>::find_left_most_child(Node<T>*& current) {
while(current->left) {
current = current->left;
}
return current;
}
template <typename T>
void BinarySearchTree<T>::replace_node(Node<T>*& replaced, Node<T>*& newone) {
if (replaced == nullptr || newone == nullptr) {
return;
}
if (replaced->left != nullptr && replaced->right != nullptr) {
newone->left = replaced->left;
if(replaced->right != newone)
newone->right = replaced->right;
}
Node<T>* temp = replaced;
replaced = newone;
delete temp;
return;
}
template <typename T>
bool BinarySearchTree<T>::remove(T value, function<int(T&, T&)>& comp)
{
return internal_remove(root, value, comp);
}
template <typename T>
bool BinarySearchTree<T>::internal_remove(Node<T>*& current, T value,
function<int(T&, T&)>& comp) {
if (comp(current->data, value) == 0) {
if (current->left == nullptr && current->right == nullptr) {
// if leaf node,
delete current;
current = nullptr;
} else if (current->left != nullptr && current->right != nullptr) {
// if has two children
replace_node(current, find_left_most_child(current->right));
} else if (current->left != nullptr && current->right == nullptr) {
// only has a left child;
replace_node(current, current->left);
} else if (current->left == nullptr && current->right != nullptr) {
// only has a right child
replace_node(current, current->right);
}
return true;
} else if (comp(value, current->data) == 1) {
// if the variable value is greater than current node's data
return internal_remove(current->right, value, comp);
} else {
// if the variable value is less than current node's data
return internal_remove(current->left, value, comp);
}
return false;
}Search
이 부분은 사실 별로 설명할 내용이 없어서 코드만 담겠습니다. 함수 comp 는 두 값이 같으면 0 을, 좌측이 크면 1 을, 좌측이 우측보다 작으면 -1 을 돌려주는 함수입니다.
template <typename T>
bool BinarySearchTree<T>::search(T value, function<int(T&, T&)>& comp)
{
Node<T>* current = root;
while (current) {
if (comp(current->data, value) == 0) {
return true;
} else if (comp(value, current->data) == 1) {
current = current->right;
} else {
current = current->left;
}
}
return false;
}3. Summary
이진 탐색트리는 최악의 경우에 언급했듯이 O(n) 의 삽입, 삭제, 검색 성능을 보여줍니다. 따라서 구조에 좀 더 제약을 가하고, 삽입과 삭제, 검색 성능을 더 이끌어 낼 수 있는 Advanced 한 탐색 트리가 몇개 더 있습니다. *AVL Tree 같은 것들인데, 다음시간에 다루겠습니다.
