今回はデータ構造の簡単な例題として「二分探索木 (binary search tree)」を取り上げます。Haskell には二分木 (平衡木) を使ったモジュール Data.Map と Data.Set が用意されているので、わざわざ二分木を自作する必要はないのですが、今回は Haskell のお勉強ということで、あえてシンプルな二分木を実際に作ってみましょう。
あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに探索してもなんとかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。
二分探索木はその名が示すように「木構造」の一種です。まずは木構造から説明しましょう。二分木を理解されている方は読み飛ばしてもらってかまいません。
「木構造 (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 回の比較が必要になりますが、二分探索木を使うと log2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。
そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは AVL 木、赤黒木 (red-black tree)、2-3 木、B 木、B* 木などがあります。拙作のページ Algorithms with Python では、AVL 木、赤黒木、2-3 木など平衡木のアルゴリズムを詳しく説明しています。興味のある方はお読みください。今回は Haskell のお勉強ということで、シンプルな二分探索木をプログラムすることにします。なお、本稿では二分探索木のことを単に「二分木」と書くことにします。
それでは、Haskell で二分木を作ってみましょう。最初に data 宣言で二分木を定義します。
リスト : 二分木の定義 data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show
二分木のデータ型は Tree a とします。Nil が空の木を表し、Node が節を表します。Node の第 1 要素が二分木に格納するデータ、第 2 要素が左部分木、第 3 要素が右部分木を表します。簡単な例を示します。
12
／ ＼ ==> Node 12 (Node 11 Nil Nil) (Node 13 Nil Nil)
11 13
これを図で表すと次のようになります。
┌─┬─┬─┐
│12│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│11│／│／│ │13│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｄ│Ｌ│Ｒ│
└─┴─┴─┘
Ｄ：data, Ｌ：left, Ｒ：right, ／：Nil
図 : 二分木の構造
それでは、データを探索する関数から作ってみましょう。この処理はデータを比較して左右の部分木をたどっていくだけです。
リスト : データの探索 search :: Ord a => a -> Tree a -> Maybe a search _ Nil = Nothing search x (Node y l r) | x == y = Just y | x < y = search x l | otherwise = search x r
関数 search の第 1 引数 x が探索するデータ、第 2 引数が二分木です。二分木が Nil であれば、これ以上探索することはできません。データは見つからなかったので Nothing を返します。そうでなければ、引数 x と節のデータを比較します。節のデータはパターンマッチングで取り出すことができます。y がデータ、l が左部分木、r が右部分木です。x == y ならばデータが見つかったので Just y を返します。x < y ならば search を再帰呼び出しして左部分木をたどります。そうでなければ x > y なので右部分木をたどります。
それでは簡単な実行例を示します。
*Tree> a = Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil)) *Tree> a Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil)) *Tree> search 0 a Nothing *Tree> search 1 a Just 1 *Tree> search 2 a Just 2 *Tree> search 3 a Just 3 *Tree> search 4 a Just 4 *Tree> search 5 a Just 5 *Tree> search 6 a Just 6 *Tree> search 7 a Just 7 *Tree> search 8 a Nothing
二分木の場合、最小値と最大値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。逆に、右側の子を順番にたどっていき、右側の子がない節に行き着いたとき、その節のデータが最大値になります。
プログラムは次のようになります。
リスト : 最小値と最大値 -- 最小値を求める searchMin :: Tree a -> Maybe a searchMin Nil = Nothing searchMin (Node x Nil _) = Just x searchMin (Node _ l _) = searchMin l -- 最大値を求める searchMax :: Tree a -> Maybe a searchMax Nil = Nothing searchMax (Node x _ Nil) = Just x searchMax (Node _ _ r) = searchMax r
関数 searchMin は最小値を求めてそれを返します。空の木の場合は Nothing を返します。次に、左側の子の値をチェックします。もし、Nil であれば左側の子がないので、その節のデータが最小値です。格納されているデータ x を Just に格納して返します。そうでなければ、searchMin を再帰呼び出しして左側の子をたどります。関数 searchMax は最大値を求めてそれを返します。右側の子をたどり、右側の子が Nil の節のデータを返します。
それでは実行してみましょう。
*Tree> a Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil)) *Tree> searchMin a Just 1 *Tree> searchMax a Just 7
次は、データを挿入する関数を作りましょう。探索と同様に、データを比較して木をたどっていき、木がなくなった所に新しいデータを挿入します。
リスト : データの挿入 -- 要素が一つの木 singleton :: a -> Tree a singleton x = Node x Nil Nil -- データの挿入 insert :: Ord a => a -> Tree a -> Tree a insert x Nil = singleton x insert x (Node y l r) | x == y = Node x l r | x < y = Node y (insert x l) r | otherwise = Node y l (insert x r)
関数 insert の第 1 引数 x が挿入するデータ、第 2 引数が二分木です。二分木が Nil であれば、関数 singleton で新しい節を作って返します。この返り値を節の部分木にセットします。2 番目の節で、x と y が等しい場合は二分木に同じデータがあるので新しい節 Node x l r に置き換えます。x < y であれば、insert を再帰呼び出しして左部分木をたどります。そして、左部分木を insert x l の返り値に置き換えた節を新しく作って返します。
Haskell は純粋な関数型言語なので、手続き型言語のように節のデータを書き換えることはできません。insert の返り値を格納するため新しい節を作って、それを返すことになります。もしも、l が Nil であれば、ここに新しい節が挿入され、新しい部分木が返されます。x > y であれば右部分木をたどり、データを挿入した新しい右部分木を返します。
insert のほかに、リストから二分木を生成する関数があると便利です。次のリストを見てください。
リスト : リストから二分木を作る fromList :: Ord a => [a] -> Tree a fromList xs = foldl (flip insert) Nil xs
関数 fromList は畳み込み foldl を使うと簡単です。初期値に空の木 Nil を与え、リスト xs から要素を順番に取り出して、insert で二分木に追加していくだけです。flip は引数の順番を交換する関数です。
*Main> :t flip flip :: (a -> b -> c) -> b -> a -> c
foldl の場合、呼び出す関数に渡す引数は、最初が累積変数で次がリストの要素です。insert の引数は逆になっているので、flip を使って合わせています。
簡単な実行例を示します。
*Tree> b = Nil *Tree> c = insert 4 b *Tree> c Node 4 Nil Nil *Tree> d = insert 2 c *Tree> d Node 4 (Node 2 Nil Nil) Nil *Tree> e = insert 6 d *Tree> e Node 4 (Node 2 Nil Nil) (Node 6 Nil Nil) *Tree> f = fromList [4,2,1,3,6,7,5] *Tree> f Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil))
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 Nil 17
↑
15 を削除する 削除
図 : データの削除 (葉の場合)
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。
次に、子が一つある場合を考えてみましょう。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 15
／ ＼ ／ ／ ＼
11 13 15 11 13
16 を削除する
図 : データの削除 (子が一つの場合)
16 を削除する場合、その子である 15 と置き換えれば二分木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。
14 15 <- 最小値と置き換え
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 Nil 17
↑
14 を削除する 削除
図 : データの削除 (子が二つの場合)
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。たとえば、上図で 14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まずは木の中から最小値と最大値の節を削除する関数を作成しましょう。次のリストを見てください。
リスト : 最小値と最大値の削除 -- 最小値の削除 deleteMin :: Tree a -> Tree a deleteMin Nil = Nil deleteMin (Node _ Nil r) = r deleteMin (Node x l r) = Node x (deleteMin l) r -- 最大値の削除 deleteMax :: Tree a -> Tree a deleteMax Nil = Nil deleteMax (Node _ l Nil) = l deleteMax (Node x l r) = Node x l (deleteMax r)
関数 deleteMin は最小値を格納している節を削除します。左側の子が Nil の節を探すのは searchMin と同じです。見つけたら、もう一つの子 r を返します。そうでなければ、deleteMin を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を格納した新しい節を返します。これで、最小値を持つ節が削除されます。葉の場合であれば r は Nil なので、単純に削除されることになります。
関数 deleteMax は最大値を格納している節を削除します。右側の子が Nil の節を探して、見つけたら左側の子 r を返します。そして、その返り値を格納した新しい節を返します。
それでは、データを削除する関数 delete を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
delete :: Ord a => a -> Tree a -> Tree a
delete x Nil = Nil
delete x (Node y l r)
| x < y = Node y (delete x l) r
| x > y = Node y l (delete x r)
| otherwise = delete' l r where
delete' Nil r = r
delete' l Nil = l
delete' l r = Node x' l (deleteMin r)
where Just x' = searchMin r
まず、節が Nil ならばデータが見つからなかったので Nil をそのまま返します。次に、削除するデータ x と節のデータ y を比較します。x と節のデータ y が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じで、delete の返り値を格納した新しい節を返します。
等しい場合はその節を削除します。この処理を局所関数 delete' で行います。l が Nil の場合は r を返し、r が Nil の場合は l を返します。子が 2 つある場合は、右部分木の最小値を関数 searchMin で求め、その値を格納した新しい節を作ります。このとき、関数 deleteMin で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換えることができます。
それでは実行してみましょう。
*Tree> a Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil)) *Tree> delete 4 a Node 5 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 Nil (Node 7 Nil Nil)) *Tree> delete 2 a Node 4 (Node 3 (Node 1 Nil Nil) Nil) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil)) *Tree> delete 6 a Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 7 (Node 5 Nil Nil) Nil) *Tree> foldl (flip delete) a [1..7] Nil
次は、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。
「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。
二分木の巡回は、再帰定義を使えば簡単に実現できます。プログラムは次のようになります。
リスト : 二分木をリストに変換する (通りがけ順) toList :: Tree a -> [a] toList Nil = [] toList (Node x l r) = toList l ++ [x] ++ toList r -- 別解 toList :: Tree a -> [a] toList tree = iter tree [] where iter Nil xs = xs iter (Node x l r) xs = iter l (x : iter r xs)
関数 toList は二分木を通りがけ順で巡回し、要素をリストに格納して返します。木が Nil であれば空リストを返します。そうでなければ、toList を再帰呼び出しして左部分木を巡回し、次に右部分木を巡回します。あとはその返り値を [x] をはさんで演算子 ++ で連結するだけです。
別解は演算子 ++ を使わないでプログラムしたものです。局所関数 iter の第 2 引数を累積変数として使います。ここに二分木の要素を追加していきます。要素はリストの先頭に追加されていくので、左部分木からたどるとリストの要素は逆順になります。このため、右部分木からたどることに注意してください。
それでは実行してみましょう。
*Tree> a Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil)) *Tree> toList a [1,2,3,4,5,6,7]
最後に、二分木を畳み込む関数 fold_left と fold_right を作りましょう。
リスト : 畳み込み fold_left :: (a -> b -> a) -> a -> Tree b -> a fold_left _ a Nil = a fold_left f a (Node x l r) = fold_left f (f (fold_left f a l) x) r fold_right :: (a -> b -> b) -> b -> Tree a -> b fold_right _ a Nil = a fold_right f a (Node x l r) = fold_right f (f x (fold_right f a r)) l
今回は通りがけ順で畳み込みを行うことにします。fold_left は左部分木から、fold_right は右部分木から順番にたどります。木が Nil の場合は引数 a をそのまま返します。そうでなければ fold_left (fold_right) を再帰呼び出します。関数 f を適用するとき、fold_left であれば左部分木を畳み込みした結果と x を渡します。fold_right は x と右部分木を畳み込みした結果を渡します。これで二分木を畳み込むことができます。
それでは実行例を示します。
*Tree> a Node 4 (Node 2 (Node 1 Nil Nil) (Node 3 Nil Nil)) (Node 6 (Node 5 Nil Nil) (Node 7 Nil Nil)) *Tree> fold_left (flip (:)) [] a [7,6,5,4,3,2,1] *Tree> fold_right (:) [] a [1,2,3,4,5,6,7] *Tree> fold_right (\_ a -> a + 1) 0 a 7 *Tree> fold_right (const (+1)) 0 a 7
const は次に示す型を持つ関数です。
const :: a -> b -> a
a -> b -> a は a -> (b -> a) のことなので、const a で生成される関数は、どのような引数を与えても、a を返す関数になります。次の例を見てください。
*Tree> c10 = const 10 *Tree> :t +d c10 c10 :: b -> Integer *Tree> c10 20 10 *Tree> c10 30 10
const 10 で生成された関数 c10 は、どんな引数が渡されても 10 を返す関数となります。ここで、const に型 a -> c の関数を渡す場合を考えてみましょう。型は次のようになります。
(a -> c) -> (b -> (a -> c)) => (a -> c) -> (b -> a -> c)
生成される関数は b -> a -> c になります。これは第 1 引数を無視して、第 2 引数の値に対して関数を適用することになります。
簡単な例を示しましょう。
*Tree> add1 = const (+1) *Tree> :t +d add1 add1 :: b -> Integer -> Integer *Tree> add1 1 2 3 *Tree> add1 10 2 3
このように、const (+1) で生成した関数 add1 は第 2 引数の値を +1 します。
fold_right の場合、関数の第 2 引数が累積変数になるので、const (+1) を渡せば、第 1 引数を無視して第 2 引数の値を +1 することができます。これで二分木の要素数を求めることができます。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリストをお読みください。
--
-- Tree.hs : 二分探索木
--
-- Copyright (C) 2013-2021 Makoto Hiroi
--
module Tree (
Tree,
emptyTree, singleton, insert,
search, searchMin, searchMax,
delete, deleteMin, deleteMax,
toList, fromList,
fold_left, fold_right, isEmptyTree
) where
-- データ型の定義
data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show
-- 空の木
emptyTree :: Tree a
emptyTree = Nil
-- 要素が一つの木
singleton :: a -> Tree a
singleton x = Node x Nil Nil
-- データの挿入
insert :: Ord a => a -> Tree a -> Tree a
insert x Nil = singleton x
insert x (Node y l r)
| x == y = Node x l r
| x < y = Node y (insert x l) r
| otherwise = Node y l (insert x r)
-- データの探索
search :: Ord a => a -> Tree a -> Maybe a
search _ Nil = Nothing
search x (Node y l r)
| x == y = Just y
| x < y = search x l
| otherwise = search x r
searchMin :: Tree a -> Maybe a
searchMin Nil = Nothing
searchMin (Node x Nil _) = Just x
searchMin (Node _ l _) = searchMin l
searchMax :: Tree a -> Maybe a
searchMax Nil = Nothing
searchMax (Node x _ Nil) = Just x
searchMax (Node _ _ r) = searchMax r
-- データの削除
deleteMin :: Tree a -> Tree a
deleteMin Nil = Nil
deleteMin (Node _ Nil r) = r
deleteMin (Node x l r) = Node x (deleteMin l) r
deleteMax :: Tree a -> Tree a
deleteMax Nil = Nil
deleteMax (Node _ l Nil) = l
deleteMax (Node x l r) = Node x l (deleteMax r)
delete :: Ord a => a -> Tree a -> Tree a
delete x Nil = Nil
delete x (Node y l r)
| x < y = Node y (delete x l) r
| x > y = Node y l (delete x r)
| otherwise = delete' l r where
delete' Nil r = r
delete' l Nil = l
delete' l r = Node x' l (deleteMin r)
where Just x' = searchMin r
-- データの変換
fromList :: Ord a => [a] -> Tree a
fromList xs = foldl (flip insert) Nil xs
toList :: Tree a -> [a]
toList tree = iter tree [] where
iter Nil xs = xs
iter (Node x l r) xs = iter l (x : iter r xs)
-- 畳み込み
fold_left :: (a -> b -> a) -> a -> Tree b -> a
fold_left _ a Nil = a
fold_left f a (Node x l r) = fold_left f (f (fold_left f a l) x) r
fold_right :: (a -> b -> b) -> b -> Tree a -> b
fold_right _ a Nil = a
fold_right f a (Node x l r) = fold_right f (f x (fold_right f a r)) l
-- 空の木か
isEmptyTree :: Tree a -> Bool
isEmptyTree Nil = True
isEmptyTree _ = False