[C언어 #70] 이진탐색트리 (Binary Search Tree) - 구현 (3) - 노드 삭제

c언어 이진탐색트리 (Binary Search Tree) - 구현 (3) - 노드 삭제

 

[C언어 #69] 이진탐색트리 (Binary Search Tree)

[C언어 #70] 이진탐색트리 (Binary Search Tree) - 구현 (1) - 노드 생성, 노드 삽입

[C언어 #70] 이진탐색트리 (Binary Search Tree) - 구현 (2) - 노드 탐색

 

 

구현 함수 정리

#include <stdbool.h>
 
// 트리(Tree)를 구성하는 노드 구조체
struct node;
typedef struct node node;
 
// 숫자 k를 가지는 노드를 생성
node *newNode(int k);
 
// 트리의 데이터 제거 및 메모리 해제
node *freenode(node *p);
 
// 숫자 k를 가지는 노드를 트리에 삽입
node *insert(node *p, int k);
 
// 트리에서 k를 탐색
node *search(node *p, int k);
 
// k값을 가진 노드 존재 여부 확인
bool find(node *p, int k);
 
// 트리에서 최소값을 가진 노드 반환 (노드 삭제시 활용)
node *minnode(node *p);
 
// k값을 가진 노드를 트리에서 제거
node *deletenode(node *p, int k);

 

 

최소값을 가진 노드 반환

node *minnode(node *p) {
    node *min = p;
    while (min->left != NULL) min = min->left;
    return min;
}

 

 

테스트 - 최소값을 가진 노드 반환 테스트

void testMinnode() {
    node *p = newNode(7);
    p = insert(p, 3);
    p = insert(p, 11);
    p = insert(p, 5);
    p = insert(p, 2);
    p = insert(p, 19);
    p = insert(p, 17);
    p = insert(p, 13);
    node *min = minnode(p);
    assert(min->value == 2);
    freenode(p);    
}

 

 

노드 삭제

node *deletenode(node *p, int k) {
    if (p == NULL) return p;
 
    if (k < p->value) {
        p->left = deletenode(p->left, k);
    } else if (k > p->value) {
        p->right = deletenode(p->right, k);
    } else {
 
        if (p->left == NULL) {
            node *tmp = p->right;
            free(p);
            return tmp;
        } else if (p->right == NULL) {
            node *tmp = p->left;
            free(p);
            return tmp;
        }
 
        node *tmp = minnode(p->right);
        p->value = tmp->value;
        p->right = deletenode(p->right, tmp->value);
    }
 
    return p;
}

 

 

테스트 - 노드 삭제 테스트

void testDelete() {
    node *n = newNode(7);
    n = insert(n, 3);
    n = insert(n, 13);
    n = insert(n, 2);
    n = insert(n, 11);
    n = insert(n, 17);
    n = deletenode(n, 7);
    assert(n->value == 11);
    assert(n->right->value == 13);
    freenode(n);
}