Augmented tree
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/20 15:19 UTC 版)
「区間木」の記事における「Augmented tree」の解説
別の手法は、Introduction to Algorithms, Second Editionの 14.3 章（pp.331–317、First 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のページへのリンク
