二分探索木を辞書データ構造として実装する方法
抽象データ型としての辞書
抽象データ型である辞書(Dictionary)を実装する場合、各ノードに値を関連付けていくことになります。辞書とは、本質的には「全順序(total ordering)が定義された要素集合から取り出されたキーの集合」です。各キーには追加の情報(値)を関連付けることができますが、これは辞書の概念的理解には本質的には関わりません。
二分探索木の不変条件
辞書を木構造で実装する場合、各ノードは一意なキーを保持します。木の中の各ノード u に対して、左部分木 u.l 内のすべてのキーは u.k よりも厳密に小さく、右部分木 u.r 内のすべてのキーは u.k よりも厳密に大きい、という不変条件が成り立ちます。この不変条件に従って構成された木を「二分探索木(Binary Search Tree)」と呼びます。
中間順走査でソート済みキーリストを取得
この不変条件の大きな利点のひとつは、中間順走査(in-order traversal)を用いることで、ソート済みのキーリストを線形時間で取得できる点です。中間順走査は再帰的に次のように定義できます。
- 木が空であれば、何もしない
- そうでなければ、まず左部分木に対して再帰的に走査を行い、次に根(ルート)のキーを報告し、最後に右部分木に対して再帰的に走査を行う
二分探索木に対する操作
二分探索木に対しては、探索・挿入・削除など複数の操作を実行できます。探索は木の高さに依存して行われ、平衡な木であれば O(log n)、最悪ケース(木が連結リストのようになっている場合)では O(n) の時間計算量となります。探索は他のすべての操作の基盤となる、最も重要な操作です。
-
データ構造の範囲ツリー(レンジツリー)とは?仕組み・kd-treeとの違い・構築方法を解説
範囲ツリー(range tree)は、点の集合を格納するための順序付き木構造として定義されるデータ構造です。最大の特徴は、指定された範囲内に存在するすべての点を効率的に取得できる点にあり、実務では主に2次元以上の空間で実装されます。範囲ツリーはkd-tree(kd木)とよく似た構造を持っていますが、両者には明確なトレードオフがあります。範囲ツリーはクエリ時間が O(logd n + k) とkd-treeより高速である一方、必要な記憶領域は O(n logd-1 n) と大きくなります。ここで、d は空間の次元数、n は木に格納されている点の総数、k は1回のクエリで取得される点の数を表します
-
二分木（バイナリツリー）のデータ構造と重要な性質を解説
二分木（バイナリツリー）とは、各ノードが持てる子ノードの数を最大2つに制限した木構造のデータ構造です。本記事では、この二分木が持つ重要な性質について、具体例とともにわかりやすく解説します。まず、次のような二分木を例に考えてみましょう。二分木の主な性質各レベルの最大ノード数：レベル「l」における最大ノード数は 2l−1 です。ここでいうレベルとは、根（ルート）からそのノードまでの経路上にあるノードの総数を指し、ルート自身も含みます。なお、ルートのレベルは1として扱います。木全体の最大ノード数：高さ h の二分木に含まれる最大ノード数は 2h−1 です。ここでいう高さとは、ルートから葉までの経路上