이진 탐색 트리 (Binary Search Tree)

Binary Search Tree is a node-based binary tree data structure which has the following properties:

이진 트리는 최상위 루트 노드로부터 하위 트리로 갈 때 가질 수 있는 자식의 노드 수가 2개 이하인 트리 구조를 의미한다. 이진 탐색 트리는 노드 기반 자료 구조이며 다음의 네 가지 특성을 가진다.

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.
4. There must be no duplicate nodes.

1. 왼쪽 서브트리의 데이터 값은 부모 노드의 데이터 값보다 작은 값을 가진다.
2. 오른쪽 서브트리의 데이터 값은 부모 노드의 데이터 값보다 큰 값을 가진다.
3. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
4. 모든 노드는 다른 값을 가진다.

이진 탐색 트리에서 특정 값을 찾는 연산은 세 가지 방법으로 이루어진다.

1. 검색을 원하는 데이터 값 = 루트 노드: 원하는 값을 찾음 탐색 성공
2. 검색을 원하는 데이터 값 < 루트 노드: 루트 노드의 왼쪽 서브트리에서 탐색
3. 검색을 원하는 데이터 값 > 루트 노드: 루트 노드의 오른쪽 서브트리에서 탐색

1. 이진 탐색 트리 검색 및 노드 추가 함수

#include <stdio.h>
#include <stdlib.h>

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

// 이진 탐색 트리 생성 함수
struct node *newNode(int item) {
    // temp 생성 및 동적 메모리 할당
    struct node *temp = malloc(sizeof(struct node));
    // temp의 key에 item 저장
    temp -> key = item;
    // temp의 left와 right에 NULL 저장
    temp -> left = temp -> right = NULL;
    return temp;
}

// 이진 탐색 트리 노드 방문 함수
void inorder(struct node *root) {
    // root이 NULL이 아니면
    if (root != NULL) {
        // root의 left 노드 방문
        inorder(root -> left);
        // root의 key를  출력
        printf("%d \n", root -> key);
        // root의 right 노드 방문
        inorder(root -> right);
    }
}

// 이진 탐색 트리 노드 추가 함수
struct node *insert(struct node *node, int key) {
    // 트리의 노드가 없으면 newNode의 key를 반환
    if (node == NULL)
        return newNode(key);

    // key 값이 node의 key보다 작으면 node의 left에 삽입
    if (key < node -> key)
        node -> left = insert(node -> left, key);
    // key 값이 node의 key보다 크면 node의 right에 삽입
    else if (key > node -> key)
        node -> right = insert(node -> right, key);
    
    // key 값이 node의 key와 같으면 node를 반환
    return node;
}

int main() {
    struct node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    inorder(root);

    return 0;
}

2. 이진 탐색 트리 노드 삭제 함수

1. 삭제할 노드의 자식이 0개이거나 1개인 경우
   삭제할 노드의 부모 노드에서 삭제하여 자신이 있던 자리에 자식의 주소를 넘긴다.

2. 삭제할 노드의 자식이 2개인 경우
   삭제할 노드의 자식 노드 중 삭제할 노드와 가장 비슷한 값을 가진 노드를 찾는다.
   후계자 노드: 삭제할 노드와 가장 비슷한 값을 가진 노드 (왼쪽 서브트리 중 가장 큰 값, 혹은 오른쪽 서브트리 중 가장 작은 값)

후계자 노드의 값만 복사하여 삭제할 노드의 값에 대입한다.

삭제할 노드 대신 후계자 노드를 삭제한다.

#include <stdio.h>
#include <stdlib.h>

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

struct node *newNode(int item) {
    struct node *temp = malloc(sizeof(struct node));
    temp -> key = item;
    temp -> left = temp -> right = NULL;

    return temp;
}

void inorder(struct node *root) {
    if (root != NULL) {
        inorder(root -> left);
        printf("%d \n", root -> key);
        inorder(root -> right);
    }
}

struct node *insert(struct node *node, int key) {
    if (node == NULL)
        return newNode(key);
    
    if (key < node -> key)
        node -> left = insert(node -> left, key);
    else
        node -> right = insert(node -> right, key);
    
    return node;
}

struct node *minValueNode(struct node *node) {
    struct node *current = node;

    while (current && current -> left != NULL)
        current = current -> left;
    
    return current;
}

struct node *deleteNode(struct node *root, int key) {
    if (root == NULL)
        return root;
    
    if (key < root -> key)
        root -> left = deleteNode(root -> left, key);
    
    else if (key > root -> key)
        root -> right = deleteNode(root -> right, key);
    
    else {
        if (root -> left == NULL) {
            struct node *temp = root -> right;
            free(root);
            return temp;
        }
        else if (root -> right == NULL) {
            struct node *temp = root -> left;
            free(root);
            return (temp);
        }

        struct node *temp = minValueNode(root -> right);

        root -> key = temp -> key;

        root -> right = deleteNode(root -> right, temp -> key);
    }

    return root;
}

int main() {
    struct node *root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal of the given tree \n");
    inorder(root);

    printf("\nDelete 20\n");
    root = deleteNode(root, 20);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    printf("\nDelete 30\n");
    root = deleteNode(root, 30);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    printf("\nDelete 50\n");
    root = deleteNode(root, 50);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);
    return 0;
}