BST (Binary Search Tree)

[자료구조 복습]

자료구조를 복습하면서 트리 위주로 보고 있는데 그 이유는 정말 많은 트리가 있고 실제로 범용성이 크기 때문이다.

BST 트리를 다시 볼때 개념도 어렵지 않고 이름부터 쉬워보여서 사실 쉽게 넘어갈 줄 알았다. 직접 구현을 해보려니 미천한 나의 실력으로 정말 오래 걸렸다. 재귀함수를 기피하다 보니까 코드도 지저분해지고...

Binary Search Tree란 다음의 성질을 만족하는 이진트리다.

• Each node has exactly one key and the keys in the tree are distinct
• The keys (if any)  in the left subtree are smaller than the key in the root
• The keys (if any)  in the right subtree are smaller than the key in the root
• subtrees are also BST

즉 leftchild < parent < rightchild 형태를 띄는 이진트리이다.

BST operations

• search
• insert
• delete

역시 코드를 보자.

#define ITER 0
#define RECUR 1
#define SEARCH ITER

typedef struct _NODE {
    int key;
    struct _NODE* leftchild;
    struct _NODE* rightchild;
    struct _NODE* parent;
}BST;

BST* bst_root;

BST* r_search(BST* subtree,int key) {
    if (!subtree) return NULL;
    if (subtree->key == key)
        return subtree;
    if (key < subtree->key)
        return r_search(subtree->leftchild, key);
    return r_search(subtree->rightchild, key);
}

BST* i_search(BST* subtree, int key) {
    while (subtree) {
        if (key == subtree->key)
           return subtree;
        if (key < subtree->key)
            subtree = subtree->leftchild;
        else
            subtree = subtree->rightchild;
    }
    return NULL;
}

BST* m_search(BST* subtree, int key) {
    while (subtree) {
        if (key == subtree->key)
            return NULL;
        if (key < subtree->key) {
            if (subtree->leftchild == NULL)
                return subtree;
            subtree = subtree->leftchild;
        }
        else {
            if (subtree->rightchild == NULL)
                return subtree;
            subtree = subtree->rightchild;
        }
    }
    return NULL;
}

search 의 경우 정말 간단하다.

왼쪽 오른쪽을 비교해가며 내려가면서 key 값을 비교하기만 하면된다.
BST가 균형이 잘 맞춰져 있다면 시간복잡도는 O(log n) 에 가깝고 한쪽으로 치우친 리스트 형태를 띄면 최악의 경우 O(n) 이다. 즉 트리의 깊이를 d라 할때 O(d)라 볼 수 있다.

search가 3개나 있는 이유는 recursive, iterative, 그리고 insert에 사용할 modified search가 필요하기 때문이다.

void insert(BST** root, int key) {
    BST* temp=m_search(*root,key);
    if (temp || !(*root)) {
        BST* new_node = (BST*)malloc(sizeof(BST));
        new_node->key = key;
        new_node->leftchild = NULL;
        new_node->rightchild = NULL;
        new_node->parent = NULL;
        if (temp) {
            if (key < temp->key)
                temp->leftchild = new_node;
            else
                temp->rightchild = new_node;
            new_node->parent = temp;
        }
        else *root = new_node;
    }
}

insert의 경우 일단 BST에 key값이 존재하는지 판별한다. 이미 존재 한다면 insert 할 필요가 없고 존재하지 않는다면 m_search로 부터 반환받은 위치의 leftchild 혹은 rightchild 에 insert한다.

위치를 반환한 후 나머지 작업은 O(c) 이므로 총 시간 복잡도는 O(h)이다.

void bst_delete(int key) {
    BST* del_node=i_search(bst_root,key);
    BST* parent = del_node->parent;
    BST *temp_root;

    if (!del_node) {
        fprintf(stdout, "not in the tree\n");
        return;
    }
 
    /* DEL_NODE HAS 0 OR 1 CHILD */
    if (del_node->leftchild == NULL) {
        BST *temp = del_node->rightchild;
        free(del_node);
        if (!parent) {
            bst_root = temp;
            if(temp)
                temp->parent = NULL;
            return;
        }
        if (parent->leftchild->key == del_node->key)
            parent->leftchild = temp;
        else
            parent->rightchild = temp;
        return;
    }
    else if (del_node->rightchild == NULL) {
        BST *temp = del_node->leftchild;
        free(del_node);
        if (!parent) {
            bst_root = temp;
            if(temp)
                temp->parent = NULL;
            return;
        }
        if (parent->leftchild->key == del_node->key)
            parent->leftchild = temp;
        else
            parent->rightchild = temp;
        return;
    }
    /* DEL_NODE HAS 2 CHILD */
    else if (del_node->leftchild && del_node->rightchild) {
        BST* curr=del_node->leftchild;
        while (curr->rightchild) {
            curr = curr->rightchild;
        }
        del_node->key = curr->key;
        curr->parent->rightchild = curr->leftchild;
        if(curr->leftchild)
            curr->leftchild->parent = curr->parent;
        free(curr);
    }
}

이 빌어먹을 deletion을 짜느라 고생좀 했다(사실 오류가 있을지도 모른다)

insertion 과 다르게 살짝 복잡한데 delete 할 node의 자식 수에 따라 다르게 행동하기 때문이다.

1. delete 할 node에 child node가 없다면 그냥 free해버린다.
2. delete 할 node에 child node가 하나 있다면 delete 할 node 의 위치에 child를 둔 후 free한다
3. delete 할 node에 child node가 두개 있다면 왼쪽 subtree에서 가장 큰 node나 오른쪽 subtree에서 가장 작은 node (A 라 하자)를 delete할 node의 key를 swap한 후 A의 위치에는 A의 left child를 둔다

사실 재귀함수로 짜인 여러 예쁜 코드들을 봤지만 interative로 작성해보고 싶어 시도했다가 정말 시간을 많이 버렸다.