翻訳と辞書 Words near each other ・ インソール ・ インタアーバン ・ インタウィチャヤーノン ・ インタウィチャヤーノン公 ・ インタウィチャヤーノン王 ・ インタグリオー ・ インタゲ ・ インタッチ・ホールディングス ・ インタノン山 ・ インタノン山国立公園 ・ インタバル木 ・ インタビュアー ・ インタビュー ・ インタビューフォーム ・ インタビューボード ・ インタビュー・ウィズ・バンパイア ・ インタビュー・ウィズ・ヴァンパイア ・ インタファクス ・ インタファクス通信 ・ インタファックス通信 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク インタバル木 ： ウィキペディア日本語版 区間木[くかんき] 区間木またはインターバル木（）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、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）』 ■ウィキペディアで「区間木」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Interval tree 」があります。 スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.