二分探索木

C

http://www.geocities.jp/ky_webid/algorithm/017.html

前回の二分木構造の続きですね。

構造は二分木と同じだが、「左の子 ≤ 親 ≤ 右の子」という制約を持つ。左の子と右の子の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。

平衡（左右のバランスがとれている状態）している状態では木の高さは O(log2 N) となる。ただし最悪の場合は、事実上の 線形リスト になり、木の高さは O(N) となる。木の形は挿入時のデータ出現順序に依存し、特にソート済みのデータを与えると線形リストになる点は注意を要する。データの出現順序によって大きく性能が劣化しないように、挿入・削除の際に木の平衡を取り直す処理を追加した2分探索木は平衡2分探索木と呼ばれる。

二分探索木 - Wikipedia

振り分けの処理を「左の子 ≤ 親 ≤ 右の子」とすることで検索のしやすさをアップさせてるわけですね。場合によっては便利そうです。

ノードの追加や探索は割と簡単に実装できそうですが、削除はどうやら難しいみたいです。

探索、挿入に比べると、削除の処理は少し複雑な手順となる。

  1. ルートから手順を開始する。
  2. 着目しているノードと目的の値を比較する。「目的の値 < 着目しているノード」なら左の子、「着目しているノード ≤ 目的の値」なら右の子が、次に着目するノードとなる。
  3. 着目ノードが削除する対象（以下、削除ノード）であり、削除ノードが子どもを持たないなら、そのノードをそのまま削除する。
  4. 削除ノードが子どもを一つしかもっていない場合は、削除ノードを削除してその子どもと置き換える。
  5. 削除ノードが子どもを二つ持つ場合
    1. 削除ノードの左の子から最大の値を探索する。
    2. 1 で探索してきたノード（以下、探索ノード）を削除対象のノードと置き換えて、削除対象のノードを削除する。このとき探索ノードの左の子を探索ノードの元位置に置き換える（2分探索木の性質上、探索ノードには右の子は無い）。


5-1 で行う操作は「右の子から最小の値を探索する」でも良い。この場合は 5-2 の操作は探索ノードの右の子を探索ノードの元位置に置き換えることになる。

二分探索木 - Wikipedia

できるでしょうか・・・ちょっと不安ですが、実装してみます。

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

struct NODE {
    int data;
    struct NODE *left;
    struct NODE *right;
};
typedef struct NODE NODE;

NODE *create_node(int data);
void create_tree(NODE **root);
NODE *delete_max(NODE **root);
void del_node(NODE **root,int data);
void preorder(NODE *n);
void inorder(NODE *n);
void postorder(NODE *n);

NODE *create_node(int data) {
    NODE *p;
    p = (NODE *)malloc(sizeof(NODE));
    if ( p == NULL ) {
        return NULL;
    }
    p->left  = NULL;
    p->right = NULL;
    p->data  = data;
    return p;
}

void add_node(NODE **root,int data){
    NODE *node,*prev;
    
    if ( *root == NULL ) {
        *root = create_node(data);
        return;
    }
    
    prev = node = *root;
    while ( node != NULL ) {
        prev = node;
        node = node->data <= data ? node->right : node->left;
    }
    
    if ( prev->data <= data ) {
        prev->right = create_node(data);
    }
    else {
        prev->left = create_node(data);
    }
}

NODE *search_node(NODE **root,int data){
    NODE *node = *root;
    
    while ( node != NULL ) {
        if ( node->data == data ) { break; }
        node = node->data < data ? node->right : node->left;
    }
    
    return node;
}

NODE *delete_max(NODE **root){
    NODE *max;
    
    while ( (*root)->right != NULL ) {
        // 後で変更するためにアドレスを新たに取得しながら進む
        root = &(*root)->right;
    }
    
    max = *root;
    
    // 最大値に紐付いてるデータをずらす
    *root = (*root)->left;
    
    return max;
}

void del_node(NODE **root,int data){
    NODE *node;
    NODE *prev;
    NODE **plr;
    
    prev = node = *root;
    while ( node != NULL ) {
        if ( node->data == data ) { break; }
        prev = node;
        node = node->data < data ? node->right : node->left;
    }
    
    if ( node == NULL ) {
        // 削除対象が見つからなかった
        return;
    }
    
    // 前のデータの右左どちらからの派生か保存
    if ( node != *root ) {
        plr = prev->data <= data ? &prev->right : &prev->left;
    }
    else {
        plr = root;
    }
    
    if ( node->left == NULL ) {
        if ( node->right != NULL ) {
            // 右の子ノードが一つだけ
            *plr = node->right;
        }
        else {
            *plr = NULL;
        }
    }
    else if ( node->right == NULL ) {
        if ( node->left != NULL ) {
            // の子ノードが一つだけ左
            *plr = node->left;
        }
        else {
            *plr = NULL;
        }
    }
    else {
        // 子ノードが二つある場合
        *plr = delete_max(&node->left);
        
        // 再紐付け
        (*plr)->right = node->right;
        (*plr)->left = node->left;
    }
    
    // 解放
    free(node);
    node = NULL;
}

void preorder(NODE *n){
    if( n == NULL ){ return; }
    printf( "%2d ", n->data );
    preorder( n->left );
    preorder( n->right );
}

void inorder(NODE *n){
    if( n == NULL ){ return; }
    inorder( n->left );
    printf( "%2d ", n->data );
    inorder( n->right );
}

void postorder(NODE *n){
    if( n == NULL ){ return; }
    postorder( n->left );
    postorder( n->right );
    printf( "%2d ", n->data );
}

int main (void) {
    NODE *root = NULL;
    NODE *node = NULL;
    
    int i;
    int num[] = {8,3,10,1,6,7,4,14,13};
    int sea[] = {8,3,10,1,6,7,4,14,100,0,5,13};
    
    for(i=0;i<ARRAY_NUM(num);++i){
        add_node(&root,num[i]);
    }
    
    // ノードの削除
    del_node(&root,8);
    
    for(i=0;i<ARRAY_NUM(sea);++i){
        node = search_node(&root,sea[i]);
        if ( node != NULL ) {
            printf("found => %d\n",node->data);
        }
        else {
            printf("not found => %d\n",sea[i]);
        }
    }
    
    printf("\npreorder  : ");
    preorder(root);
    
    printf("\ninorder   : ");
    inorder(root);
    
    printf("\npostorder : ");
    postorder(root);
    
    return 0;
}

$ main
not found => 8
found => 3
found => 10
found => 1
found => 6
found => 7
found => 4
found => 14
not found => 100
not found => 0
not found => 5
found => 13

preorder  :  7  3  1  6  4 10 14 13
inorder   :  1  3  4  6  7 10 13 14
postorder :  1  4  6  3 13 14 10  7

※mylib.h

めちゃくちゃ時間かかりました。delete_max関数に関して少しカンニングした以外は全て自分で実装しました。今までで一番難しい処理でしたね。

少しはC言語でプログラム組めるようになってきたのかな・・。まだちょっと自信無いですが、この調子で今後とも頑張っていきたいと思います。