이진탐색트리
왼쪽 부분트리에 있는 노드 값은 모두 루트의 값보다 작다.
오른쪽 부분트리에 있는 노드 값은 모두 루트의 값보다 크다.
왼쪽 부분트리와 오른쪽 부분트리는 이진탐색트리이다.

연산 알고리즘
– 삽입
– 삭제
– 탐색
– 부모 노드 탐색
– 중위 순회 (정렬)
– 가장 작은 키 값을 가진 노드 탐색
– size_field 부여 (부분 트리의 노드 개수)
– k번째 노드 탐색 (크기 순)

시간복잡도
: 상수 시간 안에 레벨을 한 칸씩 내려가면서 연산 처리 가능 -> O(h)
최악의 경우: O(n) -> 트리가 편향된 상태
평균의 경우: O(logn) -> 트리가 균형된 형태

코딩 테스트 예시

size_field: [3:1], [13:1], [5:3], [15:10], [20:6], [19:3], [16:2], [17:1], [25:2], [30:1]

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

typedef struct TreeNode {
    int key;
    int size_field; // 부분 트리의 노드 개수 
    struct TreeNode* left, * right;
}TreeNode;
typedef struct TreeNode* TreeNode_ptr;


// 트리에 size_field(부분트리에 속한 노드의 개수) 부여
// postorder를 응용해서 제작함 
void get_size_field(TreeNode_ptr T) {
    if (T) {
        get_size_field(T->left);
        get_size_field(T->right);
        if ((T->left == NULL) && (T->right == NULL)) // 잎 노드
            T->size_field = 1;
        else { // 내부 노드 
            if ((T->left != NULL) && (T->right != NULL))
                T->size_field = 1 + (T->left->size_field) + (T->right->size_field);
            else if ((T->left != NULL) && (T->right == NULL))
                T->size_field = 1 + (T->left->size_field);
            else
                T->size_field = 1 + (T->right->size_field);
        }
    }
}

// 이진 탐색 트리 전용 노드 생성 
TreeNode_ptr make_node(int key) {
    TreeNode_ptr tmp = (TreeNode_ptr)malloc(sizeof(TreeNode));
    tmp->key = key;
    tmp->size_field = 0; // k-selection 사용하기 전에는 update 안 함 
    tmp->left = tmp->right = NULL;
    return tmp;
}

// 가장 작은 키 값을 가진 노드 찾기 
TreeNode_ptr min_val(TreeNode_ptr T) {
    if (T->left == NULL)
        return T;
    else
        return min_val(T->left);
}

// 이진 탐색 트리 삽입
TreeNode_ptr insert_node(TreeNode_ptr T, int key) {
    if (T == NULL)
        return make_node(key);
    if (key < T->key)
        T->left = insert_node(T->left, key);
    else if (key > T->key)
        T->right = insert_node(T->right, key);
    return T; // 삽입한 뒤 루트 반환 
}

// 이진 탐색 트리 탐색 
TreeNode_ptr search_node(TreeNode_ptr T, int key) {
    if (T == NULL)
        return NULL;
    if (key == T->key)
        return T;
    else if (key < T->key)
        return search_node(T->left, key);
    else
        return search_node(T->right, key);
}


// 이진 탐색 트리의 부모 탐색 (루트가 오면 루트 반환) 
// 순환 호출할 때 현재 노드를 같이 넘겨주면, 부모 노드를 받는 것이 됨 -> 값이 같으면 부모 노드 리턴 가능!
// is_root는 루트 노드의 size_field값으로, 루트를 구분해주는 역할을 함 
TreeNode_ptr search_parent_node(TreeNode_ptr T, int key, TreeNode_ptr parent,int is_root) {
    if (T == NULL)
        return NULL;

    if (key == T->key) {
        // T는 루트 노드 
        if (T->size_field == is_root)
            return T;
        // T는 루트 노드가 아님 
        else
            return parent;
    }
    else if (key < T->key)
        return search_parent_node(T->left, key,T,is_root);
    else
        return search_parent_node(T->right, key,T,is_root);
}

