Binary Search Tree（BST）は、各ノードが最大2つの子ノードを持つ二分木の一種です。BSTの特徴は、左部分木のすべてのノードの値は親ノードより小さく、右部分木のすべてのノードの値は親ノードより大きいということです。
- ノード（Node）: 各ノードには値（key）、左の子ノード、右の子ノードの3つの要素が含まれます。
- ルート（Root）: 木の最上部にあるノード。
- リーフ（Leaf）: 子ノードを持たないノード。
以下に、基本的なBSTの実装を示します。
// ノードの定義
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// BSTの定義
class BinarySearchTree {
constructor() {
this.root = null;
}
// ノードの挿入
insert(value) {
const newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value === current.value) return undefined; // 重複を許可しない場合
if (value < current.value) {
if (current.left === null) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (current.right === null) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
// ノードの検索
find(value) {
if (this.root === null) return false;
let current = this.root;
while (current) {
if (value === current.value) {
return current;
}
if (value < current.value) {
current = current.left;
} else {
current = current.right;
}
}
return false; // 見つからなかった場合
}
// 中順走査（In-Order Traversal）
inOrderTraversal(node = this.root, result = []) {
if (node !== null) {
this.inOrderTraversal(node.left, result);
result.push(node.value);
this.inOrderTraversal(node.right, result);
}
return result;
}
}
// 使用例
const bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
console.log('In-Order Traversal:', bst.inOrderTraversal()); // [20, 30, 40, 50, 60, 70, 80]
console.log('Find 60:', bst.find(60)); // Node { value: 60, left: null, right: null }
console.log('Find 100:', bst.find(100)); // false-
高速な探索
- 平衡状態にある場合、探索、挿入、削除の時間計算量は (O(\log n))。
-
動的データ管理
- 配列のようにサイズを固定せず、動的にデータを追加・削除できる。
-
順序付きデータの管理
- 中順走査（In-Order Traversal）により、常にソートされた順序でデータを取り出せる。
-
効率的な範囲検索
- 特定の範囲内のデータを効率的に取得可能。
-
アンバランスな木の問題
- 挿入順によっては線形構造（Linked List） に近くなり、最悪の場合 (O(n)) の性能になる。
-
平衡の維持が必要
- 高速な操作を維持するためには、自己平衡二分探索木（例: AVL木、Red-Black木）などが必要で、実装が複雑になる。
-
大量データには不向き
- データ量が非常に多い場合や頻繁な挿入・削除が発生する場合、バランス維持のコストが高くなる。
-
データベースのインデックス
- データベース管理システムで効率的なデータ検索を実現するために使用。
-
ソートアルゴリズム
- 中順走査を用いて配列をソートするTree Sort。
-
レンジクエリ
- 数値の範囲内での検索が必要なアプリケーション（例: スコアフィルタリング）。
-
ファイルシステム
- ファイルやディレクトリの構造管理に使われることがある。
-
補完機能（オートコンプリート）
- 部分一致検索などの補助的なデータ構造として利用。
自己平衡二分探索木は、挿入や削除の後に木の高さを一定に保つことでパフォーマンス劣化を防ぎます。
- AVL木: 各ノードの部分木の高さ差が1以下になるよう調整。
- Red-Black木: ノードに色を付けて木の高さバランスを保つ。
- B木/B+木: データベースやファイルシステムでの大量データ管理に適用。
- メリット: 高速な検索、動的データ管理、順序付けデータの効率的な管理。
- デメリット: アンバランスな木によるパフォーマンス低下、自己平衡木の実装の複雑さ。
- 活用例: データベース、ファイルシステム、オートコンプリート、レンジクエリなど。