Left-Leaning Red-Black Tree by Java

※注意:このページはもう長い間メンテナンスされていません。 書いてあることと実際の状況が一致しない可能性があります。 参考にする人は自己責任でお願いします。

 このページは、 赤黒木 (2色木、red-black tree)の一種である Left-Leaning Red-Black Tree (LLRB Tree)の Java による実装を紹介するページです。 LLRB は赤黒木に赤ノードは常に左の子であるという条件を追加して、 挿入や削除時の修正パターンの数を減らしたアルゴリズムです。 プログラムがとても短くなります。

 LLRB は、発案者による Java のサンプルソースが Web 上に 公開されています が、そのコード品質がよろしくありません。 ごく簡単なテストでは問題は出ませんが、 ベンチマークのために大量のランダムデータを食わせたりすると、 NullPointerException で落ちてしまいます。

 私は LLRB を完全に理解しているわけではありませんが、 大まかに各部分が何をやっているかが分かるくらいには理解しています。 そこで、発案者の公開しているコードのあからさまにおかしな部分をデバッグして大量のランダムデータを食わせても落ちないように直してみました。 ダウンロードする人は このリンク からどうぞ。

 まだ完全にバグが取れていない可能性もありますが、 興味のある方は参考にしてください。 それにしても発案者はあのコードでベンチマークをしたんだろうかと不思議でなりません。

LLRB.java

 LLRB はプログラムは短くなりますが、 理論が難しくて簡単には理解できません。各メソッドの独立性が低く、 お互いが強く依存しあっています。 そのため部分部分を順番に理解するという戦略がうまく機能しません。 そういう意味では LLRB はあまり筋の良いアルゴリズムではないようです。

【備忘録】

 以下は、私自身のための備忘録です。 1ヶ月もすれば、過去の自分の書いたコードは赤の他人が書いたコードと同じで理解できなくなります。ここには、 未来の私がその時考えたことを思い出しやすくするためのメモを書きます。 私以外の人が読んでも参考になるかもしれませんが、基本的には私専用なので、 意味不明でもご了承ください。

 LLRB の delete() は普通の赤黒木と違って、 再帰の深くなる方向に処理が進む場合にも木を変形し色を塗り替えるのが特徴です。普通の赤黒木は再帰から戻ってくる時にのみ木を変形して色を塗り替えます。LLRB は言ってしまえば、 再帰の進行する方向で一度壊した赤黒木を再帰の戻りで修復することでバランスを取る平衡木です。

 moveRedLeft(), moveRedRight() はそれぞれ、 再帰の進む先に黒ノードしかない場合に、 色の塗り替えと回転を用いて再帰の進む先に赤ノードを生成するメソッドです。 このメソッドのお陰で、ノードの削除は常に赤ノードを削除することになり、 黒高さの減少を根(root)以外の部分で気にする必要がなくなります。

 delete() の中の


        if (isRed(h.left)) h = rotateRight(h);
        
というコードは、fixUp()h.color == RED かつ h.right.color == RED のパターンを 食わせないために必要です。また、木の末端で削除処理をするとき、 この条件がないと LLRB の条件が崩れてしまいます。

 赤ノードの子に赤ノードが連続する h.color == RED かつ h.left.color == RED のパターンが常に左部分木になるのは、


        if (isBlack(h.right) && !isRed(h.right.left)) h = moveRedRight(h);
        
というコードに関係があります。!isRed(h.right.left) のせいで、moveRedRight() から moveRedLeft() に切り替わる部分で赤ノードが連続することがなくなります。さらには、

        if (isRed(h.left)) h = rotateRight(h);
        
も関係しています。また、moveRedRight() で、 colorFlip() を2回実行するパターンでは、 1度比較したノードを再度比較することになり、 再帰で再び右の子を選ぶことになります。 これによっても、赤ノードの連続が右部分木になることが妨げられます。