先頭へ戻る

二分探索木 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第8章

Programming Place Plus トップページ -- アルゴリズムとデータ構造編

先頭へ戻る

問題①

問題① 要素を昇順に追加した場合と、ランダムに追加した場合とで、探索性能がどの程度変わるか調べてください。


0~1000 の整数を、昇順に格納したときと、ランダムな順序で格納したときとで、これらの値を探索するために要する時間で比較してみます。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "bsearch_tree.h"
#include "ppp_perform.h"

#define VALUE_MAX  (1000)
#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

static BSearchTree add_linear_values(void);
static BSearchTree add_random_values(void);
static void search_values(BSearchTree tree);
static void random_shuffle(int* array, size_t size);

int main(void)
{
    srand( (unsigned int)time(NULL) );

    BSearchTree tree;

    tree = add_linear_values();
    PPP_CHECK_PERFORM_BEGIN(1000);
    search_values( tree );
    PPP_CHECK_PERFORM_END("linear");
    bsearch_tree_delete( tree );

    tree = add_random_values();
    PPP_CHECK_PERFORM_BEGIN(1000);
    search_values( tree );
    PPP_CHECK_PERFORM_END("random");
    bsearch_tree_delete( tree );

    return 0;
}

/*
    要素を昇順に追加する
*/
BSearchTree add_linear_values(void)
{
    BSearchTree tree = bsearch_tree_create();

    for( int i = 1; i <= VALUE_MAX; ++i ){
        bsearch_tree_add( tree, i );
    }

    return tree;
}

/*
    要素をランダムな順序で追加する
*/
BSearchTree add_random_values(void)
{
    static const int count = VALUE_MAX + 1;

    int* array = malloc(sizeof(int) * count);

    // 0~VALUE_MAX がランダムな順序で格納された配列を作る
    for( int i = 0; i < count; ++i ){
        array[i] = i;
    }
    random_shuffle( array, count );

    BSearchTree tree = bsearch_tree_create( array[0] );
    for( int i = 1; i < count; ++i ){
        bsearch_tree_add( tree, array[i] );
    }

    free( array );

    return tree;
}

/*
    要素を探索する
*/
void search_values(BSearchTree tree)
{
    for( int i = 0; i <= VALUE_MAX; ++i ){
        bsearch_tree_search( tree, i );
    }
}

/*
    配列の要素をランダムシャッフルする
*/
void random_shuffle(int* array, size_t size)
{
    for( size_t i = size; i > 1; --i ){
        size_t a = i - 1;
        size_t b = rand() % i;
        SWAP( int, array[a], array[b] );
    }
}

実行結果:

linear: 4.406000 seconds
random: 0.088000 seconds

1000回の試行で、実行結果にあるような違いが出ました。理論どおり、ランダムに追加された場合の方が、効率よく探索が行えるようです。

サンプルプログラムの中で、ランダムな順序で登録を行うために、値がランダムに格納された配列を用意しています。そのために、まず値が昇順に格納された配列を作り、これを random_shuffle関数でシャッフルしています。random_shuffle関数の実装については、【その他】第2章で解説しているので、そちらをご覧ください。

問題②

問題② 値の重複を許すような二分探索木を作成してください。


同じ値を重複して登録できるようにするには、二分探索木のルールを少し変えて、「左の子の値 ≦ 親の値 < 右の子の値」あるいは、「左の子の値 < 親の値 ≦ 右の子の値」にします。ここでは前者のルールを適用します。

本編で使ったプログラムの中で、要素を追加する bsearch_tree_add関数を書き換えると次のようになります。

/*
    二分探索木に要素を追加する
*/
bool bsearch_tree_add(BSearchTree tree, int value)
{
    assert(tree != NULL);

    struct BSNode_tag** p = &(tree->root);

    // 根から節を辿って、value を置いても二分探索木のルールを満たせる場所を探す
    while( *p != NULL ){
        if( (*p)->value < value ){
            p = &(*p)->right;
        }
        else{
            p = &(*p)->left;
        }
    }

    // この場所に節をつくる
    *p = malloc(sizeof(struct BSNode_tag));
    (*p)->value = value;
    (*p)->left = NULL;
    (*p)->right = NULL;

    // 1つ目の節のときは、根として登録
    if( tree->root == NULL ){
        tree->root = *p;
    }

    return true;
}

書き換え前のコードでは、追加しようとしている値と同じ値を持った節が見つかったとき、「return 0;」で終了させていました。書き換え後はこのコードがなくなり、追加しようとしている値の方が小さい場合と同じ処理へ分岐するようになります。

要素を削除する bsearch_tree_remove関数はどうすれば良いでしょう。

同じ値が重複している可能性があるので、どれを削除すれば良いのかという問題はありますが、どれを削除しても良いとするのなら、特に変更する箇所はありません。

あとは探索を行う bsearch_tree_search関数です。これも bsearch_tree_remove関数と同様に、同じ値が重複している場合に、どれを結果として返せばいいのかという問題があります。どれでも良いのであれば、特に変更する箇所はありません。

結局、bsearch_tree_add関数のわずかな変更だけで済みました。

ところで、同じ値が重複する場合、それらの節同士は近くに集まる訳ではありません。たとえば、10,5,10,15,10 という順番で要素を追加していった後で、二分探索木の中身を出力すると次のようになります。

NULL <-- 0 --> 10
5 <-- 10 --> 15
NULL <-- 5 --> 10
10 <-- 10 --> NULL
NULL <-- 10 --> NULL
NULL <-- 15 --> NULL

2行目の 10 の左の子が 5 ですが、5 の右の子が 10 になっています。したがって、この 2つの 10 は 5 を挟んだ位置関係にあります。何となく直観に反しているような感じがするかもしれませんが、内部的にはこういうことが起きます。


参考リンク


------------------------------------------------------------------------

更新履歴

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2012/7/29 新規作成。



第8章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー