12.md

再帰ドリル(12)：二分探索木(走査と削除)

今回は、木の走査と節の削除について考える。

走査

木に格納されているすべての要素を取り出したい。ここで、ある節に注目しよう。節には、左の木、要素、右の木が格納されている。走査は、伝統的に左の木を先にたどり、次に右の木を辿る。このとき、要素の取り出し方には3種類ある。(訳語が複数あることに注意。)

• 行きがけ順、前順、先行順、preorder： 要素、左の木、右の木の順
• 通りがけ順、間順、中間順、inorder： 左の木、要素、右の木の順
• 帰りがけ順、後順、後行順、postorder： 左の木、右の木の順、要素

例として以下のような小さな木を考える。

それぞれの走査は以下のように要素を取り出す。

• 行きがけ順：2 → 1 → 3
• 通りがけ順：1 → 2 → 3
• 帰りがけ順：1 → 3 → 2

要素を取り出す順番は、ある節で守ればいいのではなく、すべての節で守らなければならない。それを理解するために、以下のような要素が7つの木を考えよう。

この例では、それぞれの走査は以下のように要素を取り出す。

• 行きがけ順：4 → 2 → 1 → 3 → 6 → 5 → 7
• 通りがけ順：1 → 2 → 3 → 4 → 5 → 6 → 7
• 帰りがけ順：1 → 3 → 2 → 5 → 7 → 6 → 4

この2つの例は探索木である。例から分かるように、探索木とは通りがけ順で要素を取り出すと、ソートされている木であると言える。

連結関数(++)を使うと、これらの走査を定義するのは簡単だ。

my_preorder_slow :: Tree a -> [a]
my_preorder_slow Leaf         = []
my_preorder_slow (Node l x r) =
    [x] ++ my_preorder_slow l ++ my_preorder_slow r

my_inorder_slow :: Tree a -> [a]
my_inorder_slow Leaf         = []
my_inorder_slow (Node l x r) =
    my_inorder_slow l ++ [x] ++ my_inorder_slow r

my_postorder_slow :: Tree a -> [a]
my_postorder_slow Leaf         = []
my_postorder_slow (Node l x r) =
    my_postorder_slow l ++ my_postorder_slow r ++ [x]

実際に二番目の例に示した要素が8個の木に対して使ってみよう。

> let tree = my_from_list [4,2,6,1,3,5,7]
> my_preorder tree
[4,2,1,3,6,5,7]
> my_inorder tree
[1,2,3,4,5,6,7]
> my_postorder tree
[1,3,2,5,7,6,4]

これらの定義は分かりやすいが、問題がある。連結関数(++)を使っていることである。リストの基本演算である (:) は、破壊的な代入がなくとも効率がよい。以下の例を考えよう。

> let xs = [5,3,4,8]
> let ys = 1 : xs

これを図に描くと以下のようになる。

一方、連結関数(++)は、破壊的な代入がなければ、第一引数のリストをコピーしなければならず、効率が悪い。以下の例を考えよう。

> let xs = [5,3,4,8]
> let ys = [2,7,1]
> let zs = xs ++ ys

これを図に描くと以下のようになる。

そこで、上記3つの走査関数から、(++)を取り除き、(:) のみで実装したい。

演習

行きがけ順を実現する関数を (++) ではなく (:) を使って実装しなさい。

my_preorder :: Tree a -> [a]
my_preorder t = my_preorder' t []

my_preorder' :: Tree a -> [a] -> [a]
my_preorder' Leaf         es = es
my_preorder' (Node l x r) es = undefined

ヒント：[x] ++ xs は x:xs と同じ結果を生成するが、後者の方が効率がよい。

通りがけ順を実現する関数を (++) ではなく (:) を使って実装しなさい。

my_inorder :: Tree a -> [a]
my_inorder t = my_inorder' t []

my_inorder' :: Tree a -> [a] -> [a]
my_inorder' Leaf         es = es
my_inorder' (Node l x r) es = undefined

帰りがけ順を実現する関数を (++) ではなく (:) を使って実装しなさい。

my_postorder :: Tree a -> [a]
my_postorder t = my_postorder' t []

my_postorder' :: Tree a -> [a] -> [a]
my_postorder' Leaf         es = es
my_postorder' (Node l x r) es = undefined

削除

探索木から要素を削除する方法を考えよう。削除関数は、以下に動作する。

1. 引数の要素が探索木の中にある場合は、その要素が含まれない新しい探索木を返す
2. 引数の要素が探索木の中にない場合は、同じだが新しい探索木を返す

2. について言うと、同じ探索木を返すなら新しい木は作らなくてもよいはずである。しかし、問題を簡単にするために、こういう仕様とする。

最小値の削除

削除の実装は、挿入にくらべてはるかに難しい。このため、探索木に対する削除が解説されている技術書はほとんどない。最初から一般的な削除を実装するのは難しいので、まず最小値を削除する関数を定義しよう。以下のように動作する。

• 引数の探索木に対して、「最小値」と「最小値を削除した新しい探索木」の組を返す
• ただし、引数探索木が空の木であれば、エラーを発生する (最小値を返せないから、安直にエラーとする)

探索木において、最小値は必ず一番左にある。一番左であるから、その左の木は空である。最小値の削除を図示すると以下のようになる。

右の木(r)は、葉(空の木)でも節(空ではない木)もよいことに注意しよう。

演習

最小値を削って、「最小値」と「最小値を削除した新しい探索木」の組を返す関数を実装したい。以下の undefined を変更し、my_delete_min を完成させよ

my_delete_min :: Ord a => Tree a -> (a, Tree a)
my_delete_min Leaf            = error "my_delete_min"
my_delete_min (Node Leaf x r) = (x, r)
my_delete_min (Node l x r)    = undefined

一般的な削除

最小値の削除では、左の木が葉である節を削除できた。親を削る場合に、子が1つであれば、その子を親が元の位置に置けばよい。この操作は探索木の性質を保存する。

同様に、右の木が葉である節も削除できる。

難しいのは、両方の木が節である場合である。親の位置は1つしかないのに、子は2つある。この問題を解く一般的な方法はこうだ。

• 「右の木」から「最小値を削った木」と「最小値」を取り出す
• 「親の要素」と「最小値」を置き換え、「左の木」は「元々の左の木」、「右の木」は「最小値を削った木」にする

この操作が探索木の性質を保存することに注意。以下にこの操作を図示する。

演習

以上を踏まえると、一般的な削除関数を実装できる。しかし安直に実装すると、たくさんのパターンマッチを書かなければならず、美しいコードにならない。幸いにも、補助関数を用いると、パターンマッチの数を減らせることが知られている。

以下に削除関数 my_delete と補助関数 my_glue の骨格を示す。undefined を編集して2つの関数を完成させよ。

my_delete :: Ord a => a -> Tree a -> Tree a
my_delete _ Leaf = Leaf
my_delete e (Node l x r) = case compare e x of
    LT -> undefined
    EQ -> my_glue l r
    GT -> undefined

my_glue :: Ord a => Tree a -> Tree a -> Tree a
my_glue Leaf r = undefined
my_glue l Leaf = undefined
my_glue l r    = undefined

[目次] [演習12]