|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 区 ： [く] 【名詞】 1. ward 2. district 3. section ・ 区間 ： [くかん] 1. (n,n-suf) section (of track, etc) 2. segment 3. dimension ・ 間 ： [けん, ま] 【名詞】 1. space 2. room 3. time 4. pause ・ 木 ： [き] 【名詞】 1. tree 2. wood 3. timber
区間木またはインターバル木（）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木（）があるが別物である。 == 基本的手法 == 単純なケースとして、区間が互いにオーバーラップしないなら、単純な2分木で表すことができ、クエリにかかる時間は O(log ''n'') となる。しかし、区間同士がオーバーラップするなら、始点でソートする場合と終点でソートする場合で順序が異なることになるので、挿入時に2つの区間をどう比較すべきかが問題となる。素朴な方法としては、同時に2つの木を作り、一方は始点でソートし、もう一方は終点でソートすればよい。これを使ってクエリを行うと、それぞれの木で O(log ''n'') の時間でオーバーラップする可能性のある区間をリストアップできるが、その結果をマージする必要があって、それには O(''n'') の時間がかかる。つまりクエリに対して O(''n'' + log ''n'') = O(''n'') の時間がかかることになり、力まかせ探索と比較すると全く改善されていない。 区間木はこの問題を解決するものである。以下では 'centered interval tree' と 'augmented tree' という2種類の設計を解説する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「区間木」の詳細全文を読む スポンサード リンク
|