[Data Structure] Binary Search Tree - Inserting node

 저번 포스트에서 이진 탐색 트리에서의 탐색을 다뤘다면 오늘은 삽입을 다룰 예정이다. 삽입을 위해서는 3단계를 거치게 되는데 

1. 탐색
2. 정의
3. 삽입

탐색은 인자값인 key가 존재하는지를 검사함과 동시에 없다면 어떤 자리에 들어가야 하는지를 보는 것이다. 탐색 후 결과적으로 해당 자리의 부모 노드를 가져오게 되는데 다음의 코드와 같은 패턴을 보여준다.

    TreeNode *p, *t; // p 는 부모노드, t 는 현재노드

    t = *root;
    p = NULL;

    while (t != NULL) { // 이러한 코드 패턴은 트리에서 부모를 찾는데 이용됨.
        if (key == t->data) return;
        p = t;
        if (key < t->data) {
            t = t->left;
        } else {
            t = t->right;
        }
    }

while 문이 종료될 때 p는 새로운 노드가 들어가야할 자리의 부모 노드가 된다.

정의는 노드의 동적 할당을 의미한다. 코드에서는 간단하게 n 으로 나타내었다. 그리고 나서 이 새로운 노드를 실제로 삽입해야 하는데 이진 탐색 트리의 정의에 따라 부모 노드의 값과 key를 비교해서 작으면 왼쪽 자식으로 크면 오른쪽 자식으로 한다. 단, 부모가 null일 경우가 있다. 이 경우는 트리가 완전히 빈 것이다. 그러므로 root 로 지정해준다.

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

typedef int element;
typedef struct {
    element data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// iteration-search
TreeNode *iter_search(TreeNode *root, element key){
    TreeNode *p = root;
    while (p!=NULL) {
        if (key == p->data) {
            return p;
        } else if (key < p->data){
            p = (TreeNode*) p->left;
        } else {
            p = (TreeNode*) p->right;
        }
    }
    return NULL;
}

void insert_node(TreeNode **root, element key){
    // root 는 TreeNode* 를 가리키게 된다.
    TreeNode *p, *t; // p 는 부모노드, t 는 현재노드
    TreeNode *n; // n 은 새로운 노드
    t = *root;
    p = NULL;
    
    // 1. 먼저 들어갈 자리의 부모노드를 Search
    while (t != NULL) { // 이러한 코드 패턴은 트리에서 부모를 찾는데 이용됨.
        if (key == t->data) return;
        p = t;
        if (key < t->data) {
            t = t->left;
        } else {
            t = t->right;
        }
    }
    
    // 2. 새로운 노드를 정의
    n = (TreeNode *) malloc(sizeof(TreeNode));
    n->data = key;
    n->left = NULL;
    n->right = NULL;
    
    // 3. 노드를 실제로 삽입
    if (p == NULL) {
        *root = n;
    } else if (key < p->data) {
        p->left = n;
    } else {
        p->right = n;
    }
}

int main(){
    TreeNode n1 = {3,NULL,NULL};
    TreeNode n2 = {12,NULL,NULL};
    TreeNode n3 = {7,&n1,&n2};
    TreeNode n4 = {27,NULL,NULL};
    TreeNode n5 = {31,&n4,NULL};
    TreeNode n6 = {26,NULL,&n5};
    TreeNode n7 = {18,&n3,&n6};
    TreeNode *exp = &n7;

    insert_node(&exp, 25);
    TreeNode *result = iter_search(exp, 25);
    printf("There is %d\n", result->data);
    
    return 0;
}