でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

HaskellでB-treeを実装(delete編)

前回に引き続いて今回もHaskellでB-treeの実装。今回はキーの削除を実装する。前回同様 "Introduction to Algorithms" の実装方針に沿って実装する。前回はこちら。

yamaguchiyuto.hatenablog.com

コードはここにおいた

Haskell B-tree implementation · GitHub

shift と merge

キーの削除において重要な概念となるshiftmergeについてはじめに説明する。B-treeの定義より、各ノードはキーを (m-1) 個以上、 (2m-1) 個以下持たないといけない(m はB-treeのオーダー)。なので、キーを (m-1) 個しか持たないノードからそのままキーを削除することはできない。キーを (m-1) 個しか持たないノードをここでは "few" であると呼ぼう*1。キーを削除する前に、mergeとかshiftといった操作をすることによってノードを予め "few" でない状態にしておく。

まずはshiftについて説明する。shiftにはshift_leftshift_rightがある。下の図はshift_leftを図示している。左の子ノードは "few" であるため、そこからキーを削除することはできない。そこで、右の子ノード("few" でない)からキーを左に "シフト" することで "few" でない状態にする。ここで注意する点は、そのまま右の子ノードからキーを持ってくるのではなく、右のキーは親ノードへ、親ノードのキーを左の子ノードへシフトする。shift_rightについても同様なので、説明は省く。

f:id:yamaguchiyuto:20180105001306p:plain

shiftを実装しよう。コードは以下の通り。キーを1つと、その左右の子ノードをそれぞれ引数として受け取り、シフトしてから親ノードを返す。説明したとおりに実装しただけなので、見ればわかると思う。

shift_left :: (Ord a, Eq a) => a -> Tree a -> Tree a -> Tree a
shift_left k (Leaf m keys1) (Leaf _ (k2:keys2)) = Node m [k2] [(Leaf m (keys1 ++ [k])), (Leaf m keys2)]
shift_left k (Node m keys1 trees1) (Node _ (k2:keys2) (t2:trees2)) = Node m [k2] [(Node m (keys1 ++ [k]) (trees1 ++ [t2])), (Node m keys2 trees2)]

shift_right :: (Ord a, Eq a) => a -> Tree a -> Tree a -> Tree a
shift_right k (Leaf m keys1) (Leaf _ keys2) = Node m [last keys1] [(Leaf m (init keys1)), (Leaf m (k:keys2))]
shift_right k (Node m keys1 trees1) (Node _ keys2 trees2) = Node m [last keys1] [(Node m (init keys1) (init trees1)), (Node m (k:keys2) ((last trees1):trees2))]

mergeについて説明する。いつでもshiftができればいいんだけど、できないときもある。そういうときにmergeが必要となる。ここでも図を使って説明しよう。下の図では左の子ノードが "few" なので、キーを増やしたい。でも隣の子ノードも "few" なのでキーをシフトすることができない。そこで、親ノードの対応するキーも含めて子ノードふたつを "マージ" する。そうすることで、マージされたノードからキーを削除できるようになる。

f:id:yamaguchiyuto:20180105213216p:plain

mergeのコードは以下の通り。これも単純で、親ノードのキーと2つの子ノードを受け取って、マージされたノードを返すだけ。引数として渡されたノードがLeafNodeかで場合分けしているけど、やっていることは本質的には同じ。

merge :: (Ord a, Eq a) => a -> Tree a -> Tree a -> Tree a
merge k (Leaf m1 keys1) (Leaf _ keys2) = Leaf m1 (keys1 ++ [k] ++ keys2)
merge k (Node m1 keys1 trees1) (Node _ keys2 trees2) = Node m1 (keys1 ++ [k] ++ keys2) (trees1 ++ trees2)

delete の実装

さて、shiftmergeの説明が終わったので、キーの削除を実装していく。まずはトップレベルの関数deleteを定義する。

delete :: (Ord a, Eq a) => Tree a -> a -> Tree a
delete (Nil _) _ = error "Underflow"  -- (1)
delete (Leaf _ []) _ = error "Underflow"  -- (1)
delete n@(Node m [k] [t1, t2]) x = if is_few t1 && is_few t2  -- (2)
                                     then delete_non_few (merge k t1 t2) x
                                     else delete_non_few n x
delete n x = delete_non_few n x  -- (3)

未定義の関数がいくつも出てきたけど、それらについては順を追って説明する。ここではルートノードの状態に応じて条件分岐しているだけ。それぞれについて見てみよう。(1) 渡された木がNilもしくは空のキーリストを持ったLeafなら削除するキーはもう無いので、エラーを吐く。(2) ルートノードがキーを1つしか持たない(つまり子部分木を2つしか持たない)場合は、子部分木がどちらも "few" ならそれらを mergeしてからdelete_non_fewする。少なくともどちらかが "few" でないなら、そのままdelete_non_fewに渡す。(3) さいごに、ルートノードがキーを2つ以上持つなら、そのときもそのままdelete_non_fewに渡す。

