search  ２分探索木におけるデータの探索
insert  ２分探索木におけるノードの挿入
delete  ２分探索木におけるノードの削除

２分探索木におけるデータの探索
    NODE *search(int key);

２分探索木におけるノードの挿入
    NODE *insert(int key);

２分探索木におけるノードの削除
    int delete(int key);

typedef struct _node {
    int key;               /* 比較のキーとなるフィールド */
    int info;              /* その他のフィールド */     
    struct _node *left;    /* 左側の子を指す */
    struct _node *right;   /* 右側の子を指す */
} NODE;

２分探索木におけるデータの探索関数において
    key   探索目標とするキーの値

２分探索木におけるノードの挿入関数において
    key   追加したいキーの値

２分探索木におけるノードの削除関数において
    key   削除したいキーの値

２分探索木におけるデータの探索関数について
    探索が成功したときは見つかったノードへのポインタ。
    失敗のときは NULL。

２分探索木におけるデータの挿入関数について
    挿入が成功したときは挿入したノードへのポインタ。
    挿入失敗のときや挿入しようとするキーが既にあったときは NULL。

２分探索木におけるデータの削除関数について
    削除が成功したときは 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;
}

２分探索木による探索は、ルートから始め、探索キーの値がそのノードの データより小さいか大きいかによって、左側または右側の子ノードをたど っていく。

完全につりのとれば２分探索木なら、n 個のものを調べるのに必要な比較回数 は O(log n) である。しかし、左右のバランスの悪い木では探索時間がか かり、最悪場合の計算量は O(n) である。

また、削除のプログラムがかなり複雑になってしまうことは、２分探索木 の特徴である。考えるべきケースとして、削除しようとするノードが

1. 左側に子ノードをもたない場合
   自分自身を右側の部分木で置き換える。つまり、親ノードから右側の 部分木にリンクを張り直す。
2. 左側に子ノードをもつ場合
   左側の部分木から最大のノードを探し出し、自分自身をそのノードで 置き換える。リンクの張り直しなど、いくつかの操作が必要である。

なお、２分探索木の性質上、同じ探索キーをもつノードは一つしかないの で、同じ探索キーに複数のデータをもつ場合はデータ構造中のinfoを工夫 する必要がある。