// 이진 탐색 트리 삭제
TreeNode_ptr delete_node(TreeNode_ptr T, int key) {
    // 못 찾았을 때 
    if (T == NULL)
        return T;
    if (key < T->key)
        T->left = delete_node(T->left, key);
    else if (key > T->key)
        T->right = delete_node(T->right, key);

    // 찾았을 때
    else {
        // 오른쪽 서브트리만 존재한 경우 혹은 잎 노드
        if (T->left == NULL) {
            TreeNode_ptr tmp = T->right;
            free(T);
            return tmp;
        }
        // 왼쪽 서브트리만 존재한 경우 혹은 잎 노드 
        else if (T->right == NULL) {
            TreeNode_ptr tmp = T->left;
            free(T);
            return tmp;
        }
        // 두 서브트리 모두 존재한 경우 
        // 오른쪽 서브트리에서 가장 작은 노드로 대체 후 해당 노드 삭제
        else {
            TreeNode_ptr tmp = min_val(T->right);
            T->key = tmp->key;
            T->right = delete_node(T->right, tmp->key);
        }
    }
    return T; // 삭제한 뒤 루트 반환
}

// 크기 순으로 정렬했을 때 k번째 노드 찾기
TreeNode_ptr k_selection(TreeNode_ptr T, int k) {
    // size_field 이용
    static int temp = 0;
    if ((temp++) == 0)
        get_size_field(T);

    // k가 노드의 전체 개수보다 크면 k_selection 불가 
    if (k > T->size_field)
        return 0;

    else {
        // 왼쪽 size (왼쪽 서브트리의 사이즈) 
        int left_size = (T->left) ? T->left->size_field : 0;

        // 왼쪽 size가 k이상이면 왼쪽 서브트리에서 조사
        if (left_size >= k)
            return k_selection(T->left, k);

        // 왼쪽 size가 k미만
        else {
            // 왼쪽 size+자신(1)이 k이다 -> 해당 노드가 정답 
            if ((k - (left_size + 1)) == 0)
                return T;
            // 왼쪽 size+자신(1)이 k미만 -> k수정해서 오른쪽 서브트리에서 조사 
            else
                return k_selection(T->right, (k - (left_size + 1)));
        }
    }
}

// 중위 순회 (정렬)
void inorder(TreeNode_ptr T) {
    if (T) {
        inorder(T->left);
        printf("[%d] ", T->key);
        inorder(T->right);
    }
}

// 이진탐색트리 연산 테스트 
int main() {
    TreeNode_ptr T = NULL;

    // 삽입 테스트 
    T = insert_node(T, 15);
    T = insert_node(T, 5);
    T = insert_node(T, 3);
    T = insert_node(T, 13);
    T = insert_node(T, 20);
    T = insert_node(T, 19);
    T = insert_node(T, 25);
    T = insert_node(T, 16);
    T = insert_node(T, 17);
    T = insert_node(T, 30);

    // 정렬 테스트
    printf("이진 탐색 트리 중위 순회 결과 \n");
    inorder(T);
    printf("\n\n");

    // k번째 노드 탐색 테스트 
    TreeNode_ptr k_what = 0;
    for (int i = 1; (k_what = k_selection(T, i)) != 0; i++)
        printf("크기순으로 정렬했을 때 %d번째 노드의 키 값은? : %d\n", i, k_what->key);
    printf("\n");

    // 부모 노드 탐색 테스트
    printf("(15)노드의 부모 노드는 (%d)이다.\n", search_parent_node(T, 15, T,T->size_field)->key);
    printf("(17)노드의 부모 노드는 (%d)이다.\n",search_parent_node(T,17,T, T->size_field)->key);
    printf("(30)노드의 부모 노드는 (%d)이다.\n\n", search_parent_node(T, 30, T, T->size_field)->key);


    // 삭제 테스트 
    T = delete_node(T, 17);
    T = delete_node(T, 19);
    T = delete_node(T, 20);

    printf("삭제 후 중위 순회 결과 \n");
    inorder(T);
    printf("\n\n");

    // 탐색 테스트 
    if (search_node(T, 17))
        printf("이진 탐색 트리에서 17을 발견함");
    else
        printf("이진 탐색 트리에서 17을 발견못함");
    printf("\n");

    if (search_node(T, 15))
        printf("이진 탐색 트리에서 15를 발견함");
    else
        printf("이진 탐색 트리에서 15를 발견못함");
    printf("\n");

}