Week 8-2 : Binary Search Tree (종강) (추가:180814)

<180608>

<소스코드>

#include <cstdio>
 
struct Node {
    int data;
    struct Node *left, *right;
    Node(int data) : data(data), left(0), right(0) {}
};
 
class bst {
private:
    Node *root;
 
public:
    bst() : root(0) {}
    
    void insert(int data) {
 
        if(!root) {
            root = new Node(data); 
            return ;
        }
 
        Node *p = 0;
        Node *cur = root;
        while(cur) {
            p = cur;
            if(cur->data < data) cur = cur->right;
            else cur = cur->left;
        }
        if(p->data < data) p->right = new Node(data);
        else p->left = new Node(data);
    }
 
    Node* getRoot() { return root; }
 
    void display(Node *root) {
        if(!root) return ; 
        display(root->left);
        printf("%d\n", root->data);
        display(root->right);
    }
 
    void remove(int data) {
        Node *p = 0;
        Node *cur = root;
        while(cur && cur->data != data) {
            p = cur;
            if(cur->data < data) cur = cur->right;
            else cur = cur->left;
        }
 
        if(!cur) return ;
 
        if(cur->left == NULL && cur->right == NULL) {
            if(p == NULL) root = NULL;
            else {
                if(p->left == cur) p->left = NULL;
                else p->right = NULL;
            }
        }
        else if(cur->left == NULL || cur->right == NULL) {
            Node *child = cur->left ? cur->left : cur->right;
 
            if(p == NULL) root = child; 
            else {
                if(p->left == cur) p->left = child;
                else p->right = child;
            }
        }
        else {
            Node *sp = cur;
            Node *sc = cur->right;
 
            while(sc->left != NULL) {
                sp = sc;
                sc = sc->left;
            }
            
            if(sp->left == sc) {
                sp->left = sc->right;     
            }
            else
                sp->right = sc->right;
 
            cur->data = sc->data;
            cur = sc;
        }
 
        delete cur;
    }
};
 
int main()
{
    bst *t = new bst();
    t->insert(5);
    t->insert(1);
    t->insert(3);
    t->insert(2);
    t->insert(10);
    t->insert(9);
    t->insert(7);
    t->insert(8);
    t->display(t->getRoot()); puts("");
    t->remove(2);
    t->display(t->getRoot()); puts("");
    t->remove(1);
    t->display(t->getRoot()); puts("");
    t->remove(9);
    t->display(t->getRoot()); puts("");
    return 0;
}
 

1) 데이터의 삽입 과정

18 7 26 31 3 12 9 27

2) 데이터 찾기.

3) 데이터의 삽입

4) 데이터의 삭제

4-1) 타겟 노드가 단말노드인 경우

4-2) 타겟 노드가 자식을 하나만 가지고 있는 경우

4-3) 타겟 노드가 두개의 자식을 가지고 있는 경우

>> 타겟의 오른쪽 자식이 왼쪽 서브트리를 가진경우 or not

5) 데이터 탐색의 시간 복잡도