2色木とは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > 2色木の意味・解説 

2色木

読み方にしょくぎ
【英】:red black tree

平衡二分探索木一種で, (1) すべての頂点は赤か黒, (2) 赤い頂点は必ず黒い親をもつ, (3) 根とすべてのは黒, (4) 根からへのどのパス同数の黒い頂点を含む, という4つの条件満たす. 赤黒木ともいう. この条件より, 根からへのどのパスも, 長さが2倍以上違わなくなり, ゆえに要素n \, 赤黒木の高さは O(\log n) \,になる. 赤黒木は, 木の形の変化に対して平衡化を行うことにより, 要素挿入削除・ある要素含まれるかの確認 O(\log n) \,実行できる.


赤黒木

(2色木 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/01/25 05:35 UTC 版)

赤黒木(あかくろぎ)は、コンピュータ科学データ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木レッド・ブラック・ツリーともいう。


  1. ^ a b c d James Paton. “Red–Black Trees”. 2021年12月22日閲覧。
  2. ^ a b リバラシングのみ (検索は無し)、Tarjan and Mehlhornを参照。
  3. ^ 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. http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/SortedSequences.pdf 
  4. ^ 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 
  5. ^ Tarjan, Robert Endre (April 1985). “Amortized Computational Complexity”. SIAM Journal on Algebraic and Discrete Methods 6 (2): 306–318. doi:10.1137/0606031. http://www.cs.duke.edu/courses/fall11/cps234/reading/Tarjan85_AmortizedComplexity.pdf. 
  6. ^ a b 左の列は右の列よりはるかに少ないノードしか含まず、特に削除の場合はそうである。これは、挿入と削除のリバランシングループから最初の反復を引き出すことで、ある程度の効率を得られることを示している。なぜなら、名前付きノードの多くは最初の反復ではNILノードであり、後で決定的に非NILノードとなるからである。(この章のコメントを参照.)
  7. ^ わかりやすくするために、回転は再色付けの前に行われる。しかし、この2つのアクションは可換であるため、回転を末尾に行うことも自由である。
  8. ^ a b Ben Pfaffでも同じような分割が見られる。
  9. ^ Dinesh P. Mehta, Sartaj Sahni (Ed.) Handbook of Data Structures and Applications 10.4.2




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「2色木」の関連用語

2色木のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



2色木のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2024 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの赤黒木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2024 GRAS Group, Inc.RSS