[ Algorithm ] Binary Search Tree?

Binary Search Tree 이란?

     이진 탐색 트리(binary search tree)란 연결리스트(linked list)를 결합한 자료구조의 일종이다.

     이진 탐색(binary search)의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제가 가능합니다.

 

     이진 탐색(binary search)의 경우 탐색에 소요되는 계산복잡성은 O(longN)으로 빠르지만, 입력 및 삭제가 불가능하고,

     연결리스트의 경우 입력, 삭제에 필요한 복잡도는 O(1)이지만, 탐색을 하는데, O(N)의 시간이 걸리는데,

     탐색과 입력 및 삭제를 효율적으로 활용해보고자 하는 것이, 이진 탐색 트리(Binary Search Tree)입니다.

     시간 복잡도 

         Common case : O(h)

         Worst case : O(n)

Binary Search Tree  동작

        1. 주어진 값을 트리의 루트로 삽입합니다.

        2. 다음 요소를 일곡, 루트 노드 요소보다 작으면 왼쪽 하위 트리의 루트로 삽입합니다.

        3. 그렇지 않으면 오른쪽 하위 트리의 오른쪽 루트로 삽입합니다.

Insertion into A Binary Search Tree code with C/C++

void insert (treePointer, *node, int k) {
    treePointer ptr;
    treePointer temp = modifiedSearch(*node, k);
    if (temp || !(*node)) {
        MALLOC(ptr, sizeof(*ptr));
        ptr->data.key = k;
        ptr->leftChild = ptr->rightChild = NULL;
        
        if (*node) {
            if ( k < temp->data.key)
                temp->leftChild = ptr;
            else
                temp->rightChild = ptr;
        } else
            *node = ptr;
    }
}