「区間木」の版間の差分
ナビゲーションに移動
検索に移動
細 ("区間木" を保護しました。 [edit=sysop:move=sysop]) |
|||
| 1行目: | 1行目: | ||
'''【くかんぎ (interval tree)】''' | '''【くかんぎ (interval tree)】''' | ||
| − | 整数区間<math>I\,</math>を根に対応させ, 以下その区間をほぼ二等分しながら左右の子に対応させていきながら単位長さの区間の集合に分割する分割法を木構造のデータ構造で表現したもの. | + | 整数区間<math>I\,</math>を根に対応させ, 以下その区間をほぼ二等分しながら左右の子に対応させていきながら単位長さの区間の集合に分割する分割法を木構造のデータ構造で表現したもの. 区間木のノードにはそれぞれ分割に対応する整数区間が付随する. さらに<math>I\,</math>の与えられた部分区間の集合<math>\mathcal{I}\,</math>をこの対応に基づいて適切に記憶することにより, 区間の集合に対する探索をサポートする効率的なデータ構造が得られる. それを用いれば, <math>n\,</math>個の区間の集合<math>\mathcal{I}\,</math>に対して, 質問点<math>x\,</math>を含む <math>\mathcal{I}\,</math> の区間をすべて求める問題などが区間木を用いて効率的に解ける. |
2007年7月20日 (金) 09:30時点における版
【くかんぎ (interval tree)】
整数区間を根に対応させ, 以下その区間をほぼ二等分しながら左右の子に対応させていきながら単位長さの区間の集合に分割する分割法を木構造のデータ構造で表現したもの. 区間木のノードにはそれぞれ分割に対応する整数区間が付随する. さらにの与えられた部分区間の集合をこの対応に基づいて適切に記憶することにより, 区間の集合に対する探索をサポートする効率的なデータ構造が得られる. それを用いれば, 個の区間の集合に対して, 質問点を含む の区間をすべて求める問題などが区間木を用いて効率的に解ける.
