[Introduction To Algorithm 12장] 이진 검색 트리 내용 정리 및 C코드 구현

1. Intro

• 검색 트리 자료구조는 사전(dict)나 우선순위큐(priority queue)로 사용 가능하다.
• 평균 O(logN) 시간 안에 수행된다.
• 이진 검색 트리를 기반으로 레드블랙트리(최악의 경우에도 빠른 실행 속도 보장), B트리(데이터 베이스 관리 유용)로 확장된다.

2. 개념

• Node : key, left(Node), right(Node), parent(Node)
• Nil : 자식이나 부모가 없는 노드에 생성(부모가 nil이면, root 노드인 것이다)
• 이진 검색 트리의 특성 :
  x, y가 트리의 한 노드라고 할 때, x.key >= y.key, y는 x의 왼쪽 서브트리, x.key <= y.key, y는 x의 오른쪽 서브트리에 존재.
• 순서대로 출력 : 중위 트리 순회(inorder tree walk)를 통해 수행

3. 주요 Method

3-1. SEARCH

• 매개변수 :
  1) 트리 (트리를 매개변수로 일괄적으로 전달하고, 함수 내부에서 root를 사용한다.)
  2) 찾으려는 값(key)
• 시간복잡도 : O(h) - h는 트리의 높이(왼쪽이든 오른쪽이든 한 번씩 탐색하기에 트리의 높이만큼 탐색)

Node *tree_search(Tree *t, int key)
{
    Node *p = t->root;
    while (p != NULL)
    {
        if (key < p->key)
        {
            p = p->left;
        }
        else if (key > p->key)
        {
            p = p->right;
        }
        else
        {
            return p;
        }
    }
    printf("\n 찾는 키가 없습니다.");
    return p;
}```

### 3-2. MIN or MAX
- 시간복잡도 : O(h) - search함수와 같은 맥락이다
```c 
// 4. [METHOD] MIN
Node *tree_minimum(Node *root)
{
    Node *y;
    while (root != NULL)
    {
        y = root;
        root = root->left;
    }
    return y;
}

// 5. [METHOD] MAX
Node *tree_maximum(Node *root)
{
    Node *y;
    while (root != NULL)
    {
        y = root;
        root = root->right;
    }
    return y;
}

3-3. SUCCESSOR(직후 원소) or PREDECESSOR(직전 원소)

// 6. [METHOD] SUCCESSOR (직후 원소)
Node *tree_successor(Node *p)
{
    if (p->right != NULL)
    {
        return tree_minimum(p->right);
    }
    Node *y = p->parent;
    while (y != NULL && p == y->right)
    {
        p = y;
        y = y->parent;
    }
    return p->parent;
}

// 7. [METHOD] PREDECESSOR (직전 원소)
Node *tree_predecessor(Node *p)
{
    if (p->left != NULL)
    {
        return tree_maximum(p->left);
    }
    Node *y = p->parent;
    while (y != NULL && p == y->left)
    {
        p = y;
        y = y->parent;
    }
    return p->parent;
}

3-4. INSERT(삽입)

// 8. [METHOD] INSERT(삽입)
Node *tree_insert(Tree *t, int key)
{
    Node *new_node = (Node *)malloc(sizeof(Node));
    Node *x = t->root;
    Node *y = t->nil;

    new_node->key = key;
    new_node->left = NULL;
    new_node->right = NULL;

    // 1. 삽입될 장소를 찾는다.
    while (x != NULL)
    {
        y = x; // 부모 주소 저장하려고
        if (x->key < key)
        {
            x = x->right;
        }
        else
        {
            x = x->left;
        }
    }

    // 2. 새 노드에 부모를 연결
    new_node->parent = y; // 부모 주소 전달

    // 3. 부모에 새 노드를 연결
    if (y == t->nil)
    {
        t->root = new_node;
    }
    else if (y->key < key)
    {
        y->right = new_node;
    }
    else
    {
        y->left = new_node;
    }
    return new_node;
}

3-5. DELETE(삭제)

// [METHOD] TRANSPLANT : 기존의 노드를 새로운 노드로 대체
void transplant(Tree *t, Node *u, Node *v)
{
    if (u->parent == t->nil) // 기존의 노드의 부모가 nil이면, 새로운 노드는 root
    {
        t->root = v;
    }
    else if (u == u->parent->left) // 기존 노드의 부모의 left에 기존 노드가 위치했다면, 그 위치에 새로운 노드 지정
    {
        u->parent->left = v;
    }
    else // 기존 노드의 부모의 right에 기존 노드가 위치했다면, 그 위치에 새로운 노드 지정
    {
        u->parent->right = v;
    }
    if (v != t->nil) // 새로운 노드가 root가 아니면, 새로운 노드에 부모의 노드를 연결
    {
        v->parent = u->parent;
    }
}

