[Jungol] 정올 4320 이진탐색 트리 (binary search tree) 2

출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3670&sca=99&page=29

Approach

now 노드 삭제 

① child 노드가 존재하지 않는다면 단순히 삭제

② child 노드가 1개인 경우

    → now 자리를 child가 대신한다.

③ child가 lch, rch 두 개인 경우

Left/Right Sub Tree 중 에서 now와 가까운 숫자(target node)를 찾아야 합니다.

즉, Left Sub Tree에서 가장 큰 숫자 혹은 Right Sub Tree에서 가장 작은 숫자가 해당됩니다.

    ※ 여기서 대체되는 target 노드를 후임자(successor)라고 합니다.

    ※ 이진탐색트리 정의를 생각하면 child가 2개인 노드는 반드시 그 서브 트리에 successor를 갖습니다.

 

Q. 만약 『12』가 삭제될 때, Left Sub Tree에서 『11』 혹은 Right Sub Tree에서 『13』 중에서 후임자 선택

    ※ 문제에서는 Right Sub Tree에서 찾는 것으로 구현

① target->data가 now->data 자리를 채우고 target node를 제거합니다.

    마찬가지로 target node가 없어지면서 비워진 target node 위치에 eraseNode()로 재귀 처리합니다.

    이는 target node에 오른쪽 자식노드가 존재할 수 있을 수 있기 때문입니다.

    찾은 target node가 왼쪽 자식 노드를 가질 수는 없습니다.

target에 왼쪽 자식 노드가 존재하는 경우는 애초에 target를 잘못 찾은 case

(findMinNode()는 now node부터 시작하여 left child를 따라 계속 이동하기 때문에

 Left Child가 없는 노드가 이진탐색트리에서 최소값에 해당)

 

② Tree의 Node 개수가 줄어드는 시점은 ①의 재귀과정이 끝나고 ③에서 삭제되기 때문에 

    ①과 ③ 사이에 해당됩니다.

---

#ifndef NULL
#define NULL 0
#endif
const int SIZE = 100010;
struct Node {
    int data;
    Node* lch, * rch;
    Node* alloc(int nd) {
        data = nd, lch = rch = NULL;
        return this;
    }
}buf[SIZE];
int bcnt;
struct Tree {
    Node* root;
    int nodeCnt;
}tree;
Tree* newTree() {
    bcnt = 0;
    tree = Tree();
    return &tree;
}
void delTree(Tree* tree) {
    tree = NULL;
}
// 트리의 노드수를 반환한다.
int getTreeSize(Tree* tree) {
    return tree->nodeCnt;
}
Node* searchNode(Node* now, int nd) {
    // 찾는 노드가 존재하지 않거나 찾은 경우
    if (now == NULL || now->data == nd)
        return now;
    // 왼쪽 Sub Tree 탐색
    if (now->data > nd) {
        return searchNode(now->lch, nd);
    }
    // 오른쪽 Sub Tree 탐색
    return searchNode(now->rch, nd);
}
// 트리에 data가 있다면 1을 없다면 0을 반환한다.
int search(int data) {
    return !!searchNode(tree.root, data);
}
Node* insertNode(Node* now, int nd) {
    if (now == NULL) { // 단말노드까지 도달한 경우
        tree.nodeCnt++;
        Node* ptr = buf[bcnt++].alloc(nd);
        return ptr;
    }
    if (now->data == nd) return now;
    if (now->data > nd)
        now->lch = insertNode(now->lch, nd);
    else
        now->rch = insertNode(now->rch, nd);
    
    return now; // if(now->data == nd)인 경우
}
// 트리에 data가 존재한다면 아무일도 하지 않는다.
// 그렇지 않은경우 트리에 data를 추가한다.
void insert(int data) {
    tree.root = insertNode(tree.root, data);
}
// data를 찾을 수 없다면 아무일도 하지 않는다.
// 트리에서 data를 찾아 삭제한다.
// [노드 now를 삭제하는  프로세스]
// 1. child 노드가 없다면 삭제한다.
// 2. child가 하나뿐이라면 now자리를 child가 대신한다.
// 3. child가 lch, rch 두 개라면 now->data보다 크고
//    now->data에 가장 가까운 노드(이를 target이라 하자)를 삭제하고
//    target->data가 now->data 자리를 채운다.
Node* findMinNode(Node* now) {
    for (; now->lch; now = now->lch);
    return now;
}
Node* eraseNode(Node* now, int nd) {
    if (now == NULL) return now;
    if (now->data == nd) {
        if (now->lch && now->rch) {
            Node* ret = findMinNode(now->rch);
            now->data = ret->data;
            now->rch = eraseNode(now->rch, now->data);
            return now;
        }
        tree.nodeCnt--;
        if (now->lch == NULL && now->rch == NULL) return NULL;
        if (now->lch == NULL) return now->rch;
        return now->lch; // if(now->rch == NULL)
    }
    else if (now->data > nd)
        now->lch = eraseNode(now->lch, nd);
    else
        now->rch = eraseNode(now->rch, nd);
    return now;
}
int flag, idx, * ap;
void travel(Node* now) {
    if (now == NULL) return;
    // flag 상태(전위,중위,후위)에 따라 data를 저장하는 시기가 다름
    if (flag == 4) ap[idx++] = now->data;
    travel(now->lch);
    if (flag == 5) ap[idx++] = now->data;
    travel(now->rch);
    if (flag == 6) ap[idx++] = now->data;
}
void erase(int data) {
    tree.root = eraseNode(tree.root, data);
}
// tree를 전위순회한 결과를 arr에 담는다.
void preorder(Tree* tree, int* arr) {
    flag = 4, idx = 0, ap = arr;
    travel(tree->root);
}
// tree를 중위순회한 결과를 arr에 담는다.
void inorder(Tree* tree, int* arr) {
    flag = 5, idx = 0, ap = arr;
    travel(tree->root);
}
// tree를 후위순회한 결과를 arr에 담는다.
void postorder(Tree* tree, int* arr) {
    flag = 6, idx = 0, ap = arr;
    travel(tree->root);
}