数としての赤黒木 - エムスリーテックブログ

エンジニアリンググループの高島（@rst76）です。社内の勉強会で、計算機科学の有名な教科書、アルゴリズムイントロダクション（Introduction to Algorithms）を輪読しています。ちょうど赤黒木の章を私が担当したので、要点をかいつまんでご紹介したいと思います。今回お話したいのは「ある条件の下で、赤黒木は記数法表現と見ることができる」という話です。

f:id:rst76:20191018182114p:plain — 赤黒木の例

赤黒木

二分木というデータ構造があります。計算機科学では一般的なデータ構造で、ランダムなデータであれば、検索や挿入などの操作を $O(\log n)$ で実現できます。ただ、データの与え方によっては偏った木ができてしまうことがあり、そうすると各操作の性能が $O(n)$ に落ちてしまうので、どうやって木の平衡性を維持するかが課題です。

赤黒木は二分木の一種で、ノード（節点）を赤と黒に塗り分けて、赤と黒の組み合わせによって平衡性を保つための調整をします。具体的には、ルート（根）からリーフ（末端）までの経路を見ていったときに、黒いノードが必ず同じ数だけ含まれるように、かつ赤いノードが連続しないようにすることで、最長の経路でも最短の経路の 2 倍以下になるように調整します。

f:id:rst76:20191018131422p:plain — 赤黒木の経路の長さ

アルゴリズムイントロダクションにはこの調整のアルゴリズムが載っています。 Wikipedia にも取り上げられている *1くらい有名なアルゴリズムなのですが、少々複雑で分かりにくいものとなっています。実はもっと簡潔な調整アルゴリズムもあって、それが純粋関数型データ構造（Purely Functional Data Structures）という書籍に書かれています。紙面の都合上ここで詳しい説明はできませんが、興味のある方は、ぜひ読んでみてください。英語の論文であれば、インターネットでも参照できます（Red-Black Trees in a Functional Setting）。

ちなみに、Java の TreeMap や Scala の mutable な TreeMap はアルゴリズムイントロダクション方式、Scala の immutable な TreeMap は純粋関数型データ構造方式です。

赤黒木の構築

ためしに赤黒木を実際に構築してみます。純粋関数型データ構造に載っている方法に従い、空の赤黒木に 1 から 8 までの数を順に挿入していくと、以下のような木ができあがります（図は 45 度回転させていますが、左上がルートです）。ルートからたどると、1 つの木の中ではリーフまでのどの経路にも、同じ数の黒いノードが含まれることが分かると思います。

f:id:rst76:20191018131410p:plain — 1 から 8 までの数を順に挿入したときにできる赤黒木

ゼロなし二進数

それでは、このエントリの主題である「ある条件の下で、赤黒木は記数法表現と見ることができる」という話をしたいと思います。これは純粋関数型データ構造の演習問題 9.7 なのですが、論文にもなっている（Constructing Red-Black Trees）ので、詳しく知りたい方はそちらを参照してください。

どういうことでしょうか？

記数法表現だということは数を表す表現だということです。二分木なので二進数と対応しているということでしょうか。というわけで、二進数についてちょっと考えてみます。

二進数は 0 と 1 で表現するのが一般的ですが、正の数を表現するのであれば、必ずしも 0 を使う必要はありません。たとえば 1 と 2 だけを使って表現することもできて、それがゼロなし二進数です。十進数の 4 は、 $1 \times 2^{2} + 0 \times 2^{1} + 0 \times 2^{0}$ なのでふつうの二進数では $100$ になりますが、ゼロなし二進数だと $\times$ の左側の数に $0$ を使えないので、 $1 \times 2^{1} + 2 \times 2^{0}$ で $12$ になります。同様に、十進数の 1 から 8 に対応するゼロなし二進数は、それぞれ以下のようになります。