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

エンジニアリンググループの高島（@rst76）です。 社内の勉強会で、計算機科学の有名な教科書、アルゴリズムイントロダクション（Introduction to Algorithms）を輪読しています。 ちょうど赤黒木の章を私が担当したので、要点をかいつまんでご紹介したいと思います。 今回お話したいのは「ある条件の下で、赤黒木は記数法表現と見ることができる」という話です。 赤黒木の例 赤黒木 二分木というデータ構造があります。 計算機科学では一般的なデータ構造で、ランダムなデータであれば、検索や挿入などの操作を で実現できます。 ただ、データの与え方によっては偏った木ができてしまうことがあり、そうすると各操作の性能が に落ちてしまうので、どうやって木の平衡性を維持するかが課題です。 赤黒木は二分木の一種で、ノード（節点）を赤と黒に塗り分けて、赤と黒の組み合わせによって平衡性を保つための調整を

[hkdnet]

“なお純粋関数型データ構造には、他にも 0, 1, 2, 3, 4 を使う二進数（！）や三進数（ともちろんそれらに対応するデータ構造）が出てきます。 ワクワクしますよね。ぜひ読んでみてください。”