Augmented treeとは? わかりやすく解説

Augmented tree

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/01/20 15:19 UTC 版)

区間木」の記事における「Augmented tree」の解説

別の手法は、Introduction to Algorithms, Second Editionの 14.3 章(pp.331–317First Edition は15.3章)に記述がある。 挿入削除にかかる時間は O(log n) である(n は区間総数)。 これは、単純な順序木(例え2分探索木平衡2分探索木)を使うもので、ノード順序各区間の始点下限の値)に従い、各ノードには区間終点上限)とそのノード配下部分木全体の最大上限値格納される。この情報挿入削除に際して保つには、O(h) ステップ(h はそのノードの高さ)の処理を行えばよく、上位ノードに対して最大値更新をしていく。 2つ区間 A と B がオーバーラップするのは、A.low ≤ B.high と A.high ≥ B.low が同時に成り立つ場合だけである。この木構造オーバーラップ探して走査していく場合、以下のような場合即座に除外できる。 右の子ノード始点下限)がクエリ終点上限より大きい場合それ以降部分木は走査する必要がない最大上限値クエリ始点より小さ部分木は走査する必要がない区間全体としては、まず始点の値でソートされ、次いで終点の値でソートされていることになる。この順序付け利用して区間二重登録を防ぐことができる。区間挿入は O(log n) だが、二重登録の検出には O(k + log n) がかかる(k は新たな区間オーバーラップしている区間数)。

※この「Augmented tree」の解説は、「区間木」の解説の一部です。
「Augmented tree」を含む「区間木」の記事については、「区間木」の概要を参照ください。

ウィキペディア小見出し辞書の「Augmented tree」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



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

辞書ショートカット

すべての辞書の索引

「Augmented tree」の関連用語

Augmented treeのお隣キーワード
検索ランキング

   

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



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

   
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの区間木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS