Binary Search Tree
이진 검색 트리
* 검색 트리의 종류 (URL)
Mechanism & Pseudo Code (메커니즘과 의사 코드)
- 이진 검색 트리의 각 노드는 하나의 Key를 갖는다.
- 각 노드의 Key값은 서로 달라야 한다.
- 최상위 Level에 Root 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다.
- 임의의 노드의 Key 값은 자신의 왼쪽에 있는 모든 노드의 Key 값보다 크고,
오른쪽에 있는 모든 노드의 Key 값보다 작다.
* 이진 검색 트리의 예시
Search Operation (검색 연산)
treeSearch(t, x) {
// t: 트리의 루트노드를 함수에 건네서, 트리를 전달한다.
// x: 검색하고자 하는 Key
if(t == NULL or key[t] == x)
then return t; // 찾고자 하는 Key가 루트 노드인 경우
// 혹은, 검색에 실패할 경우 (NULL을 리턴하게 됨)
if(x < key[t])
then return treeSearch(left[t], x); // 왼쪽 서브트리에서 x를 찾는다.
else
then return treeSearch(right[t], x); // 오른쪽 서브트리에서 x를 찾는다.
}- 검색에 실패하는 경우, 임의의 Leaf 노드까지 도달하게 되고, 함수는 NULL을 리턴한다.
Insertion Operation (삽입 연산)
treeInsert(t, x) {
// t: 트리의 루트노드를 함수에 건네서, 트리를 전달한다.
// x: 삽입하고자 하는 Key
// 삽입 작업 완료 후, 루트 노드의 포인터를 리턴한다.
if(t == NULL) then{
key[r] ← x;
left[r] ← NULL;
right[r] ← NULL;
return r;
}
if(x < key[t]) then {
left[t] ← treeInsert(left[t], x);
return t;
}
else {
right[t] ← treeInsert(right[t], x);
return t;
}
}- 원소 x를 이진 검색 트리에 삽입하기 위해서는, 해당 원소가 트리에 존재하지 않아야 한다.
- 원소 x를 삽입하기 위해서는 원소 x에 대해 실패한 검색 연산을 수행해야 한다.
(원소 x가 트리 내에서 발견되지 않을 것이므로 연산이 실패할 수 밖에 없다.)
- 원소 x에 대한 검색 연산의 결과로 임의의 Leaf 노드의 자식 노드의 위치(=NULL)가 리턴될 것이고,
이 위치가 원소 x가 삽입될 위치이다.
* Insertion Operation with Non-Recursive Method (삽입 연산의 비재귀 버전)
treeInsert(t, x) {
// t: 트리의 루트노드를 함수에 건네서, 트리를 전달한다.
// x: 삽입하고자 하는 Key
key[r] ← x;
left[r] ← NULL;
right[r] ← NULL;
// r은 새로 삽입할 노드이다.
if(t == NULL) then root ← r;
else {
p ← NULL;
tmp ← t;
while(tmp != NULL) {
p ← tmp;
if(x < key[tmp]) then tmp ← left[tmp];
else tmp ← right[tmp];
}
if(x < key[p]) then left[p] ← r;
else right[p] ← r;
}
}
Deletion Operation (삭제 연산)
- 이진 검색 트리에서의 삭제는 아래와 같은 세 가지 Case에 대해 각각 다르게 처리되어야 한다.
- 삭제하고자 하는 노드를 "r"이라 칭한다.
- 삭제 연산은 최악의 경우, 트리의 높이에 따라 최소 \(\Theta(\log n)\)에서 최대 \(\Theta(n)\) 사이의 시간이 소요된다.
Case I
- r이 Leaf 노드인 경우이다.
- r과 그의 부모 노드와의 관계를 끊는 것으로 삭제 연산이 끝난다.
- 상수 시간이 소요된다.
Case II
- r의 자식 노드가 하나인 경우이다.
- r의 부모노드와 r의 자식 노드를 이어주는 것으로 삭제 연산이 끝난다.
- 상수 시간이 소요된다.
Case III
- r의 자식 노드가 두 개인 경우이다.
- r을 Root로 하는 Subtree내에서 r을 대체할 수 있는 노드를 찾아 r의 자리에 옮긴다. (r을 제거하고 그 자리를 차지하게 한다.)
- r을 대체할 수 있는 노드는 Subtree에서 딱 두 개 존재한다.
- r의 왼쪽 자식 중 가장 큰 노드 혹은 r의 오른쪽 자식 중 가장 작은 노드이다.
- Subtree에서 새롭게 Root 노드가 된 노드는 자식이 하나있거나, 없는 노드일 것이므로,
그 빈자리는 Case I 혹은 II의 방법대로 처리한다.
- Case III의 경우, 노드 r을 대체할 원소를 찾는데에 최악의 경우 트리의 높이에 비례하는 시간이 소요된다.
treeDelete(t, r, p) {
// t: 트리의 루트노드를 함수에 건네서, 트리를 전달한다.
// r: 삭제하고자 하는 Key
// p: r의 부모 노드
if(r == t) // r이 루트 노드인 경우
then root ← deleteNode(t);
else if(r == left[p]) // r이 p의 왼쪽 자식인 경우
then left[p] ← deleteNode(r);
else // r이 p의 오른쪽 자식인 경우
right[p] ← deleteNode(r);
}
deleteNode(r) {
if(left[r] == right[r] == NULL) // Case I
then return NULL;
else if (left[r] == NULL and right[r] != NULL) // Case II
then return right[r];
else if (left[r] != NULL and right[r] == NULL) // Case II
then return left[r];
else { // Case III
s ← right[r]; // r의 오른쪽 자식들중에서
while(left[s] != NULL) { // 가장 작은 Key를 가진 노드를 찾아간다. (왼쪽 Link로만 계속 타고 내려가면 r의 오른쪽 Subtree에서 가장 작은 노드를 찾을 수 있다.
parent ← s;
s ← left[s];
}
key[r] ← key[s];
if (s == right[r])
then right[r] ← right[s];
else
left[parent] ← right[s];
return r;
}
}Performance Evaluation (자료구조 성능 평가)
- n개의 원소로 구성된 이진 트리의 Depth(Level)는
가장 이상적으로 균형이 잡힌 경우(Complete Binary Tree), Depth = \(\log n\) 이고,
한 쪽으로 편향된 경우(Skewed Binary Tree), Depth = \(n\)이다.
- 따라서, 이진 검색 트리의 검색 시간은 최소 \(\Theta(\log n)\) 에서 최대 \(\Theta(n)\) 사이의 시간이 소요된다.
- 삽입 연산의 경우, 검색 연산 후에 이뤄지는 노드 삽입 작업은 상수 시간내에 처리되므로
검색과 삽입의 점근적 실행 시간은 동일하다.
※ n개의 노드로 구성된 이진 검색 트리의 평균 \(\mathrm{IPL} = O(n\log n)\)
pf) \(D(n)\): 키가 \(n\)개인 모든 이진 검색 트리의 평균 \(\mathrm{IPL}\)
\(D(0) = 0, D(1) = 1, D(2) = 3\)이며, \(D(n)\)에 대한 점화식은 아래와 같다.
\(D(n) = {1 \over n}\sum\limits_{i=0}^{n-1} (D(i) + D(n-i-1)) + n\)
\(\qquad \; \; = {2 \over n}\sum\limits_{i=0}^{n-1} D(i) + n\)
\(n=2\)일 때, \(D(2) \leq c2\log 2\)가 성립하도록 \(c\)를 설정할 수 있다.
모든 \(2 \leq k < n\)에 대해 \(D(k) \leq ck\log k\)가 성립한다 가정할 때, (귀납적 가정)
점화식 \(D(n)\)은 아래와 같이 나타낼 수 있다.
\(D(n) = {2 \over n}\sum\limits_{i=0}^{n-1} D(i) + n = {2 \over n}\sum\limits_{i=2}^{n-1} D(i) + {2 \over n}D(1) + n\)
\(\qquad \; \; \leq {2 \over n}\sum\limits_{i=2}^{n-1} ci\log i + n + {2 \over n}\)
\(\qquad \; \; \leq {2 \over n}\int_{1}^{n} cx\log x \, dx + n + {2 \over n}\)
\(\qquad \; \; = {2c \over n}({1 \over 2}n^2 \log n - {1 \over 4}n^2 + {1 \over 4}) + n + {2 \over n}\)
\(\qquad \; \; = cn\log n - {cn \over 2} + {c \over 2n} + n + {2 \over n}\)
\(\qquad \; \; = cn\log n + {(2-c)n \over 2} + {c+4 \over 2n}\)
\(\qquad \; \; \leq cn\log n\)
\(c = 3\)이면, \(2 \leq n\)인 모든 \(n\)에 대해 \(D(n) \leq cn\log n\)이므로,
\(D(n) = O(n\log n)\)이다.
즉, 모든 이진 검색 트리의 평균 \(\mathrm{IPL}\)은 \(O(n\log n)\)이다.
이를 통해 아래와 같은 정리가 파생된다.
※ \(n\)개의 노드로 구성된 이진 검색 트리의 평균 Depth = \(O(\log n)\)
※ \(n\)개의 노드로 구성된 이진 검색 트리에 대해 소요되는 평균 검색/삽입 연산 수행 시간 = \(O(\log n)\)
BST Interface and Implementation (C++)
Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)
