今回は、二分木を探索木として使う方法を考える。
二分木の定義としては、以下の一般的な定義を使うことにする。
data Tree a = Leaf | Node (Tree a) a (Tree a)この定義は以下のような意味を持つ。
- 葉(Leaf)は値を格納しない
- 節(Node)は、左の木、値、および、右の木を格納する
このように木は再帰的な構造を持つので、再帰的な処理が適している。
節を○、葉を▲で表現し、いくつかの木を図示してみよう。
左から右へ、それぞれ要素数(木の大きさ)が0から4の木の例である。要素が1個以上の場合、葉を書くのは冗長であるから、これ以降不要な場合は描かない。
8章で調べたリストの定義と二分木の定義を比べてみよう。
data List a = Nil | Cons a (List a)
data Tree a = Leaf | Node (Tree a) a (Tree a)List と Tree の定義はほとんど同じで、自分自身を1つ格納するか、2つ格納するかの違いしかないことが分かる。
実際、二分木も一方向にだけ伸びれば、リストと変わらなくなる。
このような木は、実用上好ましくない。木を使うのは、あらゆる節へ少ない手間で到達したいからである。そのためには、葉の深さをなるべく同じに揃える必要がある。ある基準において、すべての葉の深さが「同じぐらい」と見なせるとき、木は平衡(バランス)しているという。
探索木とは、要素がソートされて格納されている木のことである。二分探索木の場合を考えてみよう。ある節には、左の木、要素、右の木が含まれている。二分探索木となるには、次の条件を満たす必要がある。
- 左の木に含まれるすべての要素が「この要素」より小さい
- 右の木に含まれるすべての要素が「この要素」よりも大きい
この条件は、ある節で満たされればよい訳ではなく、すべての節で満たされる必要がある。以下に例を示す。
他の種類の木と同様、探索木も平衡を保つことが肝要である。平衡を保つ機構を持った二分探索木は、平衡二分探索木と呼ばれる。有名な例に、赤黒木、AVL、および、重み平衡木がある。
今回扱うのは単なる二分探索木であって、平衡二分探索木ではない。
Haskell で data を使いデータ型を定義すると、それがそのままリテラルとして入力に使える。すなわち、パーサが自動的に生成される。また、deriving Show を付けると、リテラルが出力に表示されるようになる。(すなわち、パーサの逆関数であるプリティプリンタが自動的に生成される。)
data Tree a = Leaf | Node (Tree a) a (Tree a) deriving Show実は、最初の図に描いた5つの木は、二分探索木である。これらをリテラルで表現してみよう。空の木は Leaf である。以下を ghci で入力して欲しい。
> Leaf
Leaf
要素数が1つの木は、次のように表現できる。
> Node Leaf 5 Leaf
Node Leaf 5 Leaf
要素数が 5 つの木まで入力してみよう。
> Node (Node Leaf 3 Leaf) 5 Leaf
Node (Node Leaf 3 Leaf) 5 Leaf
> Node (Node Leaf 3 Leaf) 5 (Node Leaf 8 Leaf)
Node (Node Leaf 3 Leaf) 5 (Node Leaf 8 Leaf)
> Node (Node Leaf 3 (Node Leaf 4 Leaf)) 5 (Node Leaf 8 Leaf)
Node (Node Leaf 3 (Node Leaf 4 Leaf)) 5 (Node Leaf 8 Leaf)
入れ子が深くなると見にくくなるので、以下のような可視化関数を用意しておく。
my_show_tree :: Show a => Tree a -> String
my_show_tree t = my_show_tree' t ""
my_show_tree' :: Show a => Tree a -> String -> String
my_show_tree' Leaf _ = ""
my_show_tree' (Node Leaf x Leaf) _ = show x
my_show_tree' (Node l x r) pref =
show x ++ "\n"
++ pref ++ "+" ++ my_show_tree' l (pref ++ " ") ++ "\n"
++ pref ++ "+" ++ my_show_tree' r (pref ++ " ")使ってみよう。
> let tree3 = Node (Node Leaf 3 Leaf) 5 (Node Leaf 8 Leaf)
> let tree4 = Node (Node Leaf 3 (Node Leaf 4 Leaf)) 5 (Node Leaf 8 Leaf)))
> putStrLn (my_show_tree tree3)
5
+3
+8
> putStrLn (my_show_tree tree4)
5
+3
+
+4
+8
左の木が右の木よりも先に表示されていることに注意。
第一引数で与えられた要素が、第二引数で与えられた探索木の中に存在するかを調べる関数 my_member を定義したい。my_member の利用例を以下に示す。
> my_member 8 tree4
True
> my_member 4 tree4
True
> my_member 2 tree4
False
以下の undefined を変更して、my_member を完成させよ。
my_member :: Ord a => a -> Tree a -> Bool
my_member _ Leaf = False
my_member e (Node l x r) = case compare e x of
LT -> undefined
EQ -> undefined
GT -> undefinedなお、compre x y は、
- x が y より小さい場合は
LT - x と y が等しい場合は
EQ - x が y より大きい場合は
GT
を返す。
次に木に要素を追加する関数 my_insert を定義しよう。
8章で説明した通り、リストでは要素の追加は基本操作であった。先頭に追加するので、破壊的な代入は伴わない。
では、破壊的な代入を使わずに、木に要素を追加するにはどうすればいいだろう？一見不可能に思えるが、実は簡単で効率のよい方法が存在する。破壊したくなる節は新しく生成すればいいのである。
以下は、'a' から 'n' までの要素を格納している探索木に、要素 'o' を追加した場合の図である。
'o' を挿入する位置を決めるためにたどった節をすべて新しく作っているのが分かる。元々の木は破壊されておらず、元々の木と新しい木といくつかの部分木を共有している。この木は小さいので、共有の比率は高くないような印象を与えるが、大きな木では共有率は高い。たとえば、10000万個の要素を持つ平衡木に、要素を1つ加えるときに新たに作る出す節は平均13個である。それ以外の節は共有される。
以下に my_insert の利用例を示す。
> let tree5 = my_insert 2 tree4
> putStrLn (my_show_tree tree5)
5
+3
+2
+4
+8
挿入では、節の要素が置き換わることはない。元々の木で言えば葉の部分に、新しい要素が追加される。
以下のコード中の undefined を変更し、my_insert を完成させよ。
my_insert :: Ord a => a -> Tree a -> Tree a
my_insert e Leaf = Node Leaf e Leaf
my_insert e (Node l x r) = case compare e x of
LT -> undefined
EQ -> Node l e r
GT -> undefinedなお、以下のコードは、ありがちな誤りである。
-- このコードは間違い
my_insert :: Ord a => a -> Tree a -> Tree a
my_insert e Leaf = Node Leaf e Leaf
my_insert e (Node l x r) = case compare e x of
LT -> my_insert e l
EQ -> Node l e r
GT -> my_insert e r木を下にたどってはいるが、木を生成せずに戻っているから間違っている。
リストから木を生成する関数 my_from_list を定義しておくと便利である。
my_from_list :: Ord a => [a] -> Tree a
my_from_list es = foldl ins Leaf es
where
ins t e = my_insert e t以下のように利用する。
> let tree = my_from_list [5,8,3,4]
> putStrLn (my_show_tree tree)
5
+3
+
+4
+8
今回使ったのは一番よく使われる二分木の定義である。節は値を保持し、葉は値を格納しない。
data Tree a = Leaf | Node (Tree a) a (Tree a)平衡木などを実装するためには、節に平衡のための情報を追加することが多い。
理論上は、逆の木も定義できる。すなわち、葉に値を保持し、節には値を格納しない木である。しかし、節に情報を含まない木が実用されているところを著者は見たことがない。
data Tree a = Leaf a | Node (Tree a) (Tree a)多分木はリストを利用して定義できる。多分木は二項ヒープの実装などに利用される。
data Tree a = Node a [Tree a]葉と節に異なるデータを入れる木も考えられる。
data Tree a b = Leaf a | Node (Tree a b) b (Tree a b)Huffman木を実装する一般的な方法では、この定義を少し変えた木を使う。
data Tree a b = Leaf a b | Node (Tree a b) b (Tree a b)