BST(Binary Search Tree)

이진트리는 기본적으로 왼쪽 노드의 자식값이 부모노드보다 작은 값
오른쪽 노드의 자식값이 부모노드보다 큰값을 가지는 형태를 띈다.
left child Node < parent node < Right child Node

• 탐색
  루트 노드부터 순회하며, 탐색해야 하는 값이 루트 노드보다 클경우 오른쪽 자식 방문, 작을 경우 왼쪽 자식을 방문한다.
  방문한 노드가 NULL이 될때까지 탐색값을 찾지 못하면 해당 트리의 탐색 값이 없는 것으로 간주한다.

-삽입
루트 노드에서부터 탐색하며 삽입하는 노드값이 현재노드 보다 크면 오른쪽 작으면 왼쪽으로 간다. 반복하다가 NULL을 만나면 삽입을 하고 종료한다.

-삭제
삭제도 루트 노드에서부터 탐색하며 삭제할 값을 찾는다. 삭제하고 나면 해당 자리가 비는데 그 자리는 해당 노드보다 값이 큰 오른쪽 자식 노드들 중에서 가장 작은 값이 대체해주어야 한다.
그래야 이진 트리의 속성이 유지된다.

[구현]

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

typedef struct NodeStruct
{
    int value;
    struct NodeStruct* leftchild;
    struct NodeStruct* rightchild;
}Node;

Node* root = NULL;

Node* BST_insert(Node* root, int value) {
    //root가 NULL이면 node를 생성해준다.
    if (root == NULL) {
        root = (Node*)malloc(sizeof(Node));
        root->leftchild = NULL;
        root->rightchild = NULL;
        root->value = value;
        return root;
    }
    //value가 root의 value보다 작으면 왼쪽 크면 오른쪽으로 간다.
    else {
        if (root->value > value) {
            root->leftchild = BST_insert(root->leftchild, value);
        }
        else {
            root->rightchild = BST_insert(root->rightchild, value);
        }
    }
    return root;

}

Node* findMinNode(Node* root) {
    //가장 작은 값은 제일 밑 왼쪽에 있다는걸 이용
    Node* tmp = root;
    while (tmp->leftchild != NULL)
        tmp = tmp->leftchild;
    return tmp;
}

Node* BST_delete(Node* root, int value) {
    //value 삭제하고나서 그자리를 채울 노드를 저장하는데 사용
    Node* tNode = NULL;

    //root에 값이 없다면 삭제할 수 없으므로 NULL 반환
    if (root == NULL) return NULL;
    //현재 노드보다 value가 작다면 왼쪽자식노드로 이동

    if (root->value > value) {
        root->leftchild = BST_delete(root->leftchild, value);
    }
    //현재 노드보다 value가 크다면 오른쪽 자식노드로 이동
    else if (root->value < value) {
        root->rightchild = BST_delete(root->rightchild, value);
    }
    /*
    현재 노드와 value값이 같다면 삭제해주어야한다.
    현재 노드는 오른쪽 자식노드중에서 제일 작은 값을 찾아서 넣어준다.
    */
    else {
        //오른쪽 자식 노드와 왼쪽 자식 노드가 모두 존재한다면
        if (root->rightchild != NULL && root->leftchild != NULL) {
            //오른쪽 자식 노드중 가장 작은 값 찾아서 삭제할 노드와 교체.
            tNode = findMinNode(root->rightchild);
            root->value = tNode->value;
            //위에서 찾은 tNode의 위치를 찾는다. 삭제는 밑에 else에서 할 수 있다. 
            root->rightchild = BST_delete(root->rightchild, tNode->value);
        }
        /*
        위에서 tNode의 위치를 찾았는데 우리가 찾은 TNode는 leafNode일 수 밖에 없다.
        따라서 else를 해주면 자식이 둘다 없거나 하나만 있는 노드이고
        leaf노드를 찾을 수 있다.
        */
        else {
            //삭제해준 노드의 오른쪽 자식 노드중 가장작은 값의 오른쪽 노드값이 있을 수 있으므로 tNode를 리턴해준다.
            tNode = (root->leftchild == NULL) ? root->rightchild : root->leftchild;
            free(root);
            return tNode;
        }
    }
    return root;
}
//값이 있으면 해당 노드를 return 없으면 NULL return
Node* BST_search(Node* root, int value) {
    if (root == NULL)
        return NULL;
    if (root->value == value)
        return root;
    else if (root->value > value)
        return BST_search(root->leftchild, value);
    else
        return BST_search(root->rightchild, value);
}

void BST_print(Node* root) {
    if (root == NULL) return;

    printf("%d", root->value);
    BST_print(root->leftchild);
    BST_print(root->rightchild);
}

int main() {
    root = BST_insert(root, 5);
    root = BST_insert(root, 3);
    root = BST_insert(root, 7); 
    root = BST_insert(root, 1);
    root = BST_insert(root, 9);
    root = BST_insert(root, 6);
    root = BST_insert(root, 4);
    root = BST_delete(root, 7);
    BST_print(root);

}