[Data Structure] Binary Search Tree - deleting node

 저번 글에 이어서 이진 탐색 트리에서 노드를 삭제하는 함수를 만들어 볼 것이다. 이진 탐색 트리에서 삭제를 할 때에는 3가지 타입을 알아야 한다.

삭제하고자 하는 노드가..
1. 단말 노드 일 때
2. 하나의 자식 노드가 존재할 때
3. 두개의 자식 노드가 존재할 때

 자신이 단말 노드일 경우 그냥 삭제하면 된다. 이 부분은 아주 간단하다. 하나의 자식 노드가 가지고 있는 노드일 경우에는 자식 노드에게 자신의 자리를 넘겨주면 된다. 

 마지막으로 두개의 자식 노드가 존재 할 때에는 두개의 정파를 생각해야한다. 그리고 우리는 그 중에서 그나마 중도를 걷는 녀석을 후계자로 삼아야 한다. 즉, 지우고자 하는 노드이 key값과 가장 가까운 자식 노드를 후계자로 삼아야 한다는 점이다. 그리고 가장 값이 가까운 노드는 왼쪽 서브 트리의 가장 오른쪽 아래의 노드 혹은 오른쪽 서브 트리의 가장 왼쪽 아래 노드이다. 


(참고로 코드에서 succ 은 후계자, succ_p 는 후계자의 부모 노드
t 는 현재 노드 혹은 지우고자 하는 노드
p 는 t의 부모 노드
child 는 t의 자식 노 드 이다.)

void delete_node(TreeNode **root, element key){
    TreeNode *p, *t, *child; // p는 부모 노드, t는 현재 노드, child는 서브 노드가 하나 일때 사용
    TreeNode *succ_p, *succ; // succ_p는 후계자 부모, succ는 후계자 노드. 서브 노드가 둘 일때 사용
    
    t = *root;
    p = NULL;
    
    while (t != NULL) {
        if (key == t->data) break;
        p = t;
        t = key < t->data ? t->left : t->right;
    } // 동일 key를 가진 노드를 찾는다
    
    if (t == NULL) return; // 동일키가 없다
    
    // 1. t가 단말 노드일 경우
    if (t->left == NULL && t->right == NULL) {
        if (p == NULL) { // 삭제 노드가 root일 경우다.
            *root = NULL;
        } else  {
            if (p->left == t) {
                p->left = NULL;
            } else {
                p->right = NULL;
            }
        }
    }
    // 2. 서브 노드가 하나일때
    else if (t->left == NULL || t->right == NULL){
        child = t->left == NULL ? t->right : t->left;
        if (p != NULL) {
            if (p->left == t) {
                p->left = child;
            } else {
                p->right = child;
            }
        } else {// 삭제 노드가 root일 경우
            *root = child;
        }
    }
    // 3. 서브 노드가 둘일때
    else {
        printf("p :: %d , t :: %d\n", p->data, t->data);
        succ_p = t;
        succ = t->right;
        
        while (succ->left != NULL) {
            succ_p = succ;
            succ = succ->left;
        }
        
        // 여기서부터 이게 대체 뭔소리인가 싶다. ... 조금 더 알아봐야할 코드다.
        if (succ_p->left == succ) {
            succ_p->left = succ->right;
        } else {
            succ_p->right = succ->right;
        }
        t->data = succ->data;
        t= succ;
    }
    free(t);
}

int main(){
    TreeNode root = {18,NULL,NULL};
    TreeNode *exp = &root;
    
    insert_node(&exp, 7);
    insert_node(&exp, 26);
    insert_node(&exp, 3);
    insert_node(&exp, 12);
    insert_node(&exp, 31);
    insert_node(&exp, 27);
    insert_node(&exp, 25);
    delete_node(&exp, 26);
    
    TreeNode *result = iter_search(exp, 26);
    if (result != NULL) {
        printf("There is %d\n", result->data);
    } else {
        printf("There isn't\n");
    }
    
    return 0;
}

adf

코드에서 보면 서브 노드가 2개일 때 마지막 코드 부분이 이해가 안된다.

코드는 다음과 같다.

       if (succ_p->left == succ) {
            succ_p->left = succ->right;
        } else {
            succ_p->right = succ->right;
        }
        t->data = succ->data;
        t= succ;

이 코드가 이해되면 즉시 포스팅을 수정하고 업데이트하겠다..