基本的手法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/20 15:19 UTC 版)
単純なケースとして、区間が互いにオーバーラップしないなら、単純な2分木で表すことができ、クエリにかかる時間は O(log n) となる。しかし、区間同士がオーバーラップするなら、始点でソートする場合と終点でソートする場合で順序が異なることになるので、挿入時に2つの区間をどう比較すべきかが問題となる。素朴な方法としては、同時に2つの木を作り、一方は始点でソートし、もう一方は終点でソートすればよい。これを使ってクエリを行うと、それぞれの木で O(log n) の時間でオーバーラップする可能性のある区間をリストアップできるが、その結果をマージする必要があって、それには O(n) の時間がかかる。つまりクエリに対して O(n + log n) = O(n) の時間がかかることになり、力まかせ探索と比較すると全く改善されていない。 区間木はこの問題を解決するものである。以下では 'centered interval tree' と 'augmented tree' という2種類の設計を解説する。
※この「基本的手法」の解説は、「区間木」の解説の一部です。
「基本的手法」を含む「区間木」の記事については、「区間木」の概要を参照ください。
ウィキペディア小見出し辞書の「基本的手法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 基本的手法のページへのリンク
