二分探索木
今回は簡単な例題として「二分探索木 (binary search tree)」を取り上げます。二分探索木は「木構造 (tree structer)」または「木 (tree)」と呼ばれるデータ構造の一種です。最初に木について簡単に説明します。
●木構造
木は「節 (ノード)」と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。下図を見てください。
図 : 一般的な木構造の一例
木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。
木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。
ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J, K の親で、J は G の子になります。J は子を持っていないので葉となります。
子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「 n 分木」と呼びます。
●二分木
特に、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。
図 : 二分木の一例
上図に二分木の例を示します。二分木では、節に一つのデータを格納します。そして、その節の左側の子には小さいデータが、右側の子には大きいデータが配置されるように木を構成します。
この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。
二分探索木の探索は「二分探索」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。
データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。
ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。そこで、左右のバランスを一定の範囲に収める「平衡木 (balanced tree)」が考案されています。有名なところでは AVL 木、赤黒木、AA 木、2-3 木、B 木、B* 木などがあります。
●節の定義
それではプログラムを作りましょう。まず最初に、節を表す構造体を定義します。
リスト : 節の定義
// 節の定義
typedef struct node {
double item;
struct node *left;
struct node *right;
} Node;
// 節の生成
static Node *make_node(double x)
{
Node *node = malloc(sizeof(Node));
if (node != NULL) {
node->item = x;
node->left = NULL;
node->right = NULL;
}
return node;
}
連結リストと違い、節へのポインタが 2 つ必要になります。left が左の子、right が右の子を表します。子を持たない場合は、連結リストと同様に NULL をセットすることにします。二分木に格納するデータ item の型は double とします。関数 make_node は malloc で節本体のメモリを取得し、item を引数 x に、left と right を NULL に初期化します。
連結リストのように、節を箱で表すと下図のようになります。
図 : 二分木の構造
連結リストと同様に、ルートへの参照を変数 root に格納しておけば、この変数を使って二分木にアクセスすることができます。また、節が一つもない空の木は、変数 root に NULL をセットすれば表すことができます。なお、NULL のかわりに終端を表す節を用意する方法もあります。
今回は節 (Node) のほかに、root を格納する構造体 Tree を定義することにします。そして、節を操作する関数 (xxx_node) を static 宣言し、ユーザに公開するのは Tree を操作する関数 (xxx_tree) だけに限定します。分割コンパイルできるように、ソースファイルは tree.h と tree.c に分けて記述します。
●データの探索
それでは、データを探索する関数 search_node から作りましょう。次のリストを見てください。
リスト : データの探索
static bool search_node(double x, Node *node)
{
while (node != NULL) {
if (node->item == x)
return true;
else if (x < node->item)
node = node->left;
else
node = node->right;
}
return false;
}
関数 search_node には節 node と探索するデータ x を渡します。x と node->item を比較し、値が等しければ true を返します。x が小さいのであれば左の子をたどり、そうでなければ右の子をたどります。たどるべき木がなくなれば node の値は NULL になるので、while ループを終了し false を返します。二分探索木の動作をそのままプログラムしているだけなので、難しいところはないと思います。
●データの挿入
次は、データを挿入する関数 insert_node を作ります。この関数は木を引数として受け取り、データを挿入した新しい木を返します。たとえば、変数 root に木が格納されている場合、データを挿入するときは次のように呼び出します。
root = insert_node(x, root)
この処理は再帰定義を使うと簡単にプログラムできます。次のリストを見てください。
リスト : データの挿入
static Node *insert_node(double x, Node *node)
{
if (node == NULL)
return make_node(x);
else if (x < node->item)
node->left = insert_node(x, node->left);
else if (x > node->item)
node->right = insert_node(x, node->right);
return node;
}
最初に節 node が NULL かチェックします。そうであれば木は空なので、新しい節を make_node(x) で生成して返します。たとえば、変数 root が NULL の場合、すなわち空の木であれば、新しい節が生成されて root にセットされます。
そうでなければ、x と node->item を比較します。x と等しいデータが見つかった場合は、新しいデータを挿入する必要はないので、何も行わずに node を返します。x が小さい場合は、左部分木に x を挿入します。ここで関数 insert_node を再帰呼び出しします。そして、返り値を node->left にセットして node を返します。
たとえば、node->left が NULL の場合、再帰呼び出しの返り値は新しい節なので、それが node->left にセットされ、木にデータが挿入されたことになります。そして、新しいデータが挿入された木 (node) を返せばいいわけです。x が item よりも大きければ、同様に右部分木にデータを挿入します。
けっきょく、子を格納している節には、同じ子が再度セットされることになります。無駄なように思われるかもしれませんが、その分だけ簡単にプログラムを作ることができます。
●データの削除
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
図 : データの削除（葉の場合）
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。親の left に NULL を代入するだけです。
次に、子が一つある場合を考えてみましょう。
図 : データの削除 (子が一つの場合)
16 を削除する場合、その子である 15 と置き換えれば二分探索木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。
図 : データの削除 (子が二つの場合)
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。上図で、14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
[*1] 逆に、左部分木の中から最大値を探し、それと削除するデータを置き換えてもかまいません。
●最小値の探索と削除
まず、木の中から最小値を探す関数と、最小値の節を削除する関数を作りましょう。次のリストを見てください。
リスト : 最小値の探索と削除
// 最小値の探索
static double search_min(Node *node)
{
while (node->left != NULL) node = node->left;
return node->item;
}
// 最小値の削除
static Node *delete_min(Node *node)
{
if (node->left == NULL) {
Node *temp = node->right;
free(node);
return temp;
}
node->left = delete_min(node->left);
return node;
}
最小値は簡単に求めることができます。左の子を順番にたどっていき、左の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search_min は、最小値を求めてそれを返します。最初に、node->left の値をチェックします。もし、NULL であれば左の子がないので、その節のデータが最小値です。return で node->item を返します。そうでなければ、search_min を再帰呼び出しして左の子をたどります。
関数 delete_min は最小値を格納している節を削除します。node->left が NULL の節を探すのは search_min と同じです。見つけた場合、一時変数 temp に node->right をセットして、削除する node を free で解放します。最後に temp を返します。これで、親の左部分木が書き換えられ、最小値を持つ節が削除されます。葉の場合であれば node->right は NULL なので、単純に削除されることになります。
左の子があれば delete_min を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を node->left にセットして、return で node を返します。
●データ削除のプログラム
それでは、データを削除する関数 delete_node を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
static Node *delete_node(double x, Node *node)
{
if (node == NULL) return NULL;
if (x == node->item) {
if (node->left == NULL) {
Node *temp = node->right;
free(node);
return temp;
}
if (node->right == NULL) {
Node *temp = node->left;
free(node);
return temp;
}
node->item = search_min(node->right);
node->right = delete_min(node->right);
} else if (x < node->item)
node->left = delete_node(x, node->left);
else
node->right = delete_node(x, node->right);
return node;
}
まず、node が NULL ならば木は空なので、何もしないで NULL を返します。削除するデータが見つからない場合や空の木を与えた場合がこれに相当します。次に、削除するデータ x と node->item を比較します。等しい場合はその節を削除します。node->left が NULL の場合は node->right を返し、node->right が NULL の場合は node->left を返します。
子が 2 つある場合は、右部分木の最小値を関数 search_min で求め、node->item の値を書き換えます。そして、関数 delete_min で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換え、不要になった節を二分木から削除することができます。x と item が等しくない場合は、左右の部分木をたどって削除するデータを探索します。最後に node を返します。
●巡回 (traverse)
最後に、二分木のすべての要素にアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
- 行きがけ順
まず節のデータを出力、その後左の子、右の子の順番で出力する。 - 帰りがけ順
左の子、右の子と出力してから、節のデータを出力する。 - 通りがけ順
左の子を出力、次に節のデータを出力、最後に右の子を出力する。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理も、再帰定義を使えば簡単に実現できます。次のリストを見てください。
リスト : 木の巡回
static void foreach_node(void (*func)(double), Node *node)
{
if (node != NULL) {
foreach_node(func, node->left);
func(node->item);
foreach_node(func, node->right);
}
}
関数 foreach_node は高階関数で、通りがけ順で木を巡回します。node が NULL でなければ、再帰呼び出しで左部分木を巡回してから関数 func(node->item) を実行し、そのあとで右部分木を巡回します。たとえば、次に示すようにデータを出力する関数を引数 func に与えれば、二分木のデータを昇順に表示することができます。
リスト : 要素の表示
void print_item(double x)
{
printf("%.3f ", x);
}
●構造体 Tree と操作関数の定義
最後に、構造体 Tree と操作関数を定義します。Tree の操作関数を下表に示します。
| 関数名 | 機能 |
|---|---|
| Tree *make_tree(void); | 空の二分木を生成する |
| void destroy_tree(Tree *tree); | tree を廃棄する |
| bool search_tree(double x, Tree *tree); | tree から x を探索する |
| double search_min_tree(Tree *tree, bool *err) | tree の最小値を求める |
| double search_max_tree(Tree *tree, bool *err) | tree の最大値を求める |
| void insert_tree(double x, Tree *tree); | tree に x を挿入する |
| void delete_tree(double x, Tree *tree); | tree から x を削除する |
| void delete_min_tree(Tree *tree, bool *err); | tree の最小値を削除する |
| void delete_max_tree(Tree *tree, bool *err); | tree の最大値を削除する |
| void foreach_tree(void (*func)(double), Tree *tree); | tree を巡回して、要素を関数 func に渡して呼び出す |
| bool is_empty_tree(Tre *tree); | tree が空ならば真を返す |
Tree の定義と主な操作関数は次のようになります。
リスト : 構造体 Tree と操作関数の定義
// 木の定義
typedef struct {
Node *root;
} Tree;
// 木の生成
Tree *make_tree(void)
{
Tree *tree = malloc(sizeof(Tree));
if (tree != NULL) {
tree->root = NULL;
}
return tree;
}
// データの探索
bool search_tree(double x, Tree *tree)
{
return search_node(x, tree->root);
}
// データの挿入
void insert_tree(double x, Tree *tree)
{
tree->root = insert_node(x, tree->root);
}
// データの削除
void delete_tree(double x, Tree *tree)
{
tree->root = delete_node(x, tree->root);
}
Tree のメンバ変数は root で、これが二分木の根 (ルート) になります。あとは、処理に対応する操作関数を呼び出すだけです。
二分木を廃棄するときは関数 destory_tree を呼び出します。
リスト : 二分木の廃棄
// 節の廃棄
static void destroy_node(Node *node)
{
if (node != NULL) {
destroy_node(node->left);
destroy_node(node->right);
free(node);
}
}
// 木の廃棄
void destroy_tree(Tree *tree)
{
destroy_node(tree->root);
free(tree);
}
destroy_tree は関数 destory_node を呼び出して節を廃棄し、そのあとで tree を free で解放します。destory_node は traverse とほぼ同じ処理で、node が NULL でなければ、左部分木と右部分木を destory_node で廃棄してから node 本体を free で解放します。
あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト をお読みください。
●簡単なテスト
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
リスト : 簡単なテスト
#define N 10
void test1(void)
{
double buff[N] = {5,6,4,7,3,8,2,9,1,0};
Tree *tree = make_tree();
for (int i = 0; i < N; i++) {
insert_tree(buff[i], tree);
print_tree(tree);
}
for (int i = -1; i < N + 1; i++)
printf("%d\n", search_tree(i, tree));
for (int i = 0; i < N; i++) {
delete_tree(buff[i], tree);
print_tree(tree);
}
destroy_tree(tree);
}
int main(void)
{
test1();
return 0;
}
実行結果を示します。
$ clang -O2 main.c tree.c $ ./a.out 5.000 5.000 6.000 4.000 5.000 6.000 4.000 5.000 6.000 7.000 3.000 4.000 5.000 6.000 7.000 3.000 4.000 5.000 6.000 7.000 8.000 2.000 3.000 4.000 5.000 6.000 7.000 8.000 2.000 3.000 4.000 5.000 6.000 7.000 8.000 9.000 1.000 2.000 3.000 4.000 5.000 6.000 7.000 8.000 9.000 0.000 1.000 2.000 3.000 4.000 5.000 6.000 7.000 8.000 9.000 0 1 1 1 1 1 1 1 1 1 1 0 0.000 1.000 2.000 3.000 4.000 6.000 7.000 8.000 9.000 0.000 1.000 2.000 3.000 4.000 7.000 8.000 9.000 0.000 1.000 2.000 3.000 7.000 8.000 9.000 0.000 1.000 2.000 3.000 8.000 9.000 0.000 1.000 2.000 8.000 9.000 0.000 1.000 2.000 9.000 0.000 1.000 9.000 0.000 1.000 0.000
正常に動作していますね。
●簡単なテスト (2)
次は、挿入、探索、削除の実行時間と、二分木の高さを求めてみましょう。二分木の高さ求める関数 height_tree は次のようになります。
リスト : 木の高さ
int height_node(Node *node)
{
if (node == NULL) return 0;
int a = height_node(node->left);
int b = height_node(node->right);
return 1 + (a > b ? a : b);
}
int height_tree(Tree *tree)
{
return height_node(tree->root);
}
実際の処理は関数 height_node で行います。引数 node が NULL ならば 0 を返します。次に、height_node を再帰呼び出しして、右部分木と左部分木の高さを求めます。あとは、大きいほうの値に 1 を足して返すだけです。これで二分木の高さを求めることができます。
テストプログラムは次のようになります。
リスト : 簡単なテスト (2)
#define M 2000000
double buff[M];
void test2(void)
{
for (int n = 250000; n <= M; n *= 2) {
Tree *tree = make_tree();
for (int i = 0; i < n; i++) buff[i] = rand();
shuffle(buff, n);
printf("----- %d -----\n", n);
clock_t s = clock();
for (int i = 0; i < n; i++)
insert_tree(buff[i], tree);
printf("挿入時間 %.3f\n", (double)(clock() - s) / CLOCKS_PER_SEC);
printf("高さ %d\n", height_tree(tree));
s = clock();
for (int i = 0; i < n; i++)
if (!search_tree(buff[i], tree)) fprintf(stderr, "search error\n");
printf("探索時間 %.3f\n", (double)(clock() - s) / CLOCKS_PER_SEC);
s = clock();
for (int i = 0; i < n; i++)
delete_tree(buff[i], tree);
printf("削除時間 %.3f\n", (double)(clock() - s) / CLOCKS_PER_SEC);
destroy_tree(tree);
}
}
0 から n - 1 までのデータを配列 buff に格納し、関数 shuffle でシャッフルします。あとは、二分木 tree に挿入する時間、探索する時間、削除する時間を計測します。このとき、二分木の高さを height_tree で求めます。実行結果は次のようになりました。
表 : 実行結果 (単位 : 秒)
個数 : 挿入 探索 削除 高さ (log2 N)
-----------------------------------------
250000 : 0.135 0.108 0.112 44 (18)
500000 : 0.427 0.345 0.329 49 (19)
1000000 : 1.070 0.976 0.910 51 (20)
2000000 : 2.713 2.518 2.358 54 (21)
実行環境 : clang version 14.0.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
最適化オプション : -O2
データの挿入が一番遅くなりました。データ数が多くなると探索よりも削除のほうが少しだけ速くなりました。データを挿入したときと同じ順番で削除しているので、それが影響しているのかもしれません。
二分木の高さは log2 N の約 2.5 倍ほど高くなりました。まあ、コンピュータで扱う乱数は「擬似乱数」なので、二分木のバランスが崩れるのはしょうがないでしょう。AVL 木などの平衡木を使うと、木の高さをもっと低く抑えることができるので、データの探索はもう少し速くなります。興味のある方は拙作のページ Algorithms with Python AVL 木 [1], [2] をお読みください。ほかにも、2-3 木と赤黒木を説明しています。
●プログラムリスト
/*
* tree.h : 二分探索木
*
* Copyright (C) 2015-2023 Makoto Hiroi
*/
#ifndef _TREE_H_
#define _TREE_H_
#include <stdlib.h>
#include <stdbool.h>
// 節の定義
typedef struct node {
double item;
struct node *left;
struct node *right;
} Node;
// 木の定義
typedef struct {
Node *root;
} Tree;
// 関数宣言
Tree *make_tree(void);
void destroy_tree(Tree *tree);
bool is_empty_tree(Tree *tree);
bool search_tree(double x, Tree *tree);
double search_min_tree(Tree *tree, bool *err);
double search_max_tree(Tree *tree, bool *err);
void insert_tree(double x, Tree *tree);
void delete_tree(double x, Tree *tree);
void delete_min_tree(Tree *tree);
void delete_max_tree(Tree *tree);
void foreach_tree(void (*func)(double), Tree *tree);
#endif
/*
* tree.c : 二分探索木
*
* Copyright (C) 2015-2023 Makoto Hiroi
*/
#include "tree.h"
// 節の生成
static Node *make_node(double x)
{
Node *node = malloc(sizeof(Node));
if (node != NULL) {
node->item = x;
node->left = NULL;
node->right = NULL;
}
return node;
}
// 節の廃棄
static void destroy_node(Node *node)
{
if (node != NULL) {
destroy_node(node->left);
destroy_node(node->right);
free(node);
}
}
// データの探索
static bool search_node(double x, Node *node)
{
while (node != NULL) {
if (node->item == x)
return true;
else if (x < node->item)
node = node->left;
else
node = node->right;
}
return false;
}
// データの挿入
static Node *insert_node(double x, Node *node)
{
if (node == NULL)
return make_node(x);
else if (x < node->item)
node->left = insert_node(x, node->left);
else if (x > node->item)
node->right = insert_node(x, node->right);
return node;
}
// 最小値の探索
static double search_min(Node *node)
{
while (node->left != NULL) node = node->left;
return node->item;
}
// 最大値の探索
static double search_max(Node *node)
{
while (node->right != NULL) node = node->right;
return node->item;
}
// 最小値の削除
static Node *delete_min(Node *node)
{
if (node->left == NULL) {
Node *temp = node->right;
free(node);
return temp;
}
node->left = delete_min(node->left);
return node;
}
// 最大値の削除
static Node *delete_max(Node *node)
{
if (node->right == NULL) {
Node *temp = node->left;
free(node);
return temp;
}
node->right = delete_max(node->right);
return node;
}
// データの削除
static Node *delete_node(double x, Node *node)
{
if (node == NULL) return NULL;
if (x == node->item) {
if (node->left == NULL) {
Node *temp = node->right;
free(node);
return temp;
}
if (node->right == NULL) {
Node *temp = node->left;
free(node);
return temp;
}
node->item = search_min(node->right);
node->right = delete_min(node->right);
} else if (x < node->item)
node->left = delete_node(x, node->left);
else
node->right = delete_node(x, node->right);
return node;
}
// 巡回
static void foreach_node(void (*func)(double), Node *node)
{
if (node != NULL) {
foreach_node(func, node->left);
func(node->item);
foreach_node(func, node->right);
}
}
//
// 公開する関数
//
// 木の生成
Tree *make_tree(void)
{
Tree *tree = malloc(sizeof(Tree));
if (tree != NULL) {
tree->root = NULL;
}
return tree;
}
// 木の廃棄
void destroy_tree(Tree *tree)
{
destroy_node(tree->root);
free(tree);
}
// 空の木か
bool is_empty_tree(Tree *tree)
{
return tree->root == NULL;
}
// データの探索
bool search_tree(double x, Tree *tree)
{
return search_node(x, tree->root);
}
// 最小値を求める
double search_min_tree(Tree *tree, bool *err)
{
if (is_empty_tree(tree)) {
*err = false;
return 0;
}
*err = true;
return search_min(tree->root);
}
// 最大値を求める
double search_max_tree(Tree *tree, bool *err)
{
if (is_empty_tree(tree)) {
*err = false;
return 0;
}
*err = true;
return search_max(tree->root);
}
// データの挿入
void insert_tree(double x, Tree *tree)
{
tree->root = insert_node(x, tree->root);
}
// データの削除
void delete_tree(double x, Tree *tree)
{
tree->root = delete_node(x, tree->root);
}
// 最小値を削除
void delete_min_tree(Tree *tree)
{
if (!is_empty_tree(tree))
tree->root = delete_min(tree->root);
}
// 最大値を削除
void delete_max_tree(Tree *tree)
{
if (!is_empty_tree(tree))
tree->root = delete_max(tree->root);
}
// 巡回
void foreach_tree(void (*func)(double), Tree *tree)
{
foreach_node(func, tree->root);
}
リスト : main.c
#include <stdio.h>
#include <time.h>
#include "tree.h"
// データの表示
void print_item(double x)
{
printf("%.3f ", x);
}
void print_tree(Tree *tree)
{
foreach_tree(print_item, tree);
printf("\n");
}
// 木の高さ
int height_node(Node *node)
{
if (node == NULL) return 0;
int a = height_node(node->left);
int b = height_node(node->right);
return 1 + (a > b ? a : b);
}
int height_tree(Tree *tree)
{
return height_node(tree->root);
}
// シャッフル
void shuffle(double *buff, int size)
{
for (int i = size - 1; i > 0; i--) {
int j = rand() % (i + 1);
double tmp = buff[i];
buff[i] = buff[j];
buff[j] = tmp;
}
}
#define N 10
void test1(void)
{
double buff[N] = {5,6,4,7,3,8,2,9,1,0};
Tree *tree = make_tree();
for (int i = 0; i < N; i++) {
insert_tree(buff[i], tree);
print_tree(tree);
}
for (int i = -1; i < N + 1; i++)
printf("%d\n", search_tree(i, tree));
for (int i = 0; i < N; i++) {
delete_tree(buff[i], tree);
print_tree(tree);
}
destroy_tree(tree);
}
#define M 2000000
double buff[M];
void test2(void)
{
for (int n = 250000; n <= M; n *= 2) {
Tree *tree = make_tree();
for (int i = 0; i < n; i++) buff[i] = rand();
printf("----- %d -----\n", n);
clock_t s = clock();
for (int i = 0; i < n; i++)
insert_tree(buff[i], tree);
printf("挿入時間 %.3f\n", (double)(clock() - s) / CLOCKS_PER_SEC);
printf("高さ %d\n", height_tree(tree));
s = clock();
for (int i = 0; i < n; i++)
if (!search_tree(buff[i], tree)) fprintf(stderr, "search error\n");
printf("探索時間 %.3f\n", (double)(clock() - s) / CLOCKS_PER_SEC);
s = clock();
for (int i = 0; i < n; i++)
delete_tree(buff[i], tree);
printf("削除時間 %.3f\n", (double)(clock() - s) / CLOCKS_PER_SEC);
destroy_tree(tree);
}
}
int main(void)
{
test1();
test2();
return 0;
}
改訂 2023 年 4 月 2 日