BST 삽입, 찾기, 삭제

1. BST 노드 구조 구축

struct node {
    int key;
    node *parent,*left,*right;
};

노드 와 빈 노드 를 동시에 정의 합 니 다.

node *NIL,*root;

2. 삽입 작업 진행

먼저 트 리 에 노드 가 없 으 면 삽입 할 노드 를 루트 노드 로 하고 부모 노드 를 NIL 로 설정 합 니 다.

만약 에 나무 에 뿌리 노드 가 있다 면 두 노드 x 와 y 를 정의 하고 x 는 꽂 아야 할 위 치 를 가리 키 며 y 는 x 의 부모 노드 를 가리킨다.

x 를 초기 화하 고 삽입 합 니 다.

void Insert(int key){
    node *y = NIL,*x = root,*z;
    z = (node *)malloc(sizeof(node));
    z->key = key;
    z->left = z->right = NIL;
    //  ，   root NIL    
    while (x != NIL){
        y = x;
        if (z->key < x->key){
            x = x->left;
        }else
            x = x->right;
    }
    z->parent = y;
    if (y == NIL){
        root = z;
    }else{
        if (z->key < y->key){
            y->left = z;
        }else
            y->right = z;
    }
}

3. 찾기 작업 진행
찾기 조작 은 매우 쉬 우 니, 여기 서 는 군말 하지 않 겠 다.

node *Find(node *u,int key){
    while (u != NIL && u->key != key){
        if (key < u->key){
            u = u->left;
        }else
            u = u->right;
    }
    return u;
}

4. 삭제 작업 진행

우선 삭제 할 점 을 찾 을 수 있 는 지 확인 하기

뿌리 노드 에 한 개의 나무 만 있 고 뿌리 노드 를 삭제 한 상황 을 단독 분석

if (p->parent == NIL && p->left == NIL){
    p = p->right;root = p;return;
}else if (p->parent == NIL && p->right == NIL){
    p = p->left;root = p;return;
}

다음 에 다른 상황 에 대해 분석 을 한다.

p 가 가리 키 는 노드 의 왼쪽 나 무 는 비어 있다

p 가 가리 키 는 노드 의 오른쪽 트 리 가 비어 있 습 니 다

p 가 가리 키 는 노드 의 좌우 서브 트 리 가 모두 비어 있 지 않 습 니 다

그 중에서 p 는 삭제 해 야 할 노드 를 가리 키 고 q 는 p 를 가리 키 며 s 는 p 의 왼쪽 아 이 를 가리킨다.
앞의 두 가지 상황 은 비교적 간단 하 다.
세 번 째 상황 에 대해 서 는 노드 를 삭제 할 직접 전구 (또는 직접 후계) 를 찾 은 다음 에 직접 전구 (또는 직접 후계) 의 값 을 p 가 가리 키 는 노드 에 부여 한 다음 에 q 의 서브 트 리 를 다시 연결 한 다음 에 s 지침 을 free 로 떨 어 뜨리 면 됩 니 다.(그 중에서 q 는 s 를 가리 키 는 부모, 선구자 와 후계 가 모두 중간 순서 에 비해 옮 겨 다 니 는 것 입 니 다)

if (p->left == NIL){
        if (p == p->parent->left){
            q = p;p->parent->left = p->right;free(q);
        }else{
            q = p;p->parent->right = p->right;free(q);
        }
    }else if (p->right == NIL){
        if (p == p->parent->left){
            q = p;p->parent->left = p->left;free(q);
        }else{
            q = p;p->parent->right = p->left;free(q);
        }
    }else{
        q = p;
        s = p->left;
        //  p     
        while (s->right != NIL){
            q = s;
            s = s->right;
        }
        p->key = s->key;
        if (q != p){
            q->right = s->left;
        }else{
            q->left = s->left;
        }
        free(s);
    }

이로써 BST 삽입, 찾기, 삭제 작업 이 완료 되 었 습 니 다.