前回はストラクチャとシグネチャを説明しました。SML/NJ のモジュール機能はこれだけではありません。もう一つ重要な機能に「ファンクタ (functor)」があります。ファンクタは引数にストラクチャを受け取り、それを使って新しいストラクチャを生成する機能です。ファンクタはストラクチャを生成するストラクチャと考えてください。今回は「二分探索木」を例題にファンクタを説明します。
まず最初に「二分探索木」から説明しましょう。二分探索木を理解されている方は読み飛ばしてもらってかまいません。
あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに検索してもなんとかなりますが、データ数が多くなると検索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。二分探索木はその名が示すように「木構造」の一種です。まずは木構造から説明しましょう。
「木構造 (tree structer)」は「木 (tree)」とも呼ばれるデータ構造で、「節 (ノード)」と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。
(root)
Ａ ──────── レベル０
／｜＼ ↑
／ ｜ ＼
Ｂ Ｃ Ｄ 木 レベル１
／｜＼ ｜＼ の
／ ｜ ＼ ｜ ＼ 高
Ｅ Ｆ Ｇ Ｈ Ｉ さ レベル２
／ ＼
／ ＼ ↓
Ｊ Ｋ ───── レベル３
図 : 一般的な木構造の一例
木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。
木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。
ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J と K の親で、J は G の子になります。J は子を持っていないので葉となります。
子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「 n 分木」と呼びます。
とくに、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。
(root)
18
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
14 22
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 20 24
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 19 21 23 25
図 : 二分木の一例
上図に二分木の例を示します。二分木では、節にひとつのデータを格納します。そして、その節の左側の子には小さいデータを、右側の子には大きいデータが配置されるように木を構成します。
この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。
二分探索木の探索は「二分探索 (binary search)」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。
データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log 2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。
そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは AVL 木、赤黒木、2-3 木、B 木、B* 木などがあります。
それでは、SML/NJ で二分木を作ってみましょう。まずはモジュールを使わずにプログラムします。最初に datatype で二分木を定義します。
リスト : 二分木の定義 datatype 'a tree = Nil | Node of 'a * 'a tree * 'a tree
二分木のデータ型は 'a tree とし、節は組で表します。もちろん、レコードを使ってもかまいません。Nil が空の木を表し、Node が節を表します。組の第 1 要素が二分木に格納するデータ、第 2 要素が左部分木、第 3 要素が右部分木を表します。簡単な例を示します。
12
／ ＼ ==> Node(12, Node(11, Nil, Nil), Node(13, Nil, Nil))
11 13
これを図で表すと次のようになります。
┌─┬─┬─┐
│12│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│11│／│／│ │13│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｄ│Ｌ│Ｒ│
└─┴─┴─┘
Ｄ：data, Ｌ：left, Ｒ：right, ／：Nil
図 3 : 二分木の構造
それでは、データを探索する関数から作ってみましょう。この処理はデータを比較して左右の部分木をたどっていくだけです。
リスト : データの探索 fun search(_, Nil) = false | search(x, Node(y, left, right)) = if x = y then true else if x < y then search(x, left) else search(x, right)
関数 search の第 1 引数 x が探索するデータ、第 2 引数が二分木です。二分木が Nil であれば、これ以上探索することはできません。データは見つからなかったので false を返します。そうでなければ、引数 x と節のデータを比較します。節のデータはパターンマッチングで取り出すことができます。y がデータ、left が左部分木、right が右部分木です。x = y ならばデータが見つかったので true を返します。x < y ならば search を再帰呼び出しして左部分木をたどります。そうでなければ x > y なので右部分木をたどります。
なお、データの比較に演算子 = や < を使っているため、関数 search の型は int * int tree -> bool になります。ここで「ファンクタ」を使うと、いろいろなデータ型に対応することができます。ファンクタはあとで説明します。
次は、データを挿入する関数を作りましょう。探索と同様に、データを比較して木をたどっていき、木がなくなった所に新しいデータを挿入します。
リスト : データの挿入 fun insert(x, Nil) = Node(x, Nil, Nil) | insert(x, T as Node(y, left, right)) = if x = y then T else if x < y then Node(y, insert(x, left), right) else Node(y, left, insert(x, right))
関数 insert の第 1 引数 x が挿入するデータ、第 2 引数が二分木です。二分木が Nil であれば、新しい節を作って返します。この返り値を節の部分木にセットします。
次の定義で、x と y が等しい場合は二分探索木に同じデータがあるので節をそのまま返します。x < y であれば、insert を再帰呼び出しして左部分木をたどります。そして、左部分木を insert(x, left) の返り値に置き換えた節を作って返します。もしも、left が Nil であれば、ここに新しい節が挿入され、新しい部分木が返されます。x > y であれば右部分木をたどり、データを挿入した新しい右部分木を返します。
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 Nil 17
↑
15 を削除する 削除
図 4 : データの削除 (葉の場合)
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。
次に、子が一つある場合を考えてみましょう。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 15
／ ＼ ／ ／ ＼
11 13 15 11 13
16 を削除する
図 5 : データの削除 (子が一つの場合)
16 を削除する場合、その子である 15 と置き換えれば二分木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。
14 15 <- 最小値と置き換え
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 Nil 17
↑
14 を削除する 削除
図 6 : データの削除 (子が二つの場合)
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。たとえば、上図で 14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まずは木の中から最小値を探す関数と、最小値の節を削除する関数を作成しましょう。次のリストを見てください。
リスト : 最小値の探索と削除 (* 最小値を求める *) fun search_min Nil = raise Empty | search_min(Node(x, Nil, _)) = x | search_min(Node(_, left, _)) = search_min left (* 最小値を削除する *) fun delete_min Nil = raise Empty | delete_min(Node(_, Nil, right)) = right | delete_min(Node(x, left, right)) = Node(x, delete_min left, right)
二分木の場合、最小値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search_min は最小値を求めてそれを返します。
最初の節はエラーチェックです。引数が空の木であれば例外を送出します。次に、左側の子の値をチェックします。もし、Nil であれば左側の子がないので、その節のデータが最小値です。格納されているデータ x を返します。そうでなければ、search_min を再帰呼び出しして左側の子をたどります。
関数 delete_min は最小値を格納している節を削除します。左側の子が Nil の節を探すのは search_min と同じです。見つけたら、もう一つの子 right を返します。そうでなければ、delete_min を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を格納した新しい節を返します。これで、最小値を持つ節が削除されます。葉の場合であれば right は Nil なので、単純に削除されることになります。
それでは、データを削除する関数 delete を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
(* 空の木か *)
fun isEmpty Nil = true
| isEmpty _ = false
fun delete(_, Nil) = raise Not_found
| delete(x, Node(y, left, right)) =
if x = y then
if isEmpty left then right
else if isEmpty right then left
else Node(search_min right, left, delete_min right)
else if x < y then Node(y, delete(x, left), right)
else Node(y, left, delete(x, right))
まず、節が Nil ならばデータが見つからなかったので例外 Not_found を送出します。次に、削除するデータ x と節のデータ y を比較します。等しい場合はその節を削除します。left が空の木 (Nil) の場合は right を返し、right が空の木の場合は left を返します。
子が 2 つある場合は、右部分木の最小値を関数 search_min で求め、その値を格納した新しい節を作ります。このとき、関数 delete_min で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換えることができます。
x と節のデータ y が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じで、delete の返り値を格納した新しい節を返します。
最後に、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理は、再帰定義を使えば簡単に実現できます。
リスト : 二分木の巡回 fun foreach _ Nil = () | foreach f (Node(x, left, right)) = (foreach f left; f x; foreach f right)
関数 foreach は二分木を通りがけ順に巡回し、格納されているデータに関数 f を適用します。まず、二分木が Nil ならば何もしないで unit を返します。これが再帰呼び出しの停止条件となります。あとは通りがけ順の定義そのままにプログラムをするだけです。左部分木をたどるため、left に対して foreach を再帰呼び出しします。次に、節のデータ x に関数 f を適用します。最後に右部分木をたどるため、right に対して foreach を再帰呼び出しします。
それでは簡単な実行例を示しましょう。
- val a0 = insert(5, Nil); val a0 = Node (5,Nil,Nil) : int tree - val a1 = insert(3, a0); val a1 = Node (5,Node (3,Nil,Nil),Nil) : int tree - val a2 = insert(7, a1); val a2 = Node (5,Node (3,Nil,Nil),Node (7,Nil,Nil)) : int tree - search(3, a2); val it = true : bool - search(0, a2); val it = false : bool - foreach (fn x => print (Int.toString x ^ "\n")) a2; 3 5 7 val it = () : unit - val a3 = delete(5, a2); val a3 = Node (7,Node (3,Nil,Nil),Nil) : int tree
正常に動作していますね。
(*
* tree0.sml : 二分木
*
* Copyright 2005-2020 Makoto Hiroi
*)
(* 例外 *)
exception Empty
exception Not_found
(* 節の定義 *)
datatype 'a tree = Nil | Node of 'a * 'a tree * 'a tree
(* 空の木か *)
fun isEmpty Nil = true
| isEmpty _ = false
(* 探索 *)
fun search(_, Nil) = false
| search(x, Node(y, left, right)) =
if x = y then true
else if x < y then search(x, left)
else search(x, right)
(* 挿入 *)
fun insert(x, Nil) = Node(x, Nil, Nil)
| insert(x, T as Node(y, left, right)) =
if x = y then T
else if x < y then Node(y, insert(x, left), right)
else Node(y, left, insert(x, right))
(* 最小値 *)
fun search_min Nil = raise Empty
| search_min(Node(x, Nil, _)) = x
| search_min(Node(_, left, _)) = search_min left
(* 最大値 *)
fun search_max Nil = raise Empty
| search_max(Node(x, _, Nil)) = x
| search_max(Node(_, _, right)) = search_max right
(* 最小値の削除 *)
fun delete_min Nil = raise Empty
| delete_min(Node(_, Nil, right)) = right
| delete_min(Node(x, left, right)) = Node(x, delete_min left, right)
(* 最大値の削除 *)
fun delete_max Nil = raise Empty
| delete_max(Node(_, left, Nil)) = left
| delete_max(Node(x, left, right)) = Node(x, left, delete_max right)
(* 削除 *)
fun delete(_, Nil) = raise Not_found
| delete(x, Node(y, left, right)) =
if x = y then
if isEmpty left then right
else if isEmpty right then left
else Node(search_min right, left, delete_min right)
else if x < y then Node(y, delete(x, left), right)
else Node(y, left, delete(x, right))
(* 巡回 *)
fun foreach _ Nil = ()
| foreach f (Node(x, left, right)) = (foreach f left; f x; foreach f right)
それではファンクタを使って、二分探索木を改良しましょう。ファンクタは次のように定義します。
functor 名前 (structA: sigA) = struct ..... end
ファンクタは引数に与えられたストラクチャ structA を使って新しいストラクチャを生成します。structA は関数定義の引数 (仮引数) と同じと考えてください。ファンクタは structA.func や structA.value のように、structA に定義されている関数や変数を使ってストラクチャを定義します。そして、structA の型をシグネチャ sigA で指定します。逆にいえば、ファンクタで必要になる関数や変数の仕様を sigA に記述するのです。ファンクタに与えるストラクチャは、このシグネチャの仕様を満たす必要があります。
二分探索木はデータを比較する関数が必要です。これをストラクチャに定義して渡すことにします。シグネチャの定義は次のようになります。
リスト : シグネチャの定義 signature ITEM = sig type item val compare : item * item -> order end
シグネチャの名前は ITEM としました。データの比較関数を定義するストラクチャなので、名前を ORDER にしている参考文献もあります。最初に type で item というデータ型を宣言します。このデータ型を使ってシグネチャを記述します。具体的なデータ型の指定はストラクチャで行います。データを比較する関数が compare です。関数型は item * item -> order とします。order は SML/NJ に定義されているデータ型です。
datatype order = LESS | EQUAL | GREATER
order はデータの大小関係を表します。compare(x, y) は x < y ならば LESS を、x = y ならば EQUAL を、x > y ならば GREATER を返すことにします。
このシグネチャを使ってファンクタを定義します。プログラムは次のようになります。
リスト : ファンクタの定義
functor makeTree(Item: ITEM) = struct
(* 例外 *)
exception Empty
exception Not_found
(* 節の定義 *)
datatype 'a tree = Nil | Node of 'a * 'a tree * 'a tree
(* 二分木の生成 *)
val create = Nil : Item.item tree
(* 空の木か *)
fun isEmpty Nil = true
| isEmpty _ = false
(* 探索 *)
fun search(_, Nil) = false
| search(x, Node(y, left, right)) =
case Item.compare(x, y)
of EQUAL => true
| LESS => search( x, left )
| GREATER => search( x, right )
・・・省略・・・
(* 巡回 *)
fun app _ Nil = ()
| app f (Node(x, left, right)) = (app f left; f x; app f right)
end
引数のストラクチャを Item としシグネチャを ITEM とします。ファンクタで指定するストラクチャ名は関数定義の仮引数と同じなので、あらかじめ Item というストラクチャを定義しておく必要はありません。ストラクチャで定義されているデータ型は Item.item で、比較関数は Item.compare で参照することができます。
二分木のデータ型は今までと同じ 'a tree です。変数 create はデータ型を Item.item tree に限定します。Nil だけだと多相的なデータになります。あとは各関数でデータを比較するときに Item.compare を呼び出します。compare は order を返すので、case で場合分けしています。最後に、二分木の要素に関数 f を適用する高階関数 foreach を app に変更します。
次は、ファンクタに渡すストラクチャを作ります。
リスト : ストラクチャの定義と生成
structure IntItem: ITEM = struct
type item = int
fun compare(x, y) =
if x < y then LESS
else if x = y then EQUAL
else GREATER
end
structure IntTree = makeTree(IntItem)
二分木に格納するデータは int で、ストラクチャの名前は IntItem とします。最初に、シグネチャで宣言した item のデータ型を int にします。type はデータ型の宣言だけではなく、データ型に名前を付ける機能があります。
type 名前 = 型式
type item = int で、シグネチャで宣言したデータ型 item は int になります。あとは関数 compare を定義するだけです。compare はシグネチャで item * item -> order と定義されているので、2 つの整数値を引数に受け取る関数になります。最後に、int を格納する二分木 IntTree をファンクタで生成します。これはファンクタ makeBinTree に IntItem を渡すだけです。
それでは実際に試してみましょう。IntTree を生成すると、次のようなシグネチャが表示されます。
structure IntTree :
sig
exception Empty
exception Not_found
datatype'a tree
= Nil | Node of 'a * 'a <resultStr>.tree * 'a <resultStr>.tree
val create : Item.item <resultStr>.tree
val isEmpty : 'a <resultStr>.tree -> bool
val search : Item.item * Item.item <resultStr>.tree -> bool
val
insert : Item.item * Item.item <resultStr>.tree
-> Item.item <resultStr>.tree
val search_min : 'a <resultStr>.tree -> 'a
val search_max : 'a <resultStr>.tree -> 'a
val delete_min : 'a <resultStr>.tree -> 'a <resultStr>.tree
val delete_max : 'a <resultStr>.tree -> 'a <resultStr>.tree
val
delete : Item.item * Item.item <resultStr>.tree
-> Item.item <resultStr>.tree
val app : ('a -> 'b) -> 'a <resultStr>.tree -> unit
end
IntTree の簡単な実行例を示します。
- val a = IntTree.create; val a = Nil : IntItem.item IntTree.tree - val a1 = IntTree.insert(10, a); val a1 = Node (10,Nil,Nil) : IntItem.item IntTree.tree - val a2 = IntTree.insert(5, a1); val a2 = Node (10,Node (5,Nil,Nil),Nil) : IntItem.item IntTree.tree - val a3 = IntTree.insert(15, a2); val a3 = Node (10,Node (5,Nil,Nil),Node (15,Nil,Nil)) : IntItem.item IntTree.tree - IntTree.app (fn(x)=>print(Int.toString(x) ^ "\n")) a3; 5 10 15 val it = () : unit - val a = List.foldr (fn(x, a) => IntTree.insert(x, a)) IntTree.create [5,4,6,7,3,2,8,9,1,0]; val a = Node (0,Nil,Node (1,Nil,Node (9,Node (8,Node (#,#,#),Nil),Nil))) : IntItem.item IntTree.tree - IntTree.app (fn x => print (Int.toString x ^ " ")) a; 0 1 2 3 4 5 6 7 8 9 val it = () : unit - IntTree.search(0, a); val it = true : bool - IntTree.search(5, a); val it = true : bool - IntTree.search(9, a); val it = true : bool - IntTree.search(10, a); val it = false : bool - IntTree.search_min(a); val it = 0 : IntItem.item - IntTree.search_max(a); val it = 9 : IntItem.item - val a1 = IntTree.delete_min(a); val a1 = Node (1,Nil,Node (9,Node (8,Node (2,Nil,Node (#,#,#)),Nil),Nil)) : IntItem.item IntTree.tree - IntTree.search_min(a1); val it = 1 : IntItem.item - val a2 = IntTree.delete_max(a1); val a2 = Node (1,Nil,Node (8,Node (2,Nil,Node (3,Nil,Node (#,#,#))),Nil)) : IntItem.item IntTree.tree - IntTree.search_max(a2); val it = 8 : IntItem.item - val a3 = List.foldr (fn(x, y) => IntTree.delete(x, y)) a [0,1,2,3,4,5,6,7,8,9]; val a3 = Nil : IntItem.item IntTree.tree - IntTree.isEmpty a3; val it = true : bool
正常に動作していますね。興味のある方はいろいろ試してみてください。
(*
* tree1.sml : 二分木
*
* Copyright 2005-2020 Makoto Hiroi
*)
signature ITEM = sig
type item
val compare : item * item -> order
end
functor makeTree(Item: ITEM) = struct
(* 例外 *)
exception Empty
exception Not_found
(* 節の定義 *)
datatype 'a tree = Nil | Node of 'a * 'a tree * 'a tree
(* 二分木の生成 *)
val create = Nil : Item.item tree
(* 空の木か *)
fun isEmpty Nil = true
| isEmpty _ = false
(* 探索 *)
fun search(_, Nil) = false
| search(x, Node(y, left, right)) =
case Item.compare(x, y)
of EQUAL => true
| LESS => search( x, left )
| GREATER => search( x, right )
(* 挿入 *)
fun insert(x, Nil) = Node(x, Nil, Nil)
| insert(x, T as Node(y, left, right)) =
case Item.compare(x, y)
of EQUAL => T
| LESS => Node(y, insert(x, left), right)
| GREATER => Node(y, left, insert(x, right))
(* 最小値 *)
fun search_min Nil = raise Empty
| search_min(Node(x, Nil, _)) = x
| search_min(Node(_, left, _)) = search_min left
(* 最大値 *)
fun search_max Nil = raise Empty
| search_max(Node(x, _, Nil)) = x
| search_max(Node(_, _, right)) = search_max right
(* 最小値の削除 *)
fun delete_min Nil = raise Empty
| delete_min(Node(_, Nil, right)) = right
| delete_min(Node(x, left, right)) = Node(x, delete_min left, right)
(* 最大値の削除 *)
fun delete_max Nil = raise Empty
| delete_max(Node(_, left, Nil)) = left
| delete_max(Node(x, left, right)) = Node(x, left, delete_max right)
(* 削除 *)
fun delete(_, Nil) = raise Not_found
| delete(x, Node(y, left, right)) =
case Item.compare(x, y)
of EQUAL => if isEmpty left then right
else if isEmpty right then left
else Node(search_min right, left, delete_min right)
| LESS => Node(y, delete(x, left), right)
| GRAETER => Node(y, left, delete(x, right))
(* 巡回 *)
fun app _ Nil = ()
| app f (Node(x, left, right)) = (app f left; f x; app f right)
end
structure IntItem: ITEM = struct
type item = int
fun compare(x, y) =
if x < y then LESS
else if x = y then EQUAL
else GREATER
end
structure IntTree = makeTree(IntItem)