개요
아래와 같은 특성을 가지는 추상적 자료형(Abstract Data Type)을 생각해봅시다.
- 정렬 가능한 데이터의 집합에서
- 검색, 삽입, 삭제 연산을
- 빠르게 할 수 있다.
여기서 중요한 것이 정렬 가능과 검색 연산입니다. 먼저 정렬 가능성을 언급한 이유는 기본적으로 정렬된 데이터는 이진 탐색으로 빠르게 검색 가능하기 때문입니다. 또 임의의 데이터가 이 집합에 있는지 빠르게 확인할 수 있다는 점에서 위 추상적 자료형은 데이터베이스에 아주 적합한 구조라고 할 수 있습니다. 이걸 어떻게 구현할까요? 단순히 연결 리스트로 구현하면 검색하는 데 $O(n)$만큼 걸릴 것이고, 정렬된 연결 리스트로 구현하더라도 삽입, 삭제는 $O(n)$이 걸릴 겁니다($n$은 원소의 개수). 결국 단순한 리스트로는 구현 못 한다는 거죠.
일단 힙을 생각해봅시다. 힙도 아주 비슷한 성질을 가집니다.
- 정렬 가능한 데이터의 집합에서
- 최솟갓 검색, 삽입, 최솟값 삭제 연산을
- 빠르게 할 수 있다.
이 성질을 가지는 추상적 자료형 역시 단순한 리스트로는 $O(n)$보다 빠르게 구현할 수 없기 때문에 힙 성질을 만족하는 트리를 이용해서 구현하죠. 따라서 빠른 속도를 위해 여기서도 힙과 비슷하게 트리를 사용합니다. 이 트리는 이진 탐색 트리라고 하며, 정의는 다음과 같습니다.
- 이진 트리이다.
- 각 노드는 키(key)를 가진다.
- 어떤 노드 $v$의 왼쪽 서브트리에 있는 모든 노드는 $v$보다 키가 작고, 오른쪽 서브트리에 있는 모든 노드는 $v$보다 키가 크다.
일단 중복을 허용하지 않는다고 가정하겠습니다. (즉, 데이터의 집합에 같은 값은 있을 수 없습니다.) 정의에 따라, 이진 탐색 트리는 아래 성질을 자연히 만족하게 됩니다.
- 제일 왼쪽 노드는 최솟값을 가집니다.
- 제일 오른쪽 노드는 최댓값을 가집니다.
- 이진 탐색 트리를 중위 순회하면 트리가 가지는 모든 키들을 크기 순서대로 늘어놓을 수 있습니다.
아래는 1, 2, 3, 4, 6, 7, 8, 10, 15를 포함하는 이진 탐색 트리의 예입니다. 앞으로의 예시는 이 트리로 들겠습니다.
여기서 NIL은 자식이 없다는 것을 의미하는 가상의 리프 노드입니다. 실제 구현시 NIL을 구현해서 연결시켜주는 경우도 있고, 그냥 자식 노드를 가리키는 포인터를 NULL로 하는 경우도 있습니다.
검색
이진 탐색 트리의 성질에 의해 이분 탐색과 유사하게 검색할 수 있습니다. 트리에서 어떤 값을 찾고자 하면
- 루트에 찾는 값이 있으면 찾는 데 성공입니다.
- 루트의 키보다 찾는 값이 작으면 왼쪽 자식으로 내려갑니다.
- 더 크면 반대로 오른쪽 자식으로 내려갑니다.
만약 NIL에 도달하면 찾는 값이 없는 겁니다. 위 이진 탐색 트리에서 7을 찾는 경우를 예로 들어봅시다.
한편 12를 찾으면 아래와 같이 NIL에 도달하므로 12는 이 트리에 없다고 할 수 있습니다.
검색 연산의 시간 복잡도는 트리의 높이를 $h$라 할 때 $O(h)$입니다.
삽입
새로운 값의 삽입은 항상 NIL의 위치에서만 일어납니다. 먼저 검색을 하고, 이미 있는 값이 아니라면 그렇게 도달한 NIL의 위치에 새로운 값을 집어넣습니다. 12를 추가해봅시다.
이 경우도 역시 시간 복잡도는 $O(h)$입니다.
삭제
노드의 삭제는 상대적으로 복잡합니다. 무턱대고 삭제하다간 이진 탐색 트리가 지켜야 할 성질이 깨지기 때문이죠. 삭제는 크게 세 가지 경우로 나눌 수 있습니다.
자식이 없는 경우
단순히 노드를 지우고 그 자리를 NIL로 대체하면 됩니다.
자식이 하나만 있는 경우
삭제할 노드의 부모와 자식을 서로 이어주면 됩니다. 예를 들어 위 트리에서 15를 삭제한다고 하면 15의 부모인 8을 15의 자식인 10과 연결해주고 15를 삭제합니다.
자식이 둘인 경우
이 경우가 복잡합니다. 먼저 삭제할 키 다음으로 큰 키를 가진 노드를 찾아야 합니다. 4를 삭제하는 경우를 예로 들어 설명하겠습니다. 첫 번째로 4 다음으로 큰 값인 6을 가진 노드를 찾습니다. 그리고 찾은 노드의 키를 삭제할 노드에 복사합니다.
찾은 노드의 키 6은 삭제할 키 4보다 큰 키 중에 제일 작은 키죠. 4보다 큰 키는 4의 오른쪽 서브트리에 모두 모여 있으므로 6은 4의 오른쪽 서브트리에 있는 값 중 최솟값이 됩니다. 또한 4의 왼쪽 서브트리에 있는 값은 4보다 작고, 따라서 당연히 6보다 작습니다. 결과적으로 4가 있던 위치에 6을 넣어도 여전히 이진 탐색 트리의 성질은 깨지지 않습니다. (물론, 중복을 허용하면요.)
그리고 원래 6을 지워줍니다. 이 6은 절대 왼쪽 자식을 가질 수 없습니다. 만약 왼쪽 자식이 있으면, 왼쪽 자식은 6보다 크고(6의 왼쪽 서브트리에 있으므로) 4보다 작기 때문에(4의 오른쪽 서브트리에 있으므로) 4 다음으로 큰 값이 6이라는 가정에 어긋납니다. 고로 자식이 없거나 하나만 있는 경우를 처리하는 방법으로 6을 삭제할 수 있습니다.
4로부터 그 다음으로 큰 값인 6을 찾는 방법은 아래에서 설명하겠습니다. 이 부분 때문에 시간 복잡도는 $O(h)$입니다.
순회
어떤 노드 $v$의 키 바로 다음으로 큰 키를 가진 노드를 $v$의 후임자(successor)라고 합니다. 반대로 $v$를 후임자로 가지는 노드는 $v$의 전임자(predeceessor)입니다.
$v$가 오른쪽 자식을 가지면 후임자는 오른쪽 서브트리에서 가장 왼쪽 노드가 되고, 그렇지 않다면 $v$는 후임자의 왼쪽 서브트리에서 가장 오른쪽 노드인 겁니다. 즉, $v$에서 시작해서 이 노드가 부모의 오른쪽 자식이면 부모로 올라가고, 아니면 그 때의 부모가 후임자죠. 전임자는 반대로 하면 됩니다. 이 과정은 최악의 경우에 루트 노드와 잎새 노드 사이를 이동하므로 시간 복잡도가 $O(h)$입니다.
따라서 최솟값 또는 최댓값에서 시작하여 계속 후임지나 전임자를 찾으면 모든 노드를 크기 순서대로 순회할 수 있습니다. 여기서 각 노드는 최대 2번 방문하므로 전체 순회의 복잡도는 노드 개수를 $n$이라 할 때 $O(n)$입니다.
구현
template<typename KeyType>
class BinarySearchTree {
private:
class Node;
static Node *const NIL;
Node *root, *node_max, *node_min;
size_t size;
public:
class iterator;
BinarySearchTree() : root(NIL), node_max(NIL), node_min(NIL), size(0) {}
~BinarySearchTree() {
if (root != NIL)
delete root;
}
iterator insert(KeyType key);
iterator search(KeyType key);
void remove(KeyType key);
void remove(iterator it);
inline iterator begin(void);
inline iterator end(void);
inline iterator rbegin(void);
inline iterator rend(void);
void print(void);
};
BinarySearchTree 클래스는 private으로 Node
클래스와 public으로 iterator 클래스를 가지고 있습니다. 또 static
멤버 변수로 앞 포스트에서도 설명했던 NIL 노드를 가지고 있고, 그 외에
private으로 root, node_max,
node_min를 가집니다. 각각 루트 노드, 최댓값을 가지는 노드,
최솟값을 가지는 노드를 가리킵니다. 사실 루트 노드만 저장해줘도 트리 구현엔
문제가 없지만 반복자(iterator)를 구현할 때 있으면 좋습니다. size
변수는 이름에서 유추할 수 있듯이 트리 크기를 저장합니다. 메서드로는 삽입,
검색, 삭제 연산을 해줄 insert, search,
remove가 있고 STL에서 흔히 볼 수 있는 메서드 begin,
end, rbegin, rend가 있습니다. 마지막
print는 디버깅용으로, 트리를 출력해줍니다.
일단 NIL 노드를 할당합시다. 덧붙이자면 위 그림에선 NIL 노드를 자식이 없는 노드마다 일일이 따로 그려줬지만, 실제로 NIL 노드를 구현할 경우에는 보통 유일한 NIL 노드가 하나 있고, 자식이 없으면 그 NIL 노드를 가리키게 하는 형태로 구현합니다.
template<typename KeyType>
typename BinarySearchTree<KeyType>::Node *const BinarySearchTree<KeyType>::NIL = new BinarySearchTree<KeyType>::Node();
그 다음 중첩 클래스를 정의합니다.
template<typename KeyType>
class BinarySearchTree<KeyType>::Node {
public:
KeyType key;
Node *left, *right, *parent;
Node() : left(nullptr), right(nullptr), parent(nullptr) {}
Node(KeyType k) : key(k), left(NIL), right(NIL), parent(NIL) {}
~Node() {
if (this->left != NIL)
delete this->left;
if (this->right != NIL)
delete this->right;
}
Node *predecessor(void);
Node *successor(void);
};
Node 클래스는 키와, 왼쪽 자식, 오른쪽 자식, 부모를 가리키는
포인터를 가집니다. 생성자에서는 세 포인터가 NIL 노드를 가리키게 하고,
소멸자에서는 왼쪽 자식과 오른쪽 자식을 해제해주는 과정이 필수적으로
필요합니다. 마지막에 보이는 두 메서드 predecessor와
successor는 이름대로 전임자와 후임자를 계산해줍니다. 역시
반복자를 구현할 때 필요합니다.
template<typename KeyType>
typename BinarySearchTree<KeyType>::Node *BinarySearchTree<KeyType>::Node::predecessor(void) {
Node *cur = this;
if (cur == NIL)
return NIL;
if (cur->left != NIL) {
cur = cur->left;
while (cur->right != NIL)
cur = cur->right;
return cur;
}
while (cur->parent != NIL && cur->parent->left == cur)
cur = cur->parent;
return cur->parent;
}
template<typename KeyType>
typename BinarySearchTree<KeyType>::Node *BinarySearchTree<KeyType>::Node::successor(void) {
Node *cur = this;
if (cur == NIL)
return NIL;
if (cur->right != NIL) {
cur = cur->right;
while (cur->left != NIL)
cur = cur->left;
return cur;
}
while (cur->parent != NIL && cur->parent->right == cur)
cur = cur->parent;
return cur->parent;
}
predecessor와 successor 메서드입니다. 알고리즘
설명대로 구현하면 됩니다.
template<typename KeyType>
class BinarySearchTree<KeyType>::iterator {
private:
Node *current;
public:
iterator() {}
iterator(Node *node) : current(node) {}
inline iterator &operator++(void) {
this->current = this->current->successor();
return *this;
}
inline iterator operator++(int) {
iterator tmp(this->current);
this->current = this->current->successor();
return tmp;
}
inline iterator &operator--(void) {
this->current = this->current->predecessor();
return *this;
}
inline iterator operator--(int) {
iterator tmp(this->current);
this->current = this->current->predecessor();
return tmp;
}
inline KeyType operator*(void) {
return this->current->key;
}
inline bool operator==(const iterator other) {
return this->current == other.current;
}
inline bool operator!=(const iterator other) {
return this->current != other.current;
}
friend void BinarySearchTree<KeyType>::remove(iterator it);
};
iterator 클래스는 현재 방문 중인 노드를 가리키는 변수
current를 가집니다. STL에서는 크기의 역순으로 방문하기 위해
reverse_iterator라는 걸 따로 정의했는데, 귀찮아서 그냥 감소
연산자를 써서 역순 방문이 가능하도록 만들었습니다. 증가 연산자는 현재 노드의
전임자, 감소 연산자는 후임자를 방문하게 됩니다. 참조 연산자는 현재 노드의
키를 리턴합니다. 그 외에 비교 연산자를 구현했습니다.
template<typename KeyType>
typename BinarySearchTree<KeyType>::iterator BinarySearchTree<KeyType>::insert(KeyType key) {
this->size++;
if (this->root == NIL) {
// make new node for root
this->root = new Node(key);
this->node_max = this->node_min = this->root;
return iterator(this->root);
}
Node *cur = this->root;
while (true) {
if (key < cur->key) {
// left subtree
if (cur->left == NIL) {
cur->left = new Node(key);
cur->left->parent = cur;
if (cur == this->node_min)
this->node_min = cur->left;
cur = cur->left;
break;
}
cur = cur->left;
}
else if (cur->key < key) {
// right subtree
if (cur->right == NIL) {
cur->right = new Node(key);
cur->right->parent = cur;
if (cur == this->node_max)
this->node_max = cur->right;
cur = cur->right;
break;
}
cur = cur->right;
}
else
// key already exist
return iterator(NIL);
}
return iterator(cur);
}
insert는 추가할 키를 받아서 새로 삽입한 노드를 가리키는 반복자를
리턴하도록 했습니다. (이미 있는 키인 경우 NIL을 가리키는 반복자를 리턴)
트리가 비어있는 경우는 예외로 처리합니다.
template<typename KeyType>
typename BinarySearchTree<KeyType>::iterator BinarySearchTree<KeyType>::search(KeyType key) {
Node *cur = this->root;
while (cur != NIL && cur->key != key) {
if (key < cur->key)
// left subtree
cur = cur->left;
else
// right subtree
cur = cur->right;
}
return iterator(cur);
}
search입니다. 역시 키를 받아서 그 키를 가진 노드를 가리키는
반복자를 리턴합니다. 훨씬 간단하죠.
template<typename KeyType>
void BinarySearchTree<KeyType>::remove(BinarySearchTree<KeyType>::iterator it) {
Node *v = it.current;
if (v == NIL)
return;
this->size--;
if (v->left != NIL && v->right != NIL) {
// two children
// replace v by its successor
Node *s = v->successor();
v->key = s->key;
v = s;
}
if (v == this->node_max)
this->node_max = v->predecessor();
if (v == this->node_min)
this->node_min = v->successor();
if (v->left == NIL && v->right == NIL) {
// no children
if (v == this->root)
// if v is root, make root be NIL
this->root = NIL;
else if (v == v->parent->left)
// v is left child of its parent
v->parent->left = NIL;
else
// v is right child of its parent
v->parent->right = NIL;
}
else {
// one child
Node *child = (v->left == NIL? v->right : v->left);
if (v == this->root) {
// if v is root, make child be root
child->parent = NIL;
this->root = child;
}
else if (v == v->parent->left) {
v->parent->left = child;
child->parent = v->parent;
}
else {
v->parent->right = child;
child->parent = v->parent;
}
}
delete v;
}
remove는 매우 복잡합니다. 먼저 반복자를 받아서 반복자가 가리키는
노드를 삭제하도록 해봅시다. 첫 if 문은 삭제할 노드의 자식이 둘일 경우
후임자의 키를 삭제할 노드에 복사하고 삭제할 노드를 전임자로 변경해 줍니다. 이
처리를 하면 삭제할 노드는 무조건 자식이 하나 아니면 없으므로, 각 경우에 대해
적절히 노드를 삭제하면 됩니다.
template<typename KeyType>
void BinarySearchTree<KeyType>::remove(KeyType key) {
this->remove(this->search(key));
}
키를 받아서 삭제를 하고 싶으면 search로 노드를 찾으면 됩니다.
template<typename KeyType>
typename BinarySearchTree<KeyType>::iterator BinarySearchTree<KeyType>::begin(void) {
return iterator(this->node_min);
}
template<typename KeyType>
typename BinarySearchTree<KeyType>::iterator BinarySearchTree<KeyType>::end(void) {
return iterator(NIL);
}
template<typename KeyType>
typename BinarySearchTree<KeyType>::iterator BinarySearchTree<KeyType>::rbegin(void) {
return iterator(this->node_max);
}
template<typename KeyType>
typename BinarySearchTree<KeyType>::iterator BinarySearchTree<KeyType>::rend(void) {
return iterator(NIL);
}
위 네 메서드는 반복자를 써서 트리를 순회할 때 필요한 시작점과 끝점을 계산해줍니다.
template<typename KeyType>
void BinarySearchTree<KeyType>::print(void) {
cout << "size: " << this->size << endl;
vector<Node *> cur_level = {this->root};
vector<vector<Node *>> levels;
bool no_leaf = false;
while (!no_leaf) {
levels.push_back(cur_level);
cur_level.clear();
no_leaf = true;
for (Node *p : *levels.rbegin()) {
if (p != NIL && p->left != NIL) {
cur_level.push_back(p->left);
no_leaf = false;
}
else
cur_level.push_back(NIL);
if (p != NIL && p->right != NIL) {
cur_level.push_back(p->right);
no_leaf = false;
}
else
cur_level.push_back(NIL);
}
}
int width = 4 * levels.rbegin()->size();
for (vector<Node *> &lv : levels) {
for (Node *node : lv) {
string s;
if (node != NIL)
s = to_string(node->key);
cout << string((width - s.size()) / 2, ' ') << s << string((width - s.size() + 1) / 2, ' ');
}
cout << endl;
width /= 2;
}
}
마지막으로 디버깅용 메서드 print입니다. BFS를 이용해 각 높이별로
노드 목록을 만들고, 폭에 맞춰서 적절히 출력합니다.
이 외에도 트리 크기, 트리가 비었는지 등의 여부를 계산할 메서드가 필요하지만 생략하겠습니다.
BinarySearchTree<int> b;
b.insert(4);
b.insert(2);
b.insert(6);
b.insert(1);
b.insert(5);
b.insert(7);
b.insert(3);
BinarySearchTree<int>::iterator it;
for (it = b.begin(); it != b.end(); it++)
cout << *it << ' ';
cout << endl;
for (it = b.rbegin(); it != b.rend(); it--)
cout << *it << ' ';
cout << endl;
b.remove(5);
it = b.search(2);
b.remove(it);
for (it = b.begin(); it != b.end(); it++)
cout << *it << ' ';
cout << endl;
for (it = b.rbegin(); it != b.rend(); it--)
cout << *it << ' ';
cout << endl;
BinarySearchTree클래스는 위와 같이 사용할 수 있습니다.
문제점
위에서 보듯, 이진 탐색 트리 연산의 시간복잡도는 트리 높이 $h$에 비례합니다. 트리가 충분히 균형잡혀 있다면 $h=O(\log n)$이 되어 아주 빠르게 연산할 수 있지만 다음과 같이 똑같이 1, 2, 3, 4, 6, 7, 8, 10, 15를 포함하고 있어도 한 쪽으로 치우친(skewed) 경우에는 정렬된 연결 리스트와 다를 게 없습니다. 결국 평균적으로는 $O(n)$보다 빠를지 몰라도 최악의 경우엔 정렬된 연결 리스트와 동일한 성능을 보여줍니다.
따라서 이를 해결하기 위해 이진 탐색 트리에 몇가지 속성을 더하여 균형잡힌 이진 트리가 되도록 한 AVL 트리, 레드-블랙 트리 등의 자료 구조가 제안되었습니다.