赤黒木の本質 - Qiita

この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思いついたのか見当がつかずとても不思議に感じました。 しかし、その後赤黒木の成り立ちやその基になったデータ構造について知ると、トリッキーに見えた定義がとても自然であることを実感しました。 おそらく知っている人は当たり前に知っている内容だとは思いますが、知らない人

[sh19910711]

2019 / "赤黒木の定義: 2-3-4木を学び、赤黒木が2-3-4木を二分木上でシミュレーションしているという本質を捉えると、その定義はとても自然に見えてくる / 印刷したときに赤が一番見栄えが良かった"

[ka2jun8]

ごっちゃんじゃん

[daichirata]

実装もそんなに難しくないので、木の回転とかの勉強には丁度良いと思う