search  2분 탐색나무에 있어서의 데이터의 탐색
insert  2분 탐색나무에 있어서의 노드의 삽입
delete  2분 탐색나무에 있어서의 노드의 삭제

2분 탐색나무에 있어서의 데이터의 탐색
    NODE *search(int key);

2분 탐색나무에 있어서의 노드의 삽입
    NODE *insert(int key);

2분 탐색나무에 있어서의 노드의 삭제
    int delete(int key);

typedef struct _node {
    int key;               /* 비교의 키가 되는 필드 */
    int info;              /* 그 외의 필드 */     
    struct _node *left;    /* 좌측의 아이를 가리킨다 */
    struct _node *right;   /* 우측의 아이를 가리킨다 */
} NODE;

2분 탐색나무에 있어서의 데이터의 탐색 함수에 대해
    key   탐색 목표로 하는 키의 값

2분 탐색나무에 있어서의 노드의 삽입 함수에 대해
    key   추가하고 싶은 키의 값

2분 탐색나무에 있어서의 노드의 삭제 함수에 대해
    key   삭제하고 싶은 키의 값

2분 탐색나무에 있어서의 데이터의 탐색 함수에 대해
    탐색이 성공했을 때는 발견된 노드에의 포인터.
    실패 때는 NULL.

2분 탐색나무에 있어서의 데이터의 삽입 함수에 대해
    삽입이 성공했을 때는 삽입한 노드에의 포인터.
    삽입 실패 때나 삽입하려고 하는 키가 이미 있을 때는 NULL.

2분 탐색나무에 있어서의 데이터의 삭제 함수에 대해
    삭제가 성공했을 때는 0.
    삭제하려고 하는 키가 존재하고 있지 않을 때는 -1.

static NODE *root = NULL;

NODE *search(int key){
    NODE *node = root;

    while (node ! = NULL) {
        if (key == node->key) 
            return node;
        if (key < node->key) 
            node = node->left;
        else                 
            node = node->right;
    }
    return NULL;
}

NODE *insert(int key){
    NODE **node = &root;

    while (*node ! = NULL) {
        if (key == (*node)->key) return NULL;
        if (key < (*node)->key) node = &((*node)->left);
        else                    node = &((*node)->right);
    }
    if ((*node = (NODE *) malloc(sizeof(NODE))) == NULL) return NULL;
    (*node)->key  = key;
    (*node)->left = (*node)->right = NULL;
    return (*node);
}

int delete(int key){
    NODE **node = &root;
    NODE *next, **leftmax, *tmp;

    for (;;) {
        if (*node == NULL) return -1;
        if (key == (*node)->key) break;
        if (key < (*node)->key) node = &((*node)->left);
        else                    node = &((*node)->right);
    }
    
    if ((*node)->left == NULL) 

        next = (*node)->right;
    else {
        leftmax = &((*node)->left);
        while ((*leftmax)->right ! = NULL)
            leftmax = &((*leftmax)->right);
        next = *leftmax;
        *leftmax = (*leftmax)->left;
        next->left  = (*node)->left;
        next->right = (*node)->right;
    }
    tmp = *node;
    *node = next;
    free(tmp);
    return 0;
}

2분 탐색나무에 의한 탐색은, 루트로부터 시작해 탐색 키의 값이 그 노드의 데이터보다 작은가 큰 것처럼 따라, 좌측 또는 우측의 아이 노드 라고 간다.

완전하게 낚시가 취하면 2분 탐색나무라면, n 개의 것을 조사하는데 필요한 비교 회수 (은)는 O(log n)이다. 그러나, 좌우의 밸런스가 나쁜 나무에서는 탐색 시간이인가 빌려 최악 경우의 계산량은 O(n)이다.

또, 삭제의 프로그램이 꽤 복잡하게 되어 버리는 것은, 2분 탐색나무 의 특징이다. 생각해야 할 케이스로서 삭제하려고 하는 노드가

1. 좌측으로 아이 노드를 갖지 않는 경우
   자기 자신을 우측의 부분나무로 옮겨놓는다. 즉, 친노드로부터 우측의 부분나무에 다시 링크한다.
2. 좌측으로 아이 노드를 가지는 경우
   좌측의 부분나무로부터 최대의 노드를 찾아내, 자기 자신을 그 노드로 옮겨놓는다. 링크의 의욕 수선 등, 몇개의 조작이 필요하다.

덧붙여 2분 탐색나무의 성질상, 같은 탐색 키를 가지는 노드는 1개 밖에 없는거야 그리고, 같은 탐색 키에 복수의 데이터를 가지는 경우는 데이터 구조중의 info를 궁리 할 필요가 있다.