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 : 왼쪽, 오른쪽이 존재함 (포인터가 두 개 존재함)
• 중간 값이 계속 존재하는 것이 이상적임 → 이번 경우에는 강제하지 않겠음
• 어떠한 값이 있다면 왼쪽엔 전부 작은 값, 오른쪽엔 전부 큰 값이 존재함

https://medium.com/swlh/binary-search-tree-in-javascript-31cb74d8263b

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;
}