[Algorithms] 이진 탐색트리(Binary Search Tree)

이번 학습 주제는

이진 탐색트리(Binary Search Tree)입니다

앞에서 이진 탐색(Binary Search)과

선형 탐색(Linear Search)을 학습했습니다

이진 탐색과 선형탐색이

궁금하시다면 아래의 링크 ↓↓

2020/07/27 - [Algorithms] - [Algorithms] 선형 탐색(Linear Search)과 이진 탐색(Binary Search)

[Algorithms] 선형 탐색(Linear Search)과 이진 탐색(Binary Search)

이진 탐색은 𝑂(㏒ 𝑛)에

탐색할 수 있는 방법이지만

삽입에는 𝑂(𝑛)의 복잡도를 필요로하고

반대로 선형 탐색은

삽입은 빠르지만 탐색이 느렸습니다

이는 배열 혹은 연결리스트 같은

데이터 구조를 이용하면

탐색 혹은 삽입에 𝑂(𝑛)의 복잡도가

필요하다는 결론입니다

이를 해결하기 위해

이진 탐색트리 등장!

이진 탐색트리는

임의의 정점에 있어서

왼쪽에 있는 자식 및 자식의 자손이

갖는 모든 데이터가 정점에 있는

데이터 보다 작고 반대로

오른쪽에 있는 자식 및 자식의 자손이

갖는 모든 데이터가 정점에 있는

데이터 보다 크다는 관계가 성립합니다

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

typedef int keytype;
typedef int boolean;
typedef char othertype;
typedef struct node tree;

struct node {
    keytype key;
    othertype otherinfo;
    tree *left, *right, *parent;
};

tree* root;

boolean search(keytype target) {
    boolean found = false;
    tree* p = root;
    while ( p != NULL ) {
        printf("[%d]\n", p -> key);
        if ( target == p -> key ) {
            found = true;
            break;
        } else if ( target < p -> key ) {
            p = p -> left;
        } else {
            p = p -> right;
        }
    }
    return found;
}

void insert(keytype x, othertype y) {
    if ( root == NULL ) {
        root = (tree *) malloc(sizeof(tree));
        root -> key = x; root -> otherinfo = y;
        root -> left = NULL; root -> right = NULL; root -> parent = NULL;
        return;
    }
    tree* p = root;
    while ( true ) {
        if ( x == p -> key ) {
            break;
        } else if ( x < p -> key ) {
            if ( p -> left != NULL ) {
                p = p -> left;
            } else {
                tree* tmp = (tree *) malloc(sizeof(tree));
                tmp -> key = x; tmp -> otherinfo = y;
                tmp -> left = NULL; tmp -> right = NULL; tmp -> parent = p;
                p -> left = tmp;
                break;
            }
        } else {
            if ( p -> right != NULL ) {
                p = p -> right;
            } else {
                tree* tmp = (tree *) malloc(sizeof(tree));
                tmp -> key = x; tmp -> otherinfo = y;
                tmp -> left = NULL; tmp -> right = NULL; tmp -> parent = p;
                p -> right = tmp;
                break;
            }
        }
    }
}

void delete(keytype x) {
    if ( root == NULL ) {
        return;
    }
    tree* p = root;
    while ( true ) {
        if ( x == p -> key ) {
            if ( p -> left == NULL ) {
                if ( p -> right == NULL ) {
                    if ( ( p -> parent ) -> key < p -> key ) {
                        ( p -> parent ) -> right = NULL;
                    } else {
                        ( p -> parent ) -> left = NULL;
                    }
                    free(p);
                } else {
                    if ( ( p -> parent ) -> key < p -> key ) {
                        ( p -> parent ) -> right = p -> right;
                    } else {
                        ( p -> parent ) -> left = p -> right;
                    }
                    free(p);
                }
            } else {
                if ( p -> right == NULL ) {
                    if ( ( p -> parent ) -> key < p -> key ) {
                        ( p -> parent ) -> right = p -> left;
                    } else {
                        ( p -> parent ) -> left = p -> left;
                    }
                    free(p);
                } else {
                    tree* cur = p -> left;
                    while ( true ) {
                        if ( p -> right != NULL ) {
                            cur = cur -> right;
                        } else {
                            if ( cur -> left != NULL) {
                                if ( ( cur -> parent ) -> key < cur -> key ) {
                                    ( cur -> parent ) -> right = cur -> left;
                                } else {
                                    ( cur -> parent ) -> left = cur -> left;
                                }
                                break;
                            }
                        }
                    }
                    if ( ( p -> parent ) -> key < p -> key ) {
                        ( p -> parent ) -> right = cur;
                    } else {
                        ( p -> parent ) -> left = cur;
                    }
                    cur -> left = p -> left;
                    cur -> right = p -> right;
                    free(cur);
                }
            }
            break;
        } else if ( x < p -> key ) {
            p = p -> left;
        } else {
            p = p -> right;
        }
    }
}

int main() {
    insert(4, 4);
    insert(1, 1);
    insert(2, 2);
    insert(3, 3);
    insert(7, 7);
    insert(8, 8);
    insert(5, 5);
    insert(10, 10);
    insert(11, 11);
    delete(11);
    delete(10);
    printf("result: %d\n", search(4));
}

위의 코드를 살펴보면

탐색이나 삽입보다 삭제가 복잡하네요😱

어쨌든 이진탐색트리에도

단점이 존재하는데요

바로 정렬된 데이터가 삽입될 때입니다

깊이가 한쪽으로 계속 깊어지기 떄문이죠-_-

정말 간단하게 생각해서

1,2,3,4가 순차적으로 삽입될 때는

앞서 학습한 선형 탐색과 동일해집니다

우리는 이를 또 해결하기 위해서

균형 트리(Balanced Tree)가 등장!

시간이 늦어지기도 했고

균형 트리는 좀 복잡하기에

균형 트리에 대해서는

다음에 학습하겠습니다-_-

이것으로 이번 학습을 마치겠습니다

그럼 이만-_-