K-d木

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

【けいでぃーき ( tree)】


与えられた点集合に基づいて 次元の空間の領域分割を表現するデータ構造である. 根に全体領域が対応し, その左右の子には第1座標に注目して左右に二等分された点集合の領域が対応する. 次に分割された左(右)点集合領域を第2座標に基づいて上下に二等分しそれぞれ左(右)の子の左右の子に対応させる. 以下同様に分割し, 領域に点が1個になったら分割を終了する. この分割法を表現したものが -木である.