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

#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] );
    }
}

/*
    二分探索木に要素を追加する
*/
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;

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

    return true;
}