二分探索木 (BST)
最終更新
二分探索木は値をソートされた状態で保持します。どのノードでも、左部分木のすべての値はそれより小さく、右部分木のすべての値はそれより大きくなります。値を挿入または検索するには、根から始めて比較に応じて左または右へ繰り返し進むため、各ステップで探索範囲が半分になります。上の再生ボタンを押すと、値が比較によって配置され、探索が木を下っていく様子を見られます。
平衡木ではこれらの操作は O(log n) 時間で実行されます。落とし穴として、すでにソート済みのデータを挿入すると木は連結リストに退化し、操作が O(n) になります。まさにこのために AVL 木や赤黒木のような自己平衡木が存在します。
時間計算量と空間計算量
| 操作 | 平衡時 | 最悪の場合 (偏った木) |
|---|---|---|
| 探索 | O(log n) | O(n) |
| 挿入 | O(log n) | O(n) |
| 削除 | O(log n) | O(n) |
| 空間 | O(n) | O(n) |
ステップごと (挿入)
| ステップ | 何が起こるか |
|---|---|
| 1 | 木が空なら、新しい値が根になる。 |
| 2 | そうでなければ根から始める。 |
| 3 | 値が小さければ左の子へ、大きければ右へ進む。 |
| 4 | 空いている場所に到達するまで繰り返す。 |
| 5 | そこに新しい値を葉として付け加える。 |
具体例
空の木に [5, 3, 8, 1, 4] を1つずつ挿入する場合:
| 挿入 | たどった経路 | 動作 |
|---|---|---|
5 | - | 木が空なので 5 が根になる。 |
3 | 5 | 3 < 5 なので左へ進む。場所が空いているので 3 を 5 の左の子として付ける。 |
8 | 5 | 8 > 5 なので右へ進む。場所が空いているので 8 を 5 の右の子として付ける。 |
1 | 5 -> 3 | 1 < 5 で左へ、次に 1 < 3 で左へ進む。1 を 3 の左の子として付ける。 |
4 | 5 -> 3 | 4 < 5 で左へ、次に 4 > 3 で右へ進む。4 を 3 の右の子として付ける。 |
二分探索木を使うべきとき
| 使うとき | 避けるとき |
|---|---|
| ソート順と高速な検索の両方が必要で、挿入がランダムな順序で来る。 | データがすでにソート済みで来る: 偏った BST は操作あたり O(n) に劣化する。 |
| 中間順巡回で値をソート済みの並びとして無料で得たい。 | 順序なしで所属判定だけが必要: ハッシュテーブルは平均 O(1) の検索を提供する。 |
| 範囲クエリやキーの後続/先行が必要。 | 保証された O(log n) の上限が必要: 代わりに自己平衡な AVL 木や赤黒木を使う。 |
| データ集合が頻繁に変わり、静的なソート済み配列の更新が高コストになる。 | データ集合が固定で読み取り専用: 二分探索付きのソート済み配列の方が単純でキャッシュに優しい。 |
Binary Search Treeのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なBinary Search Treeの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのBinary Search Treeのコード
Python
1class Node:2 def __init__(self, key):3 self.key = key4 self.left = None5 self.right = None6
7
8def insert(node, key):9 if node is None:10 return Node(key)11 if key < node.key:12 node.left = insert(node.left, key)13 elif key > node.key:14 node.right = insert(node.right, key)15 return node # duplicates are ignored16
17
18def search(node, key):19 if node is None:20 return False21 if key == node.key:22 return True23 if key < node.key:24 return search(node.left, key)25 return search(node.right, key)26
27
28def inorder(node):29 if node is None:30 return []31 return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36 root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))JavaScriptでのBinary Search Treeのコード
JavaScript
1class Node {2 constructor(value) {3 this.value = value;4 this.left = null;5 this.right = null;6 }7}8
9class BinarySearchTree {10 constructor() {11 this.root = null;12 }13
14 insert(value) {15 const attach = (node) => {16 if (!node) return new Node(value);17 if (value < node.value) node.left = attach(node.left);18 else node.right = attach(node.right);19 return node;20 };21 this.root = attach(this.root);22 }23
24 search(value) {25 let current = this.root;26 while (current) {27 if (value === current.value) return true;28 current = value < current.value ? current.left : current.right;29 }30 return false;31 }32
33 // Inorder traversal of a BST visits values in sorted order34 inorder(node = this.root, out = []) {35 if (!node) return out;36 this.inorder(node.left, out);37 out.push(node.value);38 this.inorder(node.right, out);39 return out;40 }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));JavaでのBinary Search Treeのコード
Java
1public class Main {2 static class Node {3 int key;4 Node left, right;5 Node(int key) { this.key = key; }6 }7
8 static Node insert(Node node, int key) {9 if (node == null) return new Node(key);10 // Smaller keys go left, larger keys go right11 if (key < node.key) node.left = insert(node.left, key);12 else if (key > node.key) node.right = insert(node.right, key);13 return node;14 }15
16 static boolean search(Node node, int key) {17 if (node == null) return false;18 if (key == node.key) return true;19 return key < node.key ? search(node.left, key) : search(node.right, key);20 }21
22 static void inorder(Node node, StringBuilder sb) {23 if (node == null) return;24 inorder(node.left, sb);25 sb.append(node.key).append(" ");26 inorder(node.right, sb);27 }28
29 public static void main(String[] args) {30 Node root = null;31 int[] keys = {8, 3, 10, 1, 6, 14, 4};32 for (int k : keys) root = insert(root, k);33
34 StringBuilder sb = new StringBuilder();35 inorder(root, sb);36 System.out.println("Inorder (sorted): " + sb.toString().trim());37 System.out.println("search 6: " + search(root, 6));38 System.out.println("search 7: " + search(root, 7));39 }40}C++でのBinary Search Treeのコード
C++
1#include <iostream>2
3struct Node {4 int value;5 Node* left = nullptr;6 Node* right = nullptr;7 explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11 if (root == nullptr) return new Node(value);12 if (value < root->value) root->left = insert(root->left, value);13 else if (value > root->value) root->right = insert(root->right, value);14 return root; // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18 // Walk down: smaller goes left, larger goes right19 while (root != nullptr) {20 if (value == root->value) return true;21 root = value < root->value ? root->left : root->right;22 }23 return false;24}25
26void inorder(const Node* node) {27 if (node == nullptr) return;28 inorder(node->left);29 std::cout << node->value << " ";30 inorder(node->right);31}32
33int main() {34 Node* root = nullptr;35 for (int value : {50, 30, 70, 20, 40, 60, 80}) {36 root = insert(root, value);37 }38 std::cout << "Sorted: ";39 inorder(root);40 std::cout << "\n" << std::boolalpha;41 std::cout << "contains(40): " << contains(root, 40) << "\n";42 std::cout << "contains(45): " << contains(root, 45) << "\n";43 return 0;44}CでのBinary Search Treeのコード
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6 int value;7 struct Node* left;8 struct Node* right;9} Node;10
11Node* newNode(int value) {12 Node* n = malloc(sizeof(Node));13 n->value = value;14 n->left = n->right = NULL;15 return n;16}17
18Node* insert(Node* root, int value) {19 if (root == NULL) return newNode(value);20 if (value < root->value) root->left = insert(root->left, value);21 else if (value > root->value) root->right = insert(root->right, value);22 return root; // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26 // Walk down: smaller goes left, larger goes right27 while (root != NULL) {28 if (value == root->value) return true;29 root = value < root->value ? root->left : root->right;30 }31 return false;32}33
34void inorder(const Node* node) {35 if (node == NULL) return;36 inorder(node->left);37 printf("%d ", node->value);38 inorder(node->right);39}40
41int main(void) {42 int values[] = {50, 30, 70, 20, 40, 60, 80};43 Node* root = NULL;44 for (int i = 0; i < 7; i++) root = insert(root, values[i]);45 printf("Sorted: ");46 inorder(root);47 printf("\n");48 printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49 printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50 return 0;51}二分探索木のよくある質問
二分探索木の時間計算量は?
平衡木では探索・挿入・削除は
O(log n) です。各比較で残りのノードの半分を捨てるためです。最悪の場合 — ソート済み挿入によって鎖状に偏った木 — では O(n) に劣化します。二分木と二分探索木の違いは?
二分木は各ノードが最大2つの子を持つ木のことで、順序の規則はありません。二分探索木は、左部分木の値がノードより小さく、右部分木の値が大きいという不変条件を加えます。これが高速な検索を可能にします。
二分探索木はなぜ遅くなることがあるのか?
値がソート順 (または逆順) で挿入されると、新しいノードが毎回同じ側に付き、連結リストのように振る舞う高く偏った木になります — 操作あたり
O(n) です。自己平衡木 (AVL、赤黒木) はこれを防ぐためにノードを回転させます。二分探索木とハッシュテーブルの違いは?
ハッシュテーブルは平均
O(1) の検索を提供しますが、キーを特定の順序で保持しないため、範囲クエリや後続クエリには答えられません。二分探索木は O(log n) とわずかに遅いですが、キーを順序付きで保持するので順に巡回したり最も近い値を見つけたりできます。順序が重要なら BST を、所属判定だけが必要ならハッシュテーブルを選びましょう。単純な BST の代わりに自己平衡木を使うべきなのはいつ?
挿入順序を制御できず、保証された
O(log n) 性能が必要なときは常に自己平衡木 (AVL、赤黒木) を使いましょう。単純な BST は教育用、小さなデータ集合、あるいはキーがランダムな順序で来る場合には十分ですが、偏った最悪の場合への保護はありません。BST の中間順巡回はソート済みの値を返すのか?
はい。左部分木、次にノード、次に右部分木を訪れると、キーが昇順で得られます。これは BST の不変条件から直接導かれます。よくある誤解は、単純な二分木にも同じことを期待することです。順序の規則がなければ、中間順巡回は意味のある並びを生みません。
関連リソース
その他の可視化
