二分探索木

3.1 二分探索木（BST）の定義

二分探索木 (BST) は、以下の特性を持つ二分木のことだよ:

• どんなノードでも、その左部分木には現在のノードのキーより小さいキーを持つノードのみが含まれる。
• どんなノードでも、その右部分木には現在のノードのキーより大きいキーを持つノードのみが含まれる。
• 各ノードの左右部分木もまた二分探索木である。

BSTの例:

BSTはBinary Search Treeの略。データを「ツリー」構造で整理していて、素早く検索できるのが特徴だよ。ツリーの構造は実際には隠れた/巧妙な要素の並べ替えなんだ。

中順走査 (in-order traversal)

走査の目的 — 特定の順序でノードのリスト（またはノードからのデータ、用語は実際の使用に関係がある）を形成すること。中順（対称）走査では、木の根が左部分木と右部分木の対応する走査結果の間に位置する。

二分探索木の特性（不等式について、理論を参照）とともに、これは中順走査がソートされたノードのリストを形成することを意味する — すごい！ 前に定義された木の走査はこんな感じになる:

3.2 BSTの動作原理と特性

動作原理:

• データの整理: BSTはデータを整理して効率的な検索、挿入、削除を可能にする。
• 再帰構造: BSTの各ノードはツリーの根と同じ規則に従い、構造は再帰的だよ。
• バランス: パフォーマンスを最適化するために、BSTはバランスが取れているべきで、つまり左右の部分木の高さがほぼ同じであるべき。

BSTの特性:

• 順序性: いつでも "in-order" 順に木を巡回できる （左部分木 → 現在のノード → 右部分木）、全ての要素をソートされた順に得ることができる。
• 操作の時間:
  • 平均して、検索、挿入、削除操作の実行時間はO(log n)。nはノードの数。
  • 最悪の場合（木がバランスされていない場合）、操作の実行時間はO(n)に達する。
• ユニークキー: BSTのすべてのキーは順序を保つためにユニークであるべき。

3.3 基本操作

1. 挿入 (Insertion):

動作原理:

• ルートノードから始める。
• 新しいノードのキーを現在のノードのキーと比較する。
• 新しいキーが小さい場合は左部分木に進み、大きい場合は右部分木に進む。
• 新しいノードの挿入に適した場所を見つけるまでプロセスを繰り返す（左右どちらかの子が存在しない場合）。

アルゴリズム:

1. 木が空の場合、新しいノードがルートノードになる。
2. そうでない場合は再帰的に正しい位置を見つけて新しいノードを追加。

2. 削除 (Deletion):

動作原理:

• 削除するノードを見つける。
• 3つの場合を考慮する:
• ノードが葉（子供がない）場合: 単にノードを削除。
• ノードが1つの子供を持つ場合: ノードをその子供に置き換える。
• ノードが2つの子供を持つ場合: 右部分木の最小ノード（または左部分木の最大ノード）を見つけ、その値を削除するノードにコピーし、再帰的に右部分木の最小ノードを削除。

アルゴリズム:

1. 指定されたキーを持つノードを見つける。
2. 場合に応じて対応する削除とノードの再配置を実行。

3. 検索 (Search):

動作原理:

• ルートノードから始める。
• 検索するノードのキーを現在のノードのキーと比較する。
• キーが一致したらノードを返す。
• キーが小さい場合は左部分木に進み、大きい場合は右部分木に進む。
• 検索するキーを持つノードを見つけるか、木の終わりに達するまでプロセスを繰り返す（この場合、ノードは見つからない）。

アルゴリズム:

1. 木が空であるか、ノードのキーが検索キーと一致する場合、ノードを返す。
2. 検索するノードのキーが小さい場合、再帰的に左部分木で検索。
3. 検索するノードのキーが大きい場合、再帰的に右部分木で検索。

3.4 BSTを使用して解く問題の例

1. 動的な集合での要素検索

数を追加したり、既存のものを削除したりして、与えられた数が集合にあるかどうかを素早く見つける必要がある。

BSTを用いた解決策:

• 新しい要素を木に挿入する。
• 既存の要素を削除する。
• 木の中の要素を検索する。

利用例:

システムで登録されたユーザーのリストを管理し、ユーザーが追加されたり削除されたりすることができ、システムがユーザーが登録されているかどうかを迅速に確認する必要がある。

2. 最小および最大要素の検索

データセットにおける最小および最大の値を迅速に見つける必要がある。

BSTを用いた解決策:

• 最小要素は木の最も左のノードにある。
• 最大要素は木の最も右のノードにある。

利用例:

株価を追跡するシステムをサポートし、現在の最小および最大価格を迅速に見つける必要がある。

3. 式のバランスチェック

数学的な式が与えられた場合、開きと閉じの括弧の数のバランスをチェックする必要がある。

BSTを用いた解決策:

括弧のバランスチェックの中間状態を保持するためにBSTを使用する。

利用例:

コードのパーシングとコンパイルにおいて、式の中で括弧が正しく配置されているかを確認する必要がある。

4. 辞書の作成

単語が追加され、削除され、そして迅速に見つけられる辞書を作成する必要がある。

BSTを用いた解決策:

• 単語はアルファベット順に木に追加される。
• 単語の検索はキーで行われる。

利用例:

テキストのオートコレクトシステムをサポートし、迅速に単語を見つけて修正する必要がある。