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