アルゴリズムクイックリファレンス 第2版

5.5

 二分探索木

■

133

も二次記憶に置かれたときにも性能が出て、ハッシュ表ではできないような、ある

範囲の要素を整列して返すことが可能である。探索木で最もよく使われるのは、二

分探索木（

binary search tree

：

BST

）で、図5-7に示すような節点

(node)

で構成さ

れる。各節点は、集まりの

1

つの値を保持し、高々

2

つの子節点、

left

と

right

へ

の参照を格納する。

次のような場合に二分探索木を使う。

●

データを昇順（または降順）に走査しなければならない。

●

データセットのサイズが未知であり、実装はメモリに格納できる限りは、ど

のようなサイズでも扱えないといけない。

●

データセットは高度に動的であり、集まりの生存期間において多くの挿入削

除が予期される。

5.5.1

 入出力

探索木を使うアルゴリズムの入出力は、

二分探索

と同じである。探索木に貯えら

れる集まり

C

の各要素

e

は、キー

k

として使われる

1

つ以上のプロパティを持つ必要

がある。キーは全体

U

を構成し、完全に順序付けられなければならない。すなわち、

2

つのキー値

k

i

と

k

j

について、

k

i

＝

k

j

, k

i

＞

k

j

, k

i

＜

k

j

のいずれかが成り立つ。

集まりの値が（文字列や整数のような）基本型なら、値そのものがキー値になりう

る。さもなければ、キー値を含む構造体への参照となる。

5.5.2

 文脈

二分探索木

BST

は、キーと呼ばれる順序値を持つ節点の空でない集まりであ

る。頂点の根（

root node

）は、

BST

の他のすべての節点の先祖（

ances ...