区間木

提供: ORWiki
2007年7月12日 (木) 02:56時点における131.112.125.103 (トーク)による版
ナビゲーションに移動 検索に移動

【くかんぎ (interval tree)】

整数区間を根に対応させ, 以下その区間をほぼ二等分しながら左右の子に対応させていきながら単位長さの区間の集合に分割する分割法を木構造のデータ構造で表現したもの. %区間木のノードにはそれぞれ分割に対応する整数区間が付随する. さらにの与えられた部分区間の集合をこの対応に基づいて適切に記憶することにより, 区間の集合に対する探索をサポートする効率的なデータ構造が得られる. それを用いれば, 個の区間の集合に対して, 質問点を含む の区間をすべて求める問題などが%区間木を用いて効率的に解ける.