이진탐색트리

- 내부 노드에 (key, value)로 저장하는 이진트리로 다음 성질을 만족함.

p, l(p의 왼쪽), r(p의 오른쪽) 일 때, l.key < p.key <= r.key 를 만족

 

전제: 적정이진트리

 

탐색

- 루트부터 내려가면서, 해당 노드가 외부노드가 아닌 경우 크기를 비교하면서 내려감

- 만약 외부노드인 경우, 해당 노드를 반환(결과값이 없음)

// 탐색
Node* treeSerach(Node* n, int target) {
    if (isExternal(n))
        return n;

    if (target == n->key)
        return n;
    else if (target > n->key)
        return treeSearch(n->l,target);
    else
        return treeSearch(n->r, targt);
}

// 탐색 결과
void findElement(Tree* t, int target) {
    Node* res = treeSearch(t->root, target);
    if (isExternal(res))
        printf("No such key\n");
    else
        printf("target: %d\n", res->key);
}

 

삽입

- treeSearch()를 통해, res가 외부노드면 그 자리에 추가 후, 리프노드 생성

- 내부노드인 경우, 기존값이 있기 때문에 패스

void insertItem(Tree* t, int target) {
    Node* res = treeSearch(t->root, target);

    if (isInternal(res))
        return;
    else {
        res->key = target;
        expandExternal(res);
    }
    
}

- expandExternal은 단순하게 left와 right에 리프노드를 생성하는 메서드임.

 

삭제

case1: 적어도 한쪽 자식이 외부노드인 경우

- 나머지 자식을 p와 바꿔치기 한고, 부모와 외부노드 자식을 삭제

 

case2: 자식 모두 내부 노드인 경우

- 중위순회에서 다음 후계자와 자신을 swap한다.

- 후계자에게 reduceExternal을 실행한다.

 

void removeElement(Tree* t, int target) {
    Node* w = treeSearch(t->root, target);
    Node* z = w->l;
    if (!isExternal(z))
        z = w->r;
    // case 1
    if (isExternal(z)) {
        reduceExternal(t, z);
    }
    // case 2
    else {
        // 바꿔치기 후
        Node* next = inOrderSucc(w);
        next->key = w->key;

        // 외부노드 z 삭제
        z = next->l;
        reduceExternal(t, z);
    }
}