データ構造の範囲ツリー(レンジツリー)とは?仕組み・kd-treeとの違い・構築方法を解説

範囲ツリー(range tree)は、点の集合を格納するための順序付き木構造として定義されるデータ構造です。最大の特徴は、指定された範囲内に存在するすべての点を効率的に取得できる点にあり、実務では主に2次元以上の空間で実装されます。

範囲ツリーはkd-tree(kd木)とよく似た構造を持っていますが、両者には明確なトレードオフがあります。範囲ツリーはクエリ時間が O(log^d n + k) とkd-treeより高速である一方、必要な記憶領域は O(n log^d-1 n) と大きくなります。ここで、d は空間の次元数、n は木に格納されている点の総数、k は1回のクエリで取得される点の数を表します。

また、範囲ツリーは区間木(interval tree)とも混同されやすい存在ですが、両者は目的が異なります。範囲ツリーが「点」を格納し、与えられた範囲内の点を効率的に検索するのに対し、区間木は「区間」を格納し、与えられた1点を含む区間を効率的に検索するための構造です。

データ構造

1次元の点集合に対する範囲ツリーは、その点集合上の平衡二分探索木(balanced binary search tree)として扱われます。具体的には以下のような特徴を持ちます。

• 点そのものは木の葉(leaf)に格納される
• 各内部ノードは、自身の左部分木に含まれる最大値を保持する

一方、d次元の点集合に対する範囲ツリーは、再帰的に定義された多層の二分探索木として構成されます。データ構造の各レベルは、d個の座標のうちの1つに関する二分探索木として機能します。

まず第1レベルは、d個の座標のうち最初の座標に関する二分探索木となります。そして、この木の各頂点 v は、関連構造(auxiliary structure)として、v の部分木に格納された点の残り (d−1) 個の座標に関する (d−1) 次元の範囲ツリーを持ちます。この階層的な再帰構造こそが、多次元範囲検索を高速に実現する鍵となっています。

操作

構築(Construction)

n個の点の集合に対する1次元の範囲ツリーは単なる二分探索木であるため、O(n log n) の計算時間で構築できます。

高次元の範囲ツリーは、以下の手順で再帰的に構築されます。

1. 点の第1座標に関する平衡二分探索木を構築する
2. その木の各頂点 v について、v の部分木に含まれる点を対象とした (d−1) 次元の範囲ツリーを構築する

この方法で範囲ツリー全体を構築するには、O(n log^d n) の計算時間が必要となります。

応用分野

範囲ツリーは、計算幾何学、地理情報システム(GIS)、データベースの空間インデックス、コンピュータグラフィックスにおける衝突判定など、「ある範囲に含まれる対象を素早く列挙したい」という場面で広く活用されています。クエリ性能を重視するシステムにおいて、kd-treeの有力な代替手段となります。