翻訳と辞書
Words near each other
・ 区間の分割
・ 区間乗車券
・ 区間列車
・ 区間券
・ 区間券番号
・ 区間快車
・ 区間快速
・ 区間快速急行
・ 区間急行
・ 区間推定
区間木
・ 区間準急
・ 区間特定運賃
・ 区間特急
・ 区間車
・ 区麗情
・ 医
・ 医(学)進(学)課程(大学の)
・ 医の倫理
・ 医の倫理、生命倫理


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

区間木 : ミニ英和和英辞書
区間木[くかんき]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [く]
 【名詞】 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)
ウィキペディアで「区間木」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.