is_fewはノードが "few" であるか否かを判定する関数。以下のように定義する。簡単。

is_few :: (Ord a, Eq a) => Tree a -> Bool
is_few (Nil _) = False
is_few (Leaf m keys)
  | length keys == (m - 1) = True
  | otherwise = False
is_few (Node m keys _)
  | length keys == (m - 1) = True
  | otherwise = False

メインとなるdelete_non_fewについて見ていこう。この関数に渡されるノードは必ず "few" で無いことが保証されている(というかそうなるように実装する)。定義は以下の通り。

delete_non_few :: (Ord a, Eq a) => Tree a -> a -> Tree a
delete_non_few l@(Leaf _ _) x = delete_leaf l x  -- (1)
delete_non_few n@(Node m [k] [t1, t2]) x  -- (2)
  | x == k = delete_here n x
  | x < k  = delete_middle n x
  | x > k  = delete_last n x
delete_non_few n@(Node m (k:ks) (t:t_next:ts)) x  -- (3)
  | x == k = delete_here n x
  | x < k  = delete_middle n x
  | x > k  = Node m (k:new_ks) (t:new_ts)
    where Node _ new_ks new_ts = delete_non_few (Node m ks (t_next:ts)) x

ここでも3つの場合分けがあるので、それぞれ見てみよう。(1) の場合、つまり渡されたノードがLeafの場合はそのままdelete_leaf(後述)に渡してキーを削除する。(2) は渡されたノードがキーを1つしか持たない場合なんだけど、これは終端処理なので先に (3) を説明しよう。(3) の場合は渡されたノードがキーを2つ以上持つことが保証されている。削除キーxといま注目しているキーkを比較していく。まずx == kの場合は削除すべきキーが見つかったので、nをそのままdelete_here(後述)に渡してキーを削除する。x < kの場合はこのノードnに探しているキーは無いことが分かった、かつ、キーが含まれるべき子部分木も分かったので、delete_middle(後述)で再帰的にキーを削除する。x > kの場合はまだこのノード内にxがある可能性があるので、先頭のキーkを取り除いて残りのキーのリストksに対して再帰的にdelete_non_fewでキーの削除を行う。(3) においてx > kのときの処理を繰り返すことで、いずれ (2) の状態に到達する。

んで、(2) の終端処理もほぼ (3) と同じことをしているんだけど、(2) でx > kになった場合はnの中にキーが無いことが判明、かつ、一番右(最後)の子部分木にキーが含まれるべきであることが判明したので、delete_lastでその子部分木から再帰的にキーを削除する*2

delete_leafは簡単。delete_leafに渡されてくるノードにキーがあれば単にそれを削除するし、なければ探しているキーxは木全体になかったということになるので、単にlを返して終了する。

delete_leaf :: (Ord a, Eq a) => Tree a -> a -> Tree a
delete_leaf l@(Leaf m (k:ks)) x
  | x == k = Leaf m ks
  | x < k  = l
  | x > k  = Leaf m (k:new_ks) where Leaf _ new_ks = delete_leaf (Leaf m ks) x

次にdelete_hereを見てみよう。ここに渡されてくるノードは、必ずキーのリストの先端kに削除すべきキーを持っていることが保証されている。つまり、delete_hereでは渡されたノードからkを削除する。削除の仕方は二部探索木とほとんど同じで、右(もしくは左)の部分木における最小キー(もしくは最大キー)を削除し、それをkと置き換える。

delete_here :: (Ord a, Eq a) => Tree a -> a -> Tree a
delete_here (Node m (k:ks) (t1:t2:ts)) x = if is_few t1 && is_few t2
                                             then Node m ks ((delete_non_few (merge k t1 t2) x):ts)  -- (1)
                                             else if is_few t1
                                               then Node m ((get_min t2):ks) (t1:(delete_min t2):ts)  -- (2)
                                               else Node m ((get_max t1):ks) ((delete_max t1):t2:ts)  -- (3)

ここも3つの場合分けがあるのでそれぞれ見ていこう。(1) を飛ばして先に (2) と (3) について説明する。(2) ではt1は "few" だけどt2は "few" じゃないので、t2から最小のキーを持ってきて置き換える。(3) では逆にt2は "few" だけどt1は "few" じゃないのでt1から最大のキーを持ってきて置き換える。get_min等の関数については後述。で、(1) のときはt1t2も "few" なので、それらをmergeしてまた再帰的にdelete_non_fewを呼ぶ。delete_minにもdelete_maxにも "few" のノードを渡さない取り決めにしておくと実装が容易になるのでこうする。

get_minget_maxdelete_mindelete_maxを定義する。これらの関数もシンプルなので特に説明はいらないと思う。get_minget_maxは渡された部分木の中で最も小さい(大きい)キーを返す。delete_mindelete_maxはそのキーを削除した部分木を返す。

get_min :: (Ord a, Eq a) => Tree a -> a
get_min (Leaf _ keys) = head keys
get_min (Node _ _ trees) = get_min (head trees)

