二分探索木
あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに探索しても何とかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。
この代表的なアルゴリズムに「ハッシュ法」と「二分探索木」があります。今回は二分探索木を Prolog で実装してみましょう。最初に「木構造 (tree structer)」について簡単に説明します。
●木構造
木は節 (ノード) と呼ばれる要素に対して、階層的な関係 (親子関係) を表したデータ構造です。身近な例では、ディレクトリ (フォルダ) の階層構造が木にあたります。ディレクトリにルートディレクトリがあるように、木にも「根 (ルート)」と呼ばれる節が存在します。次の図を見てください。
図 : 一般的な木構造の一例
木を図示する場合、階層関係がはっきりわかるように、根を上にして同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木はある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。
木はある節から他の節に至る経路を考えることができます。たとえば、A から J には A - B - G - J という経路がありますね。これはディレクトリやファイルを指定するときのパスと同じです。
ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J, K の親で、J は G の子になります。J と K は子を持っていないので葉となります。
●二分木
子は「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番が無い木を「無順序木」と呼びます。そして、節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を N に揃えた順序木を「N 分木」と呼びます。特に次数が 2 の「二分木」は、プログラムでよく使われるデータ構造です。
図 : 二分木の一例
上図に二分木の例を示します。二分木では、節に一つのデータを格納します。そして、その節の左側の子には小さいデータ、右側の子には大きいデータが配置されるように木を構成します。
二分木はデータの探索、挿入、削除を高速に行うことができるデータ構造です。たとえば、上図の二分木から 19 を探してみましょう。まず、root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。
二分木の探索は二分探索と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。したがって、データ数を N とすると、線形探索では平均で N / 2 回の比較が必要になりますが、二分木を使うと log2 N 程度の回数で収まります。たとえば、データが 100 個ある場合、線形探索では平均で 50 回データを比較しなければいけないのに、二分木では高々 7 回の比較で済むわけです。
ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されていますが、今回は木構造の例題として単純な二分木を取り上げます。
●データ構造
Prolog の場合、二分木はリストを使って表すことができます。リストの先頭がデータで、次が左側の子、最後に右側の子を格納します。子がない場合は void を格納することにすると、図の二分木は次のように表すことができます。
[18,
[14,
[12,
[11, void, void].
[13 void, void] ],
[16,
[15, void, void],
[17, void, void] ] ],
[22,
[20,
[19, void, void],
[21, void, void] ],
[24,
[23, void, void],
[25, void, void] ] ] ]
図 : 二分木をリストで表した場合
このように、リストを使えば二分木でも多分木でも作れるのですが、このリストを見ただけでは、それが二分木を表していると理解するのは困難です。そこで、データ型と型述語 で簡単に説明した「複合項」を使って二分木を表すことにしましょう。
複合項の基本的な形式は、次のようになります。
func(arg1, arg2, ... argN)
func を「ファンクタ (functor,関数子)」といいます。複合項は、ファンクタと引数の個数 (アリティ,arity) で定められます。述語と同じ形式になっているところが、ちょっとややこしいところです。述語は物事の関係を表し、複合項はデータ構造を表していることに注意してください。二分木の節 (node) を複合項で表すと、次のようになります。
node(X, Ls, Rs)
X にデータが入り、Ls には左側の子、Rs には右側の子が入ります。簡単な二分木とその複合項を図に表すと、次のようになります。
●データの探索
二分木からデータを探すことは、とても簡単にプログラムできます。
リスト : 探索 search_tree(X, node(Y, Ls, _)) :- X < Y, search_tree(X, Ls). search_tree(X, node(Y, _, Rs)) :- X > Y, search_tree(X, Rs). search_tree(X, node(X, _, _)).
最後の規則がデータを見つけた場合です。最初の規則で、X が Y よりも小さければ左の部分木をたどり、次の規則で X が Y よりも大きければ右の木をたどります。二分木の定義そのままのプログラムですね。
簡単な実行例を示します。
?- search_tree(5, node(5,node(3,void,void),node(7,void,void))). true. ?- search_tree(3, node(5,node(3,void,void),node(7,void,void))). true ; false. ?- search_tree(7, node(5,node(3,void,void),node(7,void,void))). true ; false. ?- search_tree(4, node(5,node(3,void,void),node(7,void,void))). false. ?- search_tree(1, node(5,node(3,void,void),node(7,void,void))). false. ?- search_tree(9, node(5,node(3,void,void),node(7,void,void))). false.
●最小値と最大値の探索
二分木の場合、最小値と最大値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。逆に、右側の子を順番にたどり、右側の子がない節に行き着いたとき、その節のデータが最大値になります。
プログラムは次のようになります。
リスト : 最小値と最大値の探索 search_min_tree(node(X, void, _), X). search_min_tree(node(_, Ls, _), X) :- search_min_tree(Ls, X). search_max_tree(node(X, _, void), X). search_max_tree(node(_, _, Rs), X) :- search_max_tree(Rs, X).
述語 search_min_tree は最小値を求めます。最初の規則で左の子が void であれば、その節のデータ X が最小値になります。そうでなければ、次の規則で search_min_tree を再帰呼び出しして左の子 Ls をたどります。
述語 search_max_tree は最大値を求めます。最初の規則で右の子が void であれば、その節のデータ X が最大値になります。そうでなければ、次の規則で search_max_tree を再帰呼び出しして右の子 Rs をたどります。
簡単な実行例を示します。
?- search_min_tree(node(5,node(3,void,void),node(7,void,void)), X). X = 3 ; false. ?- search_max_tree(node(5,node(3,void,void),node(7,void,void)), X). X = 7 ; false.
●データの挿入
データの挿入も簡単です。述語 insert_tree(X, Xs, Ts) は、二分木 Xs にデータ X を挿入し、新しい二分木 Ts を生成します。プログラムは次のようになります。
リスト : データの挿入 insert_tree(X, node(Y, Ls, Rs), node(Y, Ts, Rs)) :- X < Y, insert_tree(X, Ls, Ts). insert_tree(X, node(Y, Ls, Rs), node(Y, Ls, Ts)) :- X > Y, insert_tree(X, Rs, Ts). insert_tree(X, node(X, Ls, Rs), node(X, Ls, Rs)). insert_tree(X, void, node(X, void, void)).
Prolog の複合項は immutable なデータ構造です。手続き型言語のようにデータを書き換えることはできません。insert_tree の返り値を格納するため新しい node を作り、それを返すことになります。
最後の規則が空の木にデータを挿入する場合です。最初の規則で、X が節の値 Y よりも小さければ、左の部分木に X を挿入します。Ts がデータを挿入した部分木を表しています。これを左の部分木に置き換えればいいわけです。2 番目が右側の部分木にデータを挿入する規則です。3 番目の規則で、同じデータを見つけた場合は同じ節を返します。
簡単な実行例を示します。
?- insert_tree(4, node(5,node(3,void,void),node(7,void,void)), Ts). Ts = node(5, node(3, void, node(4, void, void)), node(7, void, void)) ; false. ?- insert_tree(1, node(5,node(3,void,void),node(7,void,void)), Ts). Ts = node(5, node(3, node(1, void, void), void), node(7, void, void)) ; false. ?- insert_tree(6, node(5,node(3,void,void),node(7,void,void)), Ts). Ts = node(5, node(3, void, void), node(7, node(6, void, void), void)) ; false. ?- insert_tree(8, node(5,node(3,void,void),node(7,void,void)), Ts). Ts = node(5, node(3, void, void), node(7, void, node(8, void, void))) ; false.
●データの削除
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
図 : データの削除 (葉の場合)
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。
次に、子が一つある場合を考えてみましょう。
図 : データの削除 (子が一つの場合)
16 を削除する場合、その子である 15 と置き換えれば二分木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。
図 : データの削除 (子が二つの場合)
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。たとえば、上図で 14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
[*1] 逆に、左部分木の中から最大値を探し、それと削除するデータを置き換えてもかまいません。
●最小値と最大値の削除
まずは木の中から最小値と最大値の節を削除する述語を作りましょう。次のリストを見てください。
リスト : 最小値と最大値の削除 delete_min_tree(node(_, void, Rs), Rs). delete_min_tree(node(X, Ls, Rs), node(X, Ls1, Rs)) :- delete_min_tree(Ls, Ls1). delete_max_tree(node(_, Ls, void), Ls). delete_max_tree(node(X, Ls, Rs), node(X, Ls, Rs1)) :- delete_max_tree(Rs, Rs1).
述語 delete_min_tree は最小値を格納している節を削除します。左の子が void の節を探すのは search_min_tree と同じです。最初の規則で、左の子が void の節を見つけたら、もう一つの子 Rs がデータを削除した木になります。葉の場合、Rs は void になるので、単純に削除されることになります。
左の子があれば delete_min_tree を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、削除した部分木 Ls1 を新しい節の左の子にセットします。これで最小値の節を削除することができます。
述語 delete_max_tree は最大値を格納している節を削除します。右の子が void の節を探すのは search_max_tree と同じです。最初の規則で、右の子が void の節を見つけたら、もう一つの子 Ls がデータを削除した木になります。葉の場合、Ls は void になるので、単純に削除されることになります。
右の子があれば delete_max_tree を再帰呼び出しして、その右部分木の中から最大値を探し出して削除します。そして、削除した部分木 Rs1 を新しい節の右の子にセットします。これで最大値の節を削除することができます
簡単な実行例を示します。
?- delete_min_tree(node(5,node(3,void,void),node(7,void,void)), Ts). Ts = node(5, void, node(7, void, void)) ; false. ?- delete_max_tree(node(5,node(3,void,void),node(7,void,void)), Ts). Ts = node(5, node(3, void, void), void) ; false.
●データ削除のプログラム
それでは、データを削除する述語 delete_tree を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
delete_tree(X, node(X, Ls, void), Ls) :- !.
delete_tree(X, node(X, void, Rs), Rs) :- !.
delete_tree(X, node(X, Ls, Rs), node(M, Ls, Rs1)) :-
search_min_tree(Rs, M), delete_min_tree(Rs, Rs1).
delete_tree(X, node(Y, Ls, Rs), node(Y, Ls1, Rs)) :-
X < Y, delete_tree(X, Ls, Ls1).
delete_tree(X, node(Y, Ls, Rs), node(Y, Ls, Rs1)) :-
X > Y, delete_tree(X, Rs, Rs1).
最初の規則は右の子がない節を削除する場合です。左の子 Ls が削除した木になります。節が葉の場合、Ls が void になるので、この規則でデータを削除することができます。次の規則で左の子がない節を削除します。
左右の子がある場合は search_min_tree で右部分木 Rs から最小値 M を求め、delete_min_tree で Rs から最小値を格納している節を削除します。そして、節 node(M, Ls, Rs1) がデータを削除した新しい部分木になります。あとの規則で delete_tree を再帰呼び出しして、X と等しいデータを探します。
それでは実行してみましょう。
?- delete_tree(3, node(5,node(3,void,void),node(7,void,void)), Ts). Ts = node(5, void, node(7, void, void)) ; false. ?- delete_tree(5, node(5,node(3,void,void),node(7,void,void)), Ts). Ts = node(7, node(3, void, void), void) ; false. ?- delete_tree(7, node(5,node(3,void,void),node(7,void,void)), Ts). Ts = node(5, node(3, void, void), void). ?- delete_tree(4, node(5,node(3,void,void),node(7,void,void)), Ts). false. ?- delete_tree(1, node(5,node(3,void,void),node(7,void,void)), Ts). false. ?- delete_tree(9, node(5,node(3,void,void),node(7,void,void)), Ts). false.
●二分木の巡回
次は、二分木の全データにアクセスする述語を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
- 行きがけ順
まず節のデータを出力し、その後、左の子、右の子の順番で出力。 - 帰りがけ順
左の子、右の子を出力してから、節のデータを出力。 - 通りがけ順
左の子を出力してから、節のデータを出力し、最後に右の子を出力。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。
リスト : 通りがけ順 traverse_tree(X, node(_, Left, _)) :- traverse_tree(X, Left). traverse_tree(X, node(X, _, _)). traverse_tree(X, node(_, _, Right)) :- traverse_tree(X, Right).
通りがけ順の場合、最初の規則で左部分木をたどり、次の規則で第 1 引数と節のデータ X をマッチングさせます。それから最後の規則で右部分木をたどります。
簡単な実行例を示します。
?- traverse_tree(X, node(5,node(3,void,void),node(7,void,void))). X = 3 ; X = 5 ; X = 7 ; false. ?- findall(X, traverse_tree(X, node(5,node(3,void,void),node(7,void,void))), Ls). Ls = [3, 5, 7].
●簡単なテスト
最後に簡単なテストプログラムを作ります。
リスト : 簡単なテスト
% 表示
print_tree(Ts) :-
findall(X, traverse_tree(X, Ts), Xs), write(Xs), nl.
% 乱数データの生成
make_data(0, []) :- !.
make_data(N, [X | Xs]) :-
X is random(1000), N1 is N - 1, make_data(N1, Xs).
% テスト
delete_test(_, []).
delete_test(Ts, [X | Xs]) :-
search_tree(X, Ts),
!,
format('delete ~d =>', X),
delete_tree(X, Ts, Ts1),
print_tree(Ts1),
delete_test(Ts1, Xs).
delete_test(Ts, [_ | Xs]) :- delete_test(Ts, Xs).
search_test(_, []).
search_test(Ts, [X | Xs]) :-
format('search ~d => ', X),
(search_tree(X, Ts) -> write(true) ; write(false)),
nl,
search_test(Ts, Xs).
insert_test([], void).
insert_test([X | Xs], Ts1) :-
insert_test(Xs, Ts2),
insert_tree(X, Ts2, Ts1).
test(N) :-
make_data(N, Xs),
insert_test(Xs, Ts),
print_tree(Ts),
search_test(Ts, [-1, 1001 | Xs]),
delete_test(Ts, Xs).
test は N 個の数値を二分木に挿入します。数値は random [*2] を使ってランダムに選びます。実行結果は次のようになります。
?- test(16). [198,206,213,293,321,370,386,452,467,566,666,695,717,809,816,923] search -1 => false search 1001 => false search 566 => true search 695 => true search 452 => true search 198 => true search 666 => true search 293 => true search 321 => true search 370 => true search 923 => true search 213 => true search 467 => true search 816 => true search 386 => true search 206 => true search 809 => true search 717 => true delete 566 =>[198,206,213,293,321,370,386,452,467,666,695,717,809,816,923] delete 695 =>[198,206,213,293,321,370,386,452,467,666,717,809,816,923] delete 452 =>[198,206,213,293,321,370,386,467,666,717,809,816,923] delete 198 =>[206,213,293,321,370,386,467,666,717,809,816,923] delete 666 =>[206,213,293,321,370,386,467,717,809,816,923] delete 293 =>[206,213,321,370,386,467,717,809,816,923] delete 321 =>[206,213,370,386,467,717,809,816,923] delete 370 =>[206,213,386,467,717,809,816,923] delete 923 =>[206,213,386,467,717,809,816] delete 213 =>[206,386,467,717,809,816] delete 467 =>[206,386,717,809,816] delete 816 =>[206,386,717,809] delete 386 =>[206,717,809] delete 206 =>[717,809] delete 809 =>[717] delete 717 =>[] true ; false.
正常に動作しているようです。興味のある方はいろいろ試してみてください。
[*2] 乱数を生成する述語は、たいていの Prolog 処理系で定義されていると思います。random が使えない場合でも、ほかの述語 (たとえば rand とか) ならあるかもしれません。使用されている Prolog のマニュアルをお読みくださいませ。
改訂 2023 年 5 月 7 日
●自由変数を使う方法
今度は、新しい木を作成しないでデータを挿入する方法を説明します。これは Prolog らしく自由変数を使います。今までは空の木を void で表していましたが、これを自由変数で表すのです。この自由変数と節 (node) をマッチングさせることで、データを挿入することができます。
「同じデータを二分木に挿入しない」のであれば、プログラムはとても簡単になります。
リスト : データの挿入 insert_tree(X, node(X, _, _)) :- !. insert_tree(X, node(Y, Ls, _)) :- X < Y, insert_tree(X, Ls). insert_tree(X, node(Y, _, Rs)) :- X > Y, insert_tree(X, Rs).
最初の規則がポイントです。まず、同じデータを見つけたとき、この規則が成功します。これで同じデータは二分木に挿入されません。次に、空の木 (自由変数) のときですが、自由変数と節 node がマッチングするので、これも成功となります。これで、データ X が二分木に挿入されます。このとき、node 内の左右の部分木は自由変数であることに注意してください。
簡単な実行例を示します。
?- insert_tree(5, Ts). Ts = node(5, _, _). ?- insert_tree(5, Ts), insert_tree(3, Ts). Ts = node(5, node(3, _, _), _) ; false. ?- insert_tree(5, Ts), insert_tree(3, Ts), insert_tree(7, Ts). Ts = node(5, node(3, _, _), node(7, _, _)) ; false. ?- insert_tree(5, Ts), insert_tree(3, Ts), insert_tree(7, Ts), insert_tree(2, Ts). Ts = node(5, node(3, node(2, _, _), _), node(7, _, _)) ; false. ?- insert_tree(5, Ts), insert_tree(3, Ts), insert_tree(7, Ts), insert_tree(4, Ts). Ts = node(5, node(3, _, node(4, _, _)), node(7, _, _)) ; false. ?- insert_tree(5, Ts), insert_tree(3, Ts), insert_tree(7, Ts), insert_tree(6, Ts). Ts = node(5, node(3, _, _), node(7, node(6, _, _), _)) ; false. ?- insert_tree(5, Ts), insert_tree(3, Ts), insert_tree(7, Ts), insert_tree(8, Ts). Ts = node(5, node(3, _, _), node(7, _, node(8, _, _))) ; false.
次はデータの探索です。Prolog の場合、自由変数はどんなデータでもマッチングするので、空の木を判定する規則が必要になります。そうしないと、探索するデータを挿入してしまうのです。プログラムは次のようになります。
リスト : データの探索 search_tree(_, Ts) :- var(Ts), !, fail. search_tree(X, node(X, _, _)). search_tree(X, node(Y, Ls, _)) :- X < Y, search_tree(X, Ls). search_tree(X, node(Y, _, Rs)) :- X > Y, search_tree(X, Rs).
最初の規則で、述語 var を使って Ts が空の木かチェックします。そうであれば、これ以上調べる部分木はないので fail で失敗します。このとき、カットを使って後ろの規則の実行を禁止していることに注意してください。あとの規則は「データの挿入」と同じです。最初の規則により、空の木でないことが確かめられているので、データが挿入されるのではなく探索だけが行われます。
簡単な実行例を示します。
?- search_tree(3, node(5,node(3,_,_),node(7,_,_))). true ; false. ?- search_tree(5, node(5,node(3,_,_),node(7,_,_))). true ; false. ?- search_tree(7, node(5,node(3,_,_),node(7,_,_))). true ; false. ?- search_tree(2, node(5,node(3,_,_),node(7,_,_))). false. ?- search_tree(4, node(5,node(3,_,_),node(7,_,_))). false. ?- search_tree(6, node(5,node(3,_,_),node(7,_,_))). false. ?- search_tree(8, node(5,node(3,_,_),node(7,_,_))). false.
最小値と最大値の探索は次のようになります。
リスト : 最小値と最大値の探索 search_min_tree(node(X, Ls, _), X) :- var(Ls), !. search_min_tree(node(_, Ls, _), X) :- search_min_tree(Ls, X). search_max_tree(node(X, _, Rs), X) :- var(Rs), !. search_max_tree(node(_, _, Rs), X) :- search_max_tree(Rs, X).
簡単な実行例を示します。
?- search_min_tree(node(5,node(3,_,_),node(7,_,_)), X). X = 3. ?- search_max_tree(node(5,node(3,_,_),node(7,_,_)), X). X = 7.
最小値と最大値の削除も簡単です。
リスト : 最小値と最大値の削除 delete_min_tree(node(_, Ls, Rs), Rs) :- var(Ls), !. delete_min_tree(node(X, Ls, Rs), node(X, Ls1, Rs)) :- delete_min_tree(Ls, Ls1). delete_max_tree(node(_, Ls, Rs), Ls) :- var(Rs), !. delete_max_tree(node(X, Ls, Rs), node(X, Ls, Rs1)) :- delete_max_tree(Rs, Rs1).
簡単な実行例を示します。
?- delete_min_tree(node(5,node(3,_,_),node(7,_,_)), Ts). Ts = node(5, _, node(7, _, _)). ?- delete_max_tree(node(5,node(3,_,_),node(7,_,_)), Ts). Ts = node(5, node(3, _, _), _).
データを削除する場合、データが見つからないときの規則を追加します。
リスト : データの削除
delete_tree(_, Ts, _) :- var(Ts), !, fail.
delete_tree(X, node(X, Ls, Rs), Ls) :- var(Rs), !.
delete_tree(X, node(X, Ls, Rs), Rs) :- var(Ls), !.
delete_tree(X, node(X, Ls, Rs), node(M, Ls, Rs1)) :-
search_min_tree(Rs, M), delete_min_tree(Rs, Rs1).
delete_tree(X, node(Y, Ls, Rs), node(Y, Ls1, Rs)) :-
X < Y, delete_tree(X, Ls, Ls1).
delete_tree(X, node(Y, Ls, Rs), node(Y, Ls, Rs1)) :-
X > Y, delete_tree(X, Rs, Rs1).
データが見つからない場合、最初の規則が実行されて false が返されます。
?- delete_tree(3, node(5,node(3,_,_),node(7,_,_)), Ts). Ts = node(5, _, node(7, _, _)) ; false. ?- delete_tree(5, node(5,node(3,_,_),node(7,_,_)), Ts). Ts = node(7, node(3, _, _), _) ; false. ?- delete_tree(7, node(5,node(3,_,_),node(7,_,_)), Ts). Ts = node(5, node(3, _, _), _). ?- delete_tree(2, node(5,node(3,_,_),node(7,_,_)), Ts). false. ?- delete_tree(4, node(5,node(3,_,_),node(7,_,_)), Ts). false. ?- delete_tree(6, node(5,node(3,_,_),node(7,_,_)), Ts). false. ?- delete_tree(8, node(5,node(3,_,_),node(7,_,_)), Ts). false.
二分木を通りがけ順で巡回するプログラムは次のようになります。
リスト : 巡回 (通りがけ順) traverse_tree(_, Ts) :- var(Ts), !, fail. traverse_tree(X, node(_, Ls, _)) :- traverse_tree(X, Ls). traverse_tree(X, node(X, _, _)). traverse_tree(X, node(_, _, Rs)) :- traverse_tree(X, Rs).
最初の規則で、Ts が自由変数であれば空の木なので再帰を停止します。プログラムの違いはたったこれだけです。
?- traverse_tree(X, node(5,node(3,_,_),node(7,_,_))). X = 3 ; X = 5 ; X = 7 ; false. ?- findall(X, traverse_tree(X, node(5,node(3,_,_),node(7,_,_))), Ls). Ls = [3, 5, 7].
●簡単なテスト (2)
簡単なテストプログラムと実行結果を示します。
リスト : 簡単なテスト (2)
% 表示
print_tree(Ts) :-
findall(X, traverse_tree(X, Ts), Xs), write(Xs), nl.
% 乱数データの生成
make_data(0, []) :- !.
make_data(N, [X | Xs]) :-
X is random(1000), N1 is N - 1, make_data(N1, Xs).
% テスト
delete_test(_, []).
delete_test(Ts, [X | Xs]) :-
search_tree(X, Ts),
!,
format('delete ~d =>', X),
delete_tree(X, Ts, Ts1),
print_tree(Ts1),
delete_test(Ts1, Xs).
delete_test(Ts, [_ | Xs]) :- delete_test(Ts, Xs).
search_test(_, []).
search_test(Ts, [X | Xs]) :-
format('search ~d => ', X),
(search_tree(X, Ts) -> write(true) ; write(false)),
nl,
search_test(Ts, Xs).
insert_test([], _).
insert_test([X | Xs], Ts) :-
insert_test(Xs, Ts),
insert_tree(X, Ts).
test(N) :-
make_data(N, Xs),
insert_test(Xs, Ts),
print_tree(Ts),
search_test(Ts, [-1, 1001 | Xs]),
delete_test(Ts, Xs).
?- test(16). [19,115,344,374,637,662,672,711,756,795,818,841,960,965,967,996] search -1 => false search 1001 => false search 818 => true search 662 => true search 115 => true search 967 => true search 711 => true search 960 => true search 795 => true search 374 => true search 637 => true search 19 => true search 841 => true search 672 => true search 756 => true search 965 => true search 996 => true search 344 => true delete 818 =>[19,115,344,374,637,662,672,711,756,795,841,960,965,967,996] delete 662 =>[19,115,344,374,637,672,711,756,795,841,960,965,967,996] delete 115 =>[19,344,374,637,672,711,756,795,841,960,965,967,996] delete 967 =>[19,344,374,637,672,711,756,795,841,960,965,996] delete 711 =>[19,344,374,637,672,756,795,841,960,965,996] delete 960 =>[19,344,374,637,672,756,795,841,965,996] delete 795 =>[19,344,374,637,672,756,841,965,996] delete 374 =>[19,344,637,672,756,841,965,996] delete 637 =>[19,344,672,756,841,965,996] delete 19 =>[344,672,756,841,965,996] delete 841 =>[344,672,756,965,996] delete 672 =>[344,756,965,996] delete 756 =>[344,965,996] delete 965 =>[344,996] delete 996 =>[344] delete 344 =>[] true ; false.
正常に動作しているようです。興味のある方はいろいろ試してみてください。
改訂 2023 年 5 月 7 日