2分探索木は次の性質を満たすような二分木です: ツリーのそれぞれのノードについて、ノードの中に保存されているそれぞれのキーは、そのノードの左の子に保存されている全てのキー以上で、そのノードの右の子に保存されている全てのキー以下です。 別の言い方をすると、深さ優先探索で走査すると昇順のキーの列が得られるような二分木は2分探索木です。 実際には、2分探索木は集合や写像を表現する際によく使われます。
次のコードは、保存されたキーが文字列である2分探索木を表わすデータ型 bstree を宣言しています:
bstree 型の全ての値が有効な2分探索木を表現していないことに注意すべきです。 2分探索木ではない二分木を表現する値をコンストラクトする可能性があります。
次の関数 [bstree_inord] は与えられた二分木を間順走査します:
fun bstree_inord ( t0: bstree, fwork: string -<cloref1> void ) : void = ( case+ t0 of | E () => () | B (t1, k, t2) => { val () = bstree_inord (t1, fwork) val () = fwork (k) val () = bstree_inord (t2, fwork) } ) (* end of [bstree_inord] *)
[t0] が2分探索木であるなら、 [fwork] によって作られるキーの列は昇順になります。
2分探索木とキーが与えられると、次の関数 [bstree_search] はそのキーがその探査木の中に保存されているかどうか調べます:
fun bstree_search ( t0: bstree, k0: string ) : bool = ( // case+ t0 of | E () => false | B (t1, k, t2) => let val sgn = compare (k0, k) in case+ 0 of | _ when sgn < 0 => bstree_search (t1, k0) | _ when sgn > 0 => bstree_search (t2, k0) | _ (*k0 = k*) => true end // end of [B] // ) (* end of [bstree_search] *)
与えられたキーが見つかれば [bstree_search] は true を返し、見つからなければ false を返します。
2分探索木とキーが与えられると、次の関数 [bstree_insert] はその探索木にそのキーを挿入します:
fun bstree_insert ( t0: bstree, k0: string ) : bstree = ( // case+ t0 of | E () => B (E, k0, E) | B (t1, k, t2) => let val sgn = compare (k0, k) in case+ 0 of | _ when sgn < 0 => B (bstree_insert (t1, k0), k, t2) | _ when sgn > 0 => B (t1, k, bstree_insert (t2, k0)) | _ (*k0 = k*) => t0 // [k0] found and no actual insertion end // end of [B] // ) (* end of [bstree_insert] *)
キーが与えられた探索木の中に含まれていない時のみ、[bstree_insert] はキーを挿入することに注意してください。 もし挿入する場合、そのキーを新しく作った葉ノードに格納します。
この章で紹介したコード全体と追加のテストコードは オンライン から入手できます。 (訳注: このコードを atscc でコンパイルする際には -DATS_MEMALLOC_LIBC オプションが必要です。)