赤黒木
の赤黒木の高さは
になる．赤黒木は，木の形の
赤黒木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/25 05:35 UTC 版)
赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。
- ^ a b c d James Paton. “Red–Black Trees”. 2021年12月22日閲覧。
- ^ a b リバラシングのみ (検索は無し)、Tarjan and Mehlhornを参照。
- ^ a b c Mehlhorn, Kurt; Sanders, Peter (2008). “7. Sorted Sequences”. Algorithms and Data Structures: The Basic Toolbox. Berlin/Heidelberg: Springer. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3
- ^ Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). “13. Red–Black Trees”. Introduction to Algorithms (3rd ed.). MIT Press. pp. 308–309. ISBN 978-0-262-03384-8
- ^ Tarjan, Robert Endre (April 1985). “Amortized Computational Complexity”. SIAM Journal on Algebraic and Discrete Methods 6 (2): 306–318. doi:10.1137/0606031.
- ^ a b 左の列は右の列よりはるかに少ないノードしか含まず、特に削除の場合はそうである。これは、挿入と削除のリバランシングループから最初の反復を引き出すことで、ある程度の効率を得られることを示している。なぜなら、名前付きノードの多くは最初の反復ではNILノードであり、後で決定的に非NILノードとなるからである。（この章のコメントを参照.）
- ^ わかりやすくするために、回転は再色付けの前に行われる。しかし、この2つのアクションは可換であるため、回転を末尾に行うことも自由である。
- ^ a b Ben Pfaffでも同じような分割が見られる。
- ^ Dinesh P. Mehta, Sartaj Sahni (Ed.) Handbook of Data Structures and Applications 10.4.2
[続きの解説]
- 赤黒木のページへのリンク