// 9. [METHOD] DELETE(삭제)
void tree_delete(Tree *t, Node *z)
{
    if (z == NULL)
    {
        return 0;
    }

    if (z->left == t->nil)
    {
        // case 1,2 : 자식이 아예 없거나 하나 있는 경우
        transplant(t, z, z->right);
    }
    else if (z->right == t->nil)
    {
        // case 1,2 : 자식이 아예 없거나 하나 있는 경우
        transplant(t, z, z->left);
    }
    else
    {
        // case 3 : 자식이 둘 있는 경우
        Node *y = tree_minimum(z->right);
        if (y->parent != z)
        {
            transplant(t, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(t, z, y);
        y->left = z->left;
        y->left->parent = y;
    }
}

3-6. INORDER PRINT(프린트)

void inorder_tree_walk(Node *root)
{
    if (root != NULL)
    {
        inorder_tree_walk(root->left);
        printf("%d -> ", root->key);
        inorder_tree_walk(root->right);
    }
}

3-7. MAIN(testing)

int main(void)
{
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    Node *root = tree_insert(tree, 1);
    Node *a1 = tree_insert(tree, 5);
    Node *a2 = tree_insert(tree, 3);
    Node *a3 = tree_insert(tree, 9);
    Node *a4 = tree_insert(tree, 2);
    inorder_tree_walk(root);
    tree_delete(tree, a4);
    inorder_tree_walk(root);
    // printf("%d", tree_maximum(a2)->key);
    // printf("%d", tree_predecessor(a3)->key);
    return 0;
}

4. 전체 코드

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

// 1. node 구조체
typedef struct Node
{
    int key;
    struct Node *left, *right, *parent;
} Node;

typedef struct
{
    Node *root;
    Node *nil;
} Tree;

// 2. [METHOD] inorder PRINT
void inorder_tree_walk(Node *root)
{
    if (root != NULL)
    {
        inorder_tree_walk(root->left);
        printf("%d -> ", root->key);
        inorder_tree_walk(root->right);
    }
    printf("\n\n");
}

// 3. [MTEHOD] SEARCH
Node *tree_search(Tree *t, int key)
{
    Node *p = t->root;
    while (p != NULL)
    {
        if (key < p->key)
        {
            p = p->left;
        }
        else if (key > p->key)
        {
            p = p->right;
        }
        else
        {
            return p;
        }
    }
    printf("\n 찾는 키가 없습니다.");
    return p;
}

// 4. [METHOD] MIN
Node *tree_minimum(Node *root)
{
    Node *y;
    while (root != NULL)
    {
        y = root;
        root = root->left;
    }
    return y;
}

// 5. [METHOD] MAX
Node *tree_maximum(Node *root)
{
    Node *y;
    while (root != NULL)
    {
        y = root;
        root = root->right;
    }
    return y;
}

// 6. [METHOD] SUCCESSOR (직후 원소)
Node *tree_successor(Node *p)
{
    if (p->right != NULL)
    {
        return tree_minimum(p->right);
    }
    Node *y = p->parent;
    while (y != NULL && p == y->right)
    {
        p = y;
        y = y->parent;
    }
    return p->parent;
}

// 7. [METHOD] PREDECESSOR (직전 원소)
Node *tree_predecessor(Node *p)
{
    if (p->left != NULL)
    {
        return tree_maximum(p->left);
    }
    Node *y = p->parent;
    while (y != NULL && p == y->left)
    {
        p = y;
        y = y->parent;
    }
    return p->parent;
}

// 8. [METHOD] INSERT(삽입)
Node *tree_insert(Tree *t, int key)
{
    Node *new_node = (Node *)malloc(sizeof(Node));
    Node *x = t->root;
    Node *y = t->nil;

    new_node->key = key;
    new_node->left = NULL;
    new_node->right = NULL;

    // 1. 삽입될 장소를 찾는다.
    while (x != NULL)
    {
        y = x; // 부모 주소 저장하려고
        if (x->key < key)
        {
            x = x->right;
        }
        else
        {
            x = x->left;
        }
    }

    // 2. 새 노드에 부모를 연결
    new_node->parent = y; // 부모 주소 전달

    // 3. 부모에 새 노드를 연결
    if (y == t->nil)
    {
        t->root = new_node;
    }
    else if (y->key < key)
    {
        y->right = new_node;
    }
    else
    {
        y->left = new_node;
    }
    return new_node;
}
// [METHOD] TRANSPLANT : 기존의 노드를 새로운 노드로 대체
void transplant(Tree *t, Node *u, Node *v)
{
    if (u->parent == t->nil) // 기존의 노드의 부모가 nil이면, 새로운 노드는 root
    {
        t->root = v;
    }
    else if (u == u->parent->left) // 기존 노드의 부모의 left에 기존 노드가 위치했다면, 그 위치에 새로운 노드 지정
    {
        u->parent->left = v;
    }
    else // 기존 노드의 부모의 right에 기존 노드가 위치했다면, 그 위치에 새로운 노드 지정
    {
        u->parent->right = v;
    }
    if (v != t->nil) // 새로운 노드가 root가 아니면, 새로운 노드에 부모의 노드를 연결
    {
        v->parent = u->parent;
    }
}

// 9. [METHOD] DELETE(삭제)
void tree_delete(Tree *t, Node *z)
{
    if (z == NULL)
    {
        return 0;
    }

    if (z->left == t->nil)
    {
        // case 1,2 : 자식이 아예 없거나 하나 있는 경우
        transplant(t, z, z->right);
    }
    else if (z->right == t->nil)
    {
        // case 1,2 : 자식이 아예 없거나 하나 있는 경우
        transplant(t, z, z->left);
    }
    else
    {
        // case 3 : 자식이 둘 있는 경우
        Node *y = tree_minimum(z->right);
        if (y->parent != z)
        {
            transplant(t, y, y->right);
            y->right = z->right;
            y->right->parent = y;
        }
        transplant(t, z, y);
        y->left = z->left;
        y->left->parent = y;
    }
}

int main(void)
{
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    Node *root = tree_insert(tree, 1);
    Node *a1 = tree_insert(tree, 5);
    Node *a2 = tree_insert(tree, 3);
    Node *a3 = tree_insert(tree, 9);
    Node *a4 = tree_insert(tree, 2);
    inorder_tree_walk(root);
    tree_delete(tree, a4);
    inorder_tree_walk(root);
    // printf("%d", tree_maximum(a2)->key);
    // printf("%d", tree_predecessor(a3)->key);
    return 0;
}