[データ構造] 赤黒木
以前にまとめた赤黒木は以下です。 赤黒木 Red Black Tree 赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。 出...
「Red Black Tree」一覧
Red Black Tree / 赤黒木 (2)
以下の続きです。 ノードの挿入 Red Black Tree でノードの挿入は、以下の3つのステップで行われます。 普通の2分探索木の挿入を行う まずは、普通の2分探索木と同じように、ノードを挿入します。 挿入するノードの色を赤にする ...
Red Black Tree / 赤黒木 (1)
以下の動画がとても分かりやすいです。 Red Black Treeと同じ平衡2分探索木にAVL木があります。 AVL木では、「左右部分木の高さの差は１以下」というルールを設けて、木の高さの調節を行いました。 Red Black ...