HaskellでB-treeを実装(delete編)
前回に引き続いて今回もHaskellでB-treeの実装。今回はキーの削除を実装する。前回同様 "Introduction to Algorithms" の実装方針に沿って実装する。前回はこちら。
コードはここにおいた
Haskell B-tree implementation · GitHub
shift と merge
キーの削除において重要な概念となるshift
とmerge
についてはじめに説明する。B-treeの定義より、各ノードはキーを (m-1) 個以上、 (2m-1) 個以下持たないといけない(m はB-treeのオーダー)。なので、キーを (m-1) 個しか持たないノードからそのままキーを削除することはできない。キーを (m-1) 個しか持たないノードをここでは "few" であると呼ぼう*1。キーを削除する前に、merge
とかshift
といった操作をすることによってノードを予め "few" でない状態にしておく。
まずはshift
について説明する。shift
にはshift_left
とshift_right
がある。下の図はshift_left
を図示している。左の子ノードは "few" であるため、そこからキーを削除することはできない。そこで、右の子ノード("few" でない)からキーを左に "シフト" することで "few" でない状態にする。ここで注意する点は、そのまま右の子ノードからキーを持ってくるのではなく、右のキーは親ノードへ、親ノードのキーを左の子ノードへシフトする。shift_right
についても同様なので、説明は省く。
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" なのでキーをシフトすることができない。そこで、親ノードの対応するキーも含めて子ノードふたつを "マージ" する。そうすることで、マージされたノードからキーを削除できるようになる。
merge
のコードは以下の通り。これも単純で、親ノードのキーと2つの子ノードを受け取って、マージされたノードを返すだけ。引数として渡されたノードがLeaf
かNode
かで場合分けしているけど、やっていることは本質的には同じ。
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 の実装
さて、shift
とmerge
の説明が終わったので、キーの削除を実装していく。まずはトップレベルの関数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) のときはt1
もt2
も "few" なので、それらをmerge
してまた再帰的にdelete_non_few
を呼ぶ。delete_min
にもdelete_max
にも "few" のノードを渡さない取り決めにしておくと実装が容易になるのでこうする。
get_min
、get_max
、delete_min
、delete_max
を定義する。これらの関数もシンプルなので特に説明はいらないと思う。get_min
とget_max
は渡された部分木の中で最も小さい(大きい)キーを返す。delete_min
とdelete_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
であることは分かっているのでそこに再帰したいんだけど、その前にt1
とt2
が "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