(c lang) binary search tree 구현

introduction to algorithms(Thomas H. Cormen...) 의 수도코드를 강력하게 참고했습니다

---

node 구조체 구현

// node definition
typedef struct node{
    int key;
    struct node *parent;
    struct node *left;
    struct node *right;
} node_t

tree 초기화

• node_t형 포인터 초기화

// initialize root
    node_t *root = NULL;

    // insert nodes
    insert(&root, 7);
    insert(&root, 3);
    insert(&root, 5);
    insert(&root, 9);
    //     7
    //    / \
    //   3   9
    //  / \  | \
    // N   5 N  N
    //    / \
    //   N   N
    print_tree(root);

functions

int print_tree(node_t *curr) 함수

• 트리의 모든 노드의 key값을 오름차순으로 출력하는 함수
• recursion을 이용한 dfs
• left subtree 탐색 -> 현재 노드 출력 -> right subtree 탐색 순서

// print keys of tree in increasing order
// using dfs
int print_tree(node_t *curr){

    // base case:
    if (curr == NULL) return 0;

    // recursive call: dfs
    print_tree(curr->left);
    printf("%d\n", curr->key);
    print_tree(curr->right);

    return 0;
}

node_t *search(node_t *curr, int k) 함수

• 주어진 key값을 가지는 노드를 찾아 그 주소(포인터) 반환하는 함수
• recursion을 이용한 탐색
• 주어진 key값과 노드의 key값을 비교해서 left child/ right child 노드로 이동
• 마지막 노드로 갔을때(주어진 key값이 없을 때)와 주어진 key값을 찾을 찾았을 때 탐색 종료

// find and return the address(node_t * type) of target node
// recursive version
node_t *search(node_t *curr, int k){
    // base case1: end of tree: return NULL
    if (curr == NULL){
        printf("cannot find a node with value %d !!\n", k);
        return curr;
    }
    // base case2: find target node
    if (curr->key == k) return curr;

    // target과 현재 노드의 key를 대소비교하며 찾아 내려간다
    // search left-subtree
    if (k < curr->key) return search(curr->left, k);
    // search right-subtree
    else return search(curr->right, k);
}

node_t *search_iterative(node_t *curr, int k) 함수

• 바로 위 search 함수의 iterative 버전

// find and return the address(node_t * type) of target node
// iterative version
node_t *search_iterative(node_t *curr, int k){
    // move to child node
    while (curr != NULL && curr->key != k){
        // search left-subtree
        if (k < curr->key) curr = curr->left;
        // search right-subtree
        else curr = curr->right;
    }
    // end of tree
    if (curr == NULL){
        printf("cannot find a node with value %d !!\n", k);
    }
    return curr;
}

node_t * minimum(node_t *curr) 함수

• 트리에서 최소 key값을 가지는 노드의 주소(포인터)를 반환하는 함수
• 트리에서 가장 왼쪽에 있는 노드를 반환

// find minimum key in tree
node_t * minimum(node_t *curr){
    // move to most-left-outside node
    while (curr->left != NULL) curr = curr->left;
    return curr;
}

node_t *maximum(node_t *curr) 함수

• 트리에서 최대 key값을 가지는 노드의 주소(포인터)를 반환하는 함수
• 트리에서 가장 오른쪽에 있는 노드를 반환

// find maximum key in tree
node_t *maximum(node_t *curr){
    // move to most-right-outside node
    while (curr->right != NULL) curr = curr->right;
    return curr;
}

node_t *successor(node_t *curr) 함수

• 주어진 노드의 successor 노드의 주소(포인터)를 반환하는 함수
• successor: 노드의 key들을 오름차순 정렬했을때 바로 다음에 오는 key값을 가지는 노드
• case1, 오른쪽 subtree가 비지 않았을 때: 오른쪽 subtree에서의 최소 값을 가지는 노드가 successor
• case2, 오른쪽 subtree가 비었을 때, curr의 조상 중 처음으로 left-child가 되는 노드의 부모 노드가 successor

// return the successor of given node
// successor: 주어진 노드의 key 바로 다음에 오는 key값을 가진 node
node_t *successor(node_t *curr){
    // case1: right subtree is non-empty
    if (curr->right != NULL) return minimum(curr->right);
    // case2: right-subtree is empty
    node_t *temp;
    temp = curr->parent;
    // 조건을 만족할 때까지 트리를 타고 올라간다
    // 조건: curr의 조상 중 처음으로 left child가 되는 노드의 부모 노드를 찾는다
    while( temp != NULL && temp->right == curr){
        curr = temp;
        temp = temp->parent;
    }
    // check impossible cases(루트노드까지 올라간 경우)
    if (temp == NULL){
        printf("there is no successor of given node!\n");
    }
    return temp;
}

