Left-Leaning Red-Black Tree by Java

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

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

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

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

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

【備忘録】

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

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

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

　delete() の中の

        if (isRed(h.left)) h = rotateRight(h);
        

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

        if (isBlack(h.right) && !isRed(h.right.left)) h = moveRedRight(h);
        

        if (isRed(h.left)) h = rotateRight(h);