Binary Search Tree
[지금까지 한 것]
- 배열 - 단점 : size의 제한
- Linked List - 단점 : search가 느림 (자료가 조금만 커져도)
>> size도 바꿀 수 있고 search도 빠른 자료 구조가 없을까?
search를 빠르게 하는 것 : binary search
→ Linked List와 비슷한데, binary search가 되도록 하고 싶음
Skip List
node를 건너뛸 수 있는 Linked List
Linked List의 단점을 그대로 가지고 있음
Binary Search Tree ( 이진 탐색 트리 )
- 다양한 버전이 존재함
- Linked List : 다음 것이 있음 ↔ Binary Search Tree : 왼쪽, 오른쪽이 존재함 (포인터가 두 개 존재함)
- 중간 값이 계속 존재하는 것이 이상적임 → 이번 경우에는 강제하지 않겠음
- 어떠한 값이 있다면 왼쪽엔 전부 작은 값, 오른쪽엔 전부 큰 값이 존재함
Tech Definition
- Node가 존재하며 Node안에 Key가 있다 (Key : 아주 넓은 뜻의 단어로 데이터 등을 나타냄) - 간단하게 integer = key로 보자
- 하나의 Root Node가 존재 - 제일 위에 있는 것을 root라고 함
- Empty BST를 생각해야함 - Root Node가 없는 경우 : Dummy Node를 미리 코드로 짜두기 (Root 위에 넣어놓기)
- child node가 두개 있을 수 있음 - 왼쪽, 오른쪽
- child node 아래에는 또 child가 있고 ..
- child는 subtree의 root이다
- subtree도 BST이다 (재귀적으로 생각할 수 있음)
- 왼쪽 subtree는 전부 작고, 오른쪽 subtree는 모두 크다 - 모든 곳에서 성립한다
Node
class Node{
public:
int key; // 값-key
Node *L, *R; //왼쪽 포인터, 오른쪽 포인터
};
Search
Node* BST::Search (int x, Node* N){
if(N == NULL) return NULL;
if(x == N->key) return N;
else if (x < N->key) return Search(x, N->L); // 찾는 값이 작은 경우
else return Search(x, N->R); // 찾는 값이 큰 경우
}- 첫 시작 호출은 Search(root, x)
- 원하는 값을 가진 노드를 찾으면 1, 아니면 -1 반환
- 재귀적으로 구현됨
search에서 요구하는 것 : x가 존재한다면 찾자
존재하는가와 아닌가를 대답해야함
child에 물어본 대답이 그대로 대답이 됨. 즉, 현재 내 노드의 대답과 child의 대답이 같음
x가 존재하는지에 대한 대답은 child와 같아짐
child에서 찾음 -> 전체에서 찾음
성능
트리 모양에 따라 달라짐
트리의 높이 - tree height
tree height에 걸리는 성능이 비례한다
N : 노드의 개수
한쪽 방향으로만 연결되는 경우 O(N) - 지금 정의에서는 허용해줌 ===> 이 때 N은 tree height와 같다
보통 O(log N)의 시간 복잡도를 가짐 (tree의 높이가 일반적으로 log N 높이임)
- Worst case : O(height)
- Average Case : There are not many nodes near the top -> 가장 멀리까지 간다고 쳐도 평균적으로는 절반
- Random order : all of n! permutations are equally likely
- Probability that the root has 1 is 1/n, 2 is 1/n,... 1/n
- E(Height of n Nodes) : \(E(n) = \frac{1}{n}\sum_{k=1}^{n}(E(k-1) + E(n-k))\)
- Turns out to be O(log n), also with high probability
정확성 증명
증명해야할 것 :
1. 키 값으로 x를 가지는 노드가 BST에 존재한다면, search(x, root)는 그 노드의 주소값을 리턴한다
2. 존재하지 않는다면 NULL을 리턴한다.
[ 1 ] 키 값으로 x를 가지는 노드가 BST에 존재한다면, search(x, root)는 그 노드의 주소값을 리턴
base : root에 x가 존재한다고 가정하면, root를 리턴한다.
step : search(x, N-1)에서, N을 루트로하는 서브트리 내에 x키를 가진 노드A가 존재한다고 가정 (믿자)
case 1 : 현재 노드가 x와 값이 같은 경우 현재 노드를 리턴함
case 2 : 왼쪽에 존재하는 경우 ( 찾는 값이 더 작은 경우)
왼쪽 서브트리에 존재하므로 이진 탐색 트리의 특성에 의해 x < N-1 -> key가 참이 되므로, 다음 재귀 호출에서도 존재함
case 3 : case2의 경우와 같은 오른쪽 존재
∴ N을 루트로 하는 서브트리 내에 A가 무조건 존재하게 된다.
서브트리의 크기는 재귀호출 될 때마다 작아지므로 결국은 그 값을 가진 노드가 리턴된다.
[ 2 ] 존재하지 않는다면 NULL을 리턴
자식노드를 타고 내려가면 결국 N에 NULL이 있는 것을 확인할 수 있으므로 NULL을 리턴함
Insert
int BST::Insert(int x, Node *N, Node **RP){
Node *new_node;
if(N == NULL){
new_node = new Node;
new_node -> key = x;
new_node -> L = new_node -> R = NULL:
*RP = new_node;
}
else{
if(N->key < x) return Insert(X, N->R, &(N->R));
else if(N -> key > x) return Insert(x, N->L, &(N->L));
else return; // 중복된 키 값이 있다면 insert를 하지 않는다
}정확성 증명
search알고리즘과 같은 경로를 따라 노드 A에 도달한다 -> 존재한다면 return;이 실행되므로, 중복값이 존재할 수 없음
N : 삽입 되어야할 노드의 주소
RP : N을 가리키는 노드의 주소 (즉 바로 위 부모노드)
N이 NULL이 아니면 -> 아직 삽입할 위치를 찾지 못했음
N이 NULL이면 insert실행
1. 노드 생성
2. 생성된 새 노드에 값, R,L 포인터에 NULL을 넣어줌
3. 부모 노드가 노드를 가리키도록 함
성능
insert자체의 성능은 O(1)
Delete
지워야할 노드 N에 대하여
case 1 : child가 없는 경우 - N을 가리키고 있던 부모 노드의 포인터를 NULL로 변환해줌 > N free
case 2 : child가 하나 있는 경우 - N의 부모 노드 포인터에 N의 자식노드를 가리키도록 변환 > N free
case 3: child가 두개 있는 경우
- 노드의 모든 값을 정렬했을 때 N의 값 바로 뒤의 값을 노드 x라고 가정하자
- x는 N의 오른쪽 자식 노드의 맨 왼쪽에 위치함 -> successor
- 삭제하려는 노드의 successor는 최대 1개의 노드를 가짐
- 노드 N의 키 값을 x의 키 값으로 대체함 -> 노드 x를 삭제하는 과정을 case 1, 2에 따라 진행
int Delete (Node *N, Node *P){
if(N -> L == NULL && N -> R == NULL){//자식 노드가 없는 경우
if(P -> L == N) P->L = NULL:
else P -> R == NULL;
delete N;
}
else if (N->L == NULL || N -> R == NULL){ //자식 노드가 하나인 경우
if(P -> L == N){
if(N -> L != NULL) P -> L = N -> L;
else P -> L = N -> R;
}
else {
if(N -> L != NULL) P -> R = N -> L;
else P -> R = N -> R;
}
}
else{ // 자식노드가 2개
next_N은 successor
Node* next_N = N->R;
Node* next_N_P = N;
while(next_N != NULL){
next_N_P = next_N;
next_N = next_N -> L;
}
N -> key = next_N -> key;
Delete(next_key, next_N_P);
}
}연속성 증명 (Continuity Lemma)
case 3에서 -> ................ a, x, .....처럼 연속적으로 정렬되는 이유
- 모든 노드에 대해 증명하면 됨
- 루트 아래에 있는 것들이 모두 연속으로 나옴
- 루트 왼쪽에 있는 것은 모두 루트보다 작고, 루트 오른쪽에 있는 것은 모두 루트 오른쪽에 있으므로 아래로 내려가도 항상 같은 조건을 만족함
성능
height 에 비례하여 O(log N)이다
Alternative Proofs (전체에 대한 정확성 증명)
Lemma : A BST is correct if and only if Search() succeeds for all values in the BST
proof
insert의 경우 :
- leaf에 알맞은 위치에 노드를 추가하므로, 추가된 노드를 제외하고 다른 모든 노드들을 찾는데에는 영향이 없음
- 알맞은 위치에 insert 했으므로 찾을 수 있음
delete의 경우 :
- case 1 : leaf를 없애는 경우, 찾는 경로가 모든 노드가 같으므로 성립함
- case 2 : 부모 노드를 없앴으므로, 중간에 부모 노드가 아닌, 다른 노드로 이동함. 그 전과 이후에는 영향이 없음 / 경로에서 부모 노드가 빠진 것 뿐이다
- case 3 : 경로 상에서 a가 x로 대체된 것 뿐이다
BST 전체 코드
#include <iostream>
#include <stdio.h>
class Node{
public:
int a;
Node *L, *R;
};
class BST{
public:
BST();
//제거자 생성하지 않음
Node *Search(int x);
Node *SearchP(Node *N, int x);
void Insert(int x);
void InsertP(Node *N, int x, Node **RP);
void Delete(int x);
void Print();
void PrintP(Node *N, int d, int LR);
Node *Root;
Node *Prt;
};
BST :: BST(){
Root = new Node;
Root -> a = 999;
Root -> L = NULL;
Root -> R = NULL;
}
Node *BST::Search(int x){
Prt = Root;
return SearchP(Root -> L, x);
}
Node *BST::SearchP(Node *N, int x){
if(N == NULL) return NULL;
else {
if(N->a < x) {
Prt = N;
return SearchP(N->R, x);
}
else if(N->a > x) {
Prt = N;
return SearchP(N->L, x);
}
else {
printf("found!\n");
return N;
}
}
return NULL;
}
void BST::Insert(int x){
InsertP(Root->L, x, &(Root->L));
}
void BST::InsertP(Node *N, int x, Node **RP){
Node *NN;
if(N == NULL){
NN = new Node;
NN -> a = x;
NN->L = NN->R = NULL;
*RP = NN;
}
else{
if(N -> a < x) InsertP(N->R, x, &(N->R));
else if (N->a > x) InsertP(N->L, x, &(N->L));
else return ;
}
}
void BST::Print(){
PrintP(Root, 0, 0);
}
void BST::PrintP(Node *N, int d, int LR){
if(LR == 1){
for(int i = 0; i < d; i++) printf(" ");
}
printf("%8d", N->a);
if(N->L == NULL) printf("\n");
else PrintP(N->L, d+1, 0);
if(N->R == NULL) ;
else PrintP(N->R, d+1, 1);
}
void BST::Delete(int x){
Node *NN, *PP, *MD, *MDP;
NN = Search(x);
PP = Prt;
if(NN == NULL) return;
if(NN->L == NULL && NN->R == NULL){
if(PP->L == NN) PP->L = NULL;
else PP->R = NULL;
delete NN;
}
else if(NN->L != NULL && NN->R == NULL){
if(PP->L == NN) PP->L = NN->L;
else PP->R = NN->L;
delete NN;
}
else if(NN->L == NULL && NN->R != NULL){
if(PP->L == NN) PP->L = NN->R;
else PP->R = NN->R;
delete NN;
}
else {
MD = NN -> R;
MDP = NN;
while(MD -> L != NULL) {
MDP = MD;
MD = MD -> L;
}
NN -> a = MD -> a;
if(MD->L == NULL && MD->R == NULL){
if(MDP->L == MD) MDP->L = NULL;
else MDP->R = NULL;
delete MD;
}
else if(MD->L == NULL && MD->R != NULL){
if(MDP->L == MD) MDP->L = MD->R;
else MDP->R = MD->R;
delete MD;
}
else{}
}
}
int main(int argc, const char * argv[]) {
char c;
int x;
BST T;
Node *RR;
while(true) {
T.Print();
scanf(" %c", &c);
if(c == 's'){
scanf("%d", &x);
if((RR = T.Search(x)) == NULL) printf("%d Not Found\n", x);
else printf("%d Found at Address %p\n", x, RR);
}
else if(c == 'i'){
scanf("%d", &x);
T.Insert(x);
}
else if(c == 'd'){
scanf("%d", &x);
T.Delete(x);
}
else if(c == 'q') break;
else printf("???\n");
}
return 0;
}