データ構造の区間木（インターバルツリー）とは？基本概念をわかりやすく解説
区間木（インターバルツリー）とは
この記事では、データ構造の一つである「区間木（Interval Tree）」について解説します。その名の通り、区間木は「区間」に関連付けられた木構造です。区間木の仕組みを理解するために、まず前提となる「基本区間」の考え方から確認していきましょう。
区間の基本
区間とは、ある値の範囲を表すものです。例えば、区間が [a, b] と表記されている場合、それは a から始まり b で終わる範囲を意味します。
ここで、区間 [10, 20] を例に考えてみます。このとき、数直線上には次の3つの範囲が存在します。
- −∞ から 10 まで
- 10 から 20 まで
- 20 から +∞ まで
複数の区間を重ねてみる
次に、新たな区間 [15, 25] を追加してみましょう。既存の区切り点と組み合わさることで、より細かい部分区間が生まれます。
さらに、区間 [18, 22] を追加すると、以下のようになります。
区間と部分区間の一覧
これらの区間と、そこから導かれる部分区間は、次の表のように整理できます。
| 区間名 | 区間の範囲 | 部分区間 |
| 区間1 | [10, 20] | [10, 15]、[15, 18]、[18, 20] |
| 区間2 | [15, 25] | [15, 18]、[18, 20]、[20, 22]、[22, 25] |
| 区間3 | [18, 22] | [18, 20]、[20, 22] |
区間木の構築方法
以上の情報をもとに、区間木を構築することができます。各部分区間は、木の中ではサブツリーとして配置されます。
区間木では、すべての葉ノードがそれぞれの基本区間に対応します。そして、これらの葉ノードの上層に、完全二分木が構築されます。
このような構造により、区間木は「ある点や区間と重なる区間を効率的に検索したい」という場面で威力を発揮します。計算幾何学やデータベースのインデックスなど、さまざまな分野で応用されている重要なデータ構造です。
-
データ構造の範囲ツリー(レンジツリー)とは?仕組み・kd-treeとの違い・構築方法を解説
範囲ツリー(range tree)は、点の集合を格納するための順序付き木構造として定義されるデータ構造です。最大の特徴は、指定された範囲内に存在するすべての点を効率的に取得できる点にあり、実務では主に2次元以上の空間で実装されます。範囲ツリーはkd-tree(kd木)とよく似た構造を持っていますが、両者には明確なトレードオフがあります。範囲ツリーはクエリ時間が O(logd n + k) とkd-treeより高速である一方、必要な記憶領域は O(n logd-1 n) と大きくなります。ここで、d は空間の次元数、n は木に格納されている点の総数、k は1回のクエリで取得される点の数を表します
-
データ構造における高さ制限付きハフマンツリーの基礎と実装上の課題
高さ・深さ制限付きハフマンツリーとは 高さ（深さ）に制限を設けたハフマンツリーの構成図は、下図のとおりです。 木の深さの制限は一見単純な問題に思われますが、実際のハフマン符号化の実装においては、多くの場合に対処すべき重要な課題となります。 標準的なハフマン構築には深さの制限がない 標準的なハフマン木の構築アルゴリズムは、木の高さや深さを一切制限しません。仮に深さを制限すると、「最適（オプティマル）」な符号 rather ではなくなるためです。ただし、ハフマン木の最大深度はフィボナッチ数列によって理論的な上限が定められており、際限なく深くなることはありません。それでも、実用上望まれる深さを大