delete_min :: (Ord a, Eq a) => Tree a -> Tree a
delete_min (Leaf m keys) = Leaf m (tail keys)
delete_min (Node m keys (t:ts)) = Node m keys ((delete_min t):ts)

get_max :: (Ord a, Eq a) => Tree a -> a
get_max (Leaf _ keys) = last keys
get_max (Node _ _ trees) = get_max (last trees)

delete_max :: (Ord a, Eq a) => Tree a -> Tree a
delete_max (Leaf m keys) = Leaf m (init keys)
delete_max (Node m keys trees) = Node m keys ((init trees) ++ [delete_max (last trees)])

さてさて、長くなってきたけど次はdelete_middleについて見てみよう。この関数では何をするかというと、渡されたノードの中に削除キーxがないことは判明しているので、再帰的に子部分木からキーを削除(delete_non_few)する。削除キーxが含まれるべき子部分木はt1であることは分かっているのでそこに再帰したいんだけど、その前にt1t2が "few" であるかによってmergeしたりshiftしたりする。mergeしたりshiftしたりすることによってt1は "few" ではなくなるので、安心してdelete_non_fewできる。

delete_middle :: (Ord a, Eq a) => Tree a -> a -> Tree a
delete_middle (Node m (k:ks) (t1:t2:ts)) x = if is_few t1 && is_few t2
                                               then Node m ks ((delete_non_few (merge k t1 t2) x):ts)
                                               else if is_few t1
                                                 then Node m (shifted_k:ks) ((delete_non_few shifted_t1 x):shifted_t2:ts)
                                                 else Node m (k:ks) ((delete_non_few t1 x):t2:ts)
                                               where Node _ [shifted_k] [shifted_t1, shifted_t2] = shift_left k t1 t2

delete_lastはほとんどdelete_middleと同じなんだけど、shift_leftじゃなくてshift_rightする。なぜかというと、もうそれより右の子部分木はないので、そこからshift_leftしてこれないため。delete_lastという名の通り、いま注目しているノードに含まれる子部分木のリストの最後の子部分木に再帰する。それ以外はほとんどdelete_middleと同じことをしている。

delete_last :: (Ord a, Eq a) => Tree a -> a -> Tree a
delete_last (Node m [k] [t1, t2]) x = if is_few t2 && is_few t1
                                        then Node m [] [delete_non_few (merge k t1 t2) x]
                                        else if is_few t2
                                          then Node m [shifted_k] [shifted_t1, (delete_non_few shifted_t2 x)]
                                          else Node m [k] [t1, (delete_non_few t2 x)]
                                        where Node _ [shifted_k] [shifted_t1, shifted_t2] = shift_right k t1 t2

以上で実装は終わり。場合分けが結構多いので複雑にはなってしまうんだけど、わかってしまえばやり方は単純で、ほとんど二分探索木のキーの削除と同じ。違うのはノードが "few" になったときにmergeしたりshiftしたりして "few" じゃなくしてからdelete_non_fewに渡すことくらい。その辺の場合分けでややこしくなっている。もっとイケてるかんじの書き方は当然あると思うんだけどあんまりhaskellでB-treeを実装してみたっていう記事がないのでよくわからない。

テスト

簡単にテスト。適当に作ったキーのリストを使ってB-treetを作る。で、その中から適当にキーを削除する。削除したキーをfindするとちゃんとFalseが返って来ていることが分かる。ちゃんと動いてるっぽいね。

*Main> :l btree
[1 of 1] Compiling Main             ( btree.hs, interpreted )
Ok, one module loaded.
*Main> keys = [2,234,746474,235,87876,6,756,65476876,65,658764534,1853,95149,24371,97,1234367252]
*Main> t = foldl insert (Nil 2) keys
*Main> t
Node 2 [87876] [Node 2 [6,234,756] [Leaf 2 [2],Leaf 2 [65,97],Leaf 2 [235],Leaf 2 [1853,24371]],Node 2 [65476876] [Leaf 2 [95149,746474],Leaf 2 [658764534,1234367252]]]
*Main> delete t 235
Node 2 [87876] [Node 2 [6,234,1853] [Leaf 2 [2],Leaf 2 [65,97],Leaf 2 [756],Leaf 2 [24371]],Node 2 [65476876] [Leaf 2 [95149,746474],Leaf 2 [658764534,1234367252]]]
*Main> find (delete t 235) 235
False
*Main> delete t 87876
Node 2 [24371] [Node 2 [6,234,756] [Leaf 2 [2],Leaf 2 [65,97],Leaf 2 [235],Leaf 2 [1853]],Node 2 [65476876] [Leaf 2 [95149,746474],Leaf 2 [658764534,1234367252]]]
*Main> find (delete t 87876) 87876
False

*1:適当な単語が思いつかなかったので "few" とした。

*2:実装がややこしくなってるのはこの終端処理のせいなんだけど、どうやったらうまく書けるんだろうか。