node_t *predecessor(node_t *curr) 함수

• 주어진 노드의 predecessor 노드의 주소(포인터)를 반환하는 함수
• predecessor: 노드의 key들을 오름차순 정렬했을 때 직전에 오는 key값을 가지는 노드
• successor함수와 거울 대칭으로 탐색

// 참고:successor함수와 대칭
// return the predecessor of given node
// predecessor: 주어진 노드의 key 직전에 오는 key값을 가진 node
node_t *predecessor(node_t *curr){
    // case1: left-subtree is non-empty
    if (curr->left != NULL) return maximum(curr->left);
    // case2: left-subtree is empty
    node_t *temp;
    temp = curr->parent;
    // 조건을 만족할 때까지 트리를 타고 올라간다
    // 조건: curr의 조상 중 처음으로 right-child가 되는 노드의 부모를 찾는다
    while(temp != NULL && temp->left == curr){
        curr = temp;
        temp = temp->parent;
    }
    // check impossible cases
    if (temp == NULL){
        printf("there is no successor of given node!\n");
    }
    return temp;
}

int insert(node_t **ptr_root, int k) 함수

• 트리에 주어진 key값을 가지는 새로운 노드를 추가하는 함수
• 예외: 트리가 비었을 경우 새로운 노드를 root노드로 설정
• 주어진 key값과 현재 노드의 key값을 대소비교하면서 트리를 타고 내려간다
• leaf node에 도달하면 여기에 새로운 노드를 자식 노드로 추가

// 주어진 값을 갖는 노드 추가
int insert(node_t **ptr_root, int k){
    // make new_node with key k
    node_t * new_node = (node_t*)malloc(sizeof(node_t));
    new_node->key = k;
    new_node->parent = NULL;
    new_node->left = NULL;
    new_node->right = NULL;

    // check tree is empty: make root points to new node
    if (*ptr_root == NULL){
        *ptr_root = new_node;
        return 0;
    }
    // 대소비교하면서 leaf node까지 내려간다
    node_t *curr = *ptr_root;    // root부터 시작
    node_t *before = NULL;       // x 직전 node기록하기 위함
    while (curr != NULL){        // before이 new_node의 부모가 될 노드
        before = curr;
        if (k < curr->key) curr = curr->left;
        else curr = curr->right;
    }
    // curr == NULL 이면 before은 마지막 leaf node
    // before node 밑에 new_node 추가
    new_node->parent = before;
    if (k < before->key) before->left = new_node;
    else before->right = new_node;

    return 1;
}

void delete(node_t **ptr_root, node_t *target) 함수

• 트리에서 주어진 노드를 삭제하는 함수
• 3가지 케이스로 나누어 삭제를 진행
• case1, target node의 자식 노드가 0개: target node 제거하고 그 위치에 NULL 추가
• case2, target node의 자식 노드가 1개: target node 제거 후 target node의 부모에 target node의 자식 노드 연결
• case3, target node의 자식 노드가 2개: target node와 그 successor의 key값을 교환하고, successor node를 제거(successor노드의 부모노드와 successor노드의 자식노드를 연결)

// target 노드의 주소값을 받아 트리에서 제거
void delete(node_t **ptr_root, node_t *target){

    // introduction to algorithms 책 보고 이해하는 것 추천

    ////////////////////////
    // 1. splice 대상 y 결정

    node_t *y = NULL;
    // target의 자식 노드가 0, 1개인 경우: splice 대상 y는 target 자신
    if (target->left == NULL || target->right ==NULL) y = target;
    // target의 자식 노드가 2개인 경우: splice 대상 y는 target 노드의 successor 노드
    else y = successor(target);

    /////////////////////////
    // 2. y의 자식 노드 x 결정
    // y가 잘려나가면 그 밑의 노드를 이어주어야 하므로

    node_t *x = NULL;
    if (y->left != NULL) x = y->left;
    else x = y->right;

    /////////////////////////
    // 3. splicing y

    // exception case1: x = NULL인 경우 제외
    if (x != NULL) x->parent = y->parent;
    // exception case2: y가 root node인 경우(y->parent == NULL)
    if (y->parent == NULL) *ptr_root = x;
    // y가 root node가 아닌 경우
    else {
        // y의 위치에 따라 x의 부모를 y의 부모로 설정
        if (y->parent->left == y) y->parent->left = x;
        else y->parent->right = x;
    }
    // target의 자식이 2개인 경우: splicing 대상 y는 target이 아니라 target의 successor
    if (y != target) target->key = y->key;
    // delete y
    free(y);
}