永続二色木

Purely Functional Data Structures の勉強会で説明した二色木(Red-black tree)に関するメモ。

Purely Functional Data Structures

Sedgewick らが発明した二色木は、もともと短命データとして設計されている。ある木に要素を挿入すると、赤が連続する、つまりバランスが崩れることがある。バランスを回復するときに、破壊的代入を最小限に抑えるために、複雑な作業を施さないといけない。

赤-赤と続く要素の下側を自分だと考える。すると、Sedgewick らのアルゴリズムでは、「伯父」の色も考慮するので、8通りの場合分けが必要になる。以下は、その内4通りを示してある。これと線対称のケースが4つある。

図の右側が Sedgewick らのアルゴリズム。つまり、命令的なアルゴリズム。青の星がついたところはまとめられるので、うまく実装すれば6通りの場合分けとなる。

このアルゴリズムを正しく実装するのは絶望的に難しい。学生の演習問題として出す場合は、まず先生が解いてからにすること！

左側が Okasaki のアルゴリズム。破壊操作をせずに、探索パス上のノードすべてを新たに作る。つまり、永続データの二色木。この場合は、伯父の色を気にしなくてもいいので、場合分けは4通りとなり、しかもHaskellのようにパターンマッチがあれば、コードは5行で済む。

balance :: Color -> a -> RBTree a -> RBTree a -> RBTree a
balance B z (Fork R y (Fork R x a b) c) d = Fork R y (Fork B x a b) (Fork B z c d)
balance B z (Fork R x a (Fork R y b c)) d = Fork R y (Fork B x a b) (Fork B z c d)
balance B x a (Fork R y b (Fork R z c d)) = Fork R y (Fork B x a b) (Fork B z c d)
balance B x a (Fork R z (Fork R y b c) d) = Fork R y (Fork B x a b) (Fork B z c d)
balance c y l r = Fork c y l r

これは、気軽に演習問題にできるレベル。

図を描いて気付いたけど、Sedgewick と Okasaki のアルゴリズムは、挿入の際に違う木を生成する。(単にこれが言いたかった。)