二分木 (Binary Tree) を Java で自作する — BST / 走査 / バランス崩れの実例

なぜ二分木を学ぶのか

Java には TreeMap / TreeSet (内部は Red-Black Tree) が既にあり、 「業務で BST を自作する」機会はほぼありません。 それでも二分木を自分で書けると、以下の面で現場に効きます。

• DB インデックス (B+Tree) の挙動が腑に落ちる — 計算量が速くなる仕組みと、「偏る」 と遅くなる理由- 再帰で動くデータ構造の読み書きが身につく — 式木、AST、ファイルツリー、DOM すべて同種- 「バランスが崩れる」 という現実の問題を体感 できる — 単純な BST は最悪 O(n) で、本番で致命的になる 本稿では、Generics で 二分探索木 (BST) を実装し、 3 種類の走査と、バランス崩壊の問題・対策 (AVL / Red-Black) までを扱います。

用語整理

• 二分木 (Binary Tree): 各ノードが子を最大 2 個持つ木- 二分探索木 (Binary Search Tree, BST): さらに「左の子 < 自分 < 右の子」の順序性を持つ二分木。 この順序性があるおかげで探索が O(log n) になる (バランスがとれていれば)- 走査 (Traversal): 全ノードを順番に訪問する方法。前順・中順・後順の 3 種一般に単に「二分木」と呼ぶと BST を指すことが多いので、本稿も BST を実装します。## 計算量サマリ| 操作 | バランス取れた BST | 偏った BST (最悪ケース) | | --- | --- | --- | | 探索 | O(log n) | O(n) | | 挿入 | O(log n) | O(n) | | 削除 | O(log n) | O(n) |

「ソート済みデータを順に insert する」と、BST は単なる連結リストに退化してしまい最悪 O(n) になります。 これを避けるのが AVL / Red-Black のような 「自動バランス木」 です。

Node の設計

final class Node<T extends Comparable<T>> {
    T value;
    Node<T> left;
    Node<T> right;

    Node(T value) {
        this.value = value;
    }
}

要素は Comparable を要求し、BST の順序性を型で担保します。 もし任意型を扱いたいなら Comparator<T> を外から注入する設計にします (TreeMap が実際その設計)。

BST の実装

骨格

public final class BinarySearchTree<T extends Comparable<T>> {
    private Node<T> root;
    private int size = 0;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return root == null;
    }
}

挿入: O(log n) (バランス取れていれば)

public void insert(T value) {
    root = insert(root, value);
}

private Node<T> insert(Node<T> node, T value) {
    if (node == null) {
        size++;
        return new Node<>(value);
    }
    int cmp = value.compareTo(node.value);
    if (cmp < 0) {
        node.left = insert(node.left, value);
    } else if (cmp > 0) {
        node.right = insert(node.right, value);
    } // 等しければ重複挿入しない方針
    return node;
}

再帰で root = insert(root, value) と書くイディオム。 「ノードを書き換えた結果」 を上に戻していく発想で書くと、親の参照を気にせず書けます。

探索: O(log n)

public boolean contains(T value) {
    return find(root, value) != null;
}

private Node<T> find(Node<T> node, T value) {
    if (node == null) return null;
    int cmp = value.compareTo(node.value);
    if (cmp == 0) return node;
    return cmp < 0 ? find(node.left, value) : find(node.right, value);
}

削除: 3 ケースを場合分け

削除は BST で最も難しい操作。削除対象ノードの子の数で 3 ケースに分かれます。

1. 子が無い: そのまま除去
2. 子が 1 つ: その子で置き換え
3. 子が 2 つ: 後継ノード (右部分木の最小値) で置き換え

public boolean remove(T value) {
    int before = size;
    root = remove(root, value);
    return size < before;
}

private Node<T> remove(Node<T> node, T value) {
    if (node == null) return null;
    int cmp = value.compareTo(node.value);
    if (cmp < 0) {
        node.left = remove(node.left, value);
    } else if (cmp > 0) {
        node.right = remove(node.right, value);
    } else {
        // ケース 1 & 2: 子が 0 or 1
        if (node.left == null) {
            size--;
            return node.right;
        }
        if (node.right == null) {
            size--;
            return node.left;
        }
        // ケース 3: 右部分木の最小値を昇格
        Node<T> successor = min(node.right);
        node.value = successor.value;
        node.right = remove(node.right, successor.value);
    }
    return node;
}

private Node<T> min(Node<T> node) {
    while (node.left != null) node = node.left;
    return node;
}

走査: 前順・中順・後順

中順 (In-order) は BST の全要素をソート順で返す基本操作。 その特徴から BST の最大の実用的価値は 「常にソート済みで保てる」 と言えます。

public List<T> inOrder() {
    List<T> result = new ArrayList<>(size);
    inOrder(root, result);
    return result;
}

private void inOrder(Node<T> node, List<T> out) {
    if (node == null) return;
    inOrder(node.left, out);   // 左 → 自分 → 右
    out.add(node.value);
    inOrder(node.right, out);
}

/** 前順: 自分 → 左 → 右。木のコピーに使う */
private void preOrder(Node<T> node, List<T> out) {
    if (node == null) return;
    out.add(node.value);
    preOrder(node.left, out);
    preOrder(node.right, out);
}

/** 後順: 左 → 右 → 自分。木の削除に使う */
private void postOrder(Node<T> node, List<T> out) {
    if (node == null) return;
    postOrder(node.left, out);
    postOrder(node.right, out);
    out.add(node.value);
}

幅優先 (BFS) もキューで

深さ優先 (DFS) の 3 種類に加え、 階層単位で見たい場合は BFS を Queue で実装します。

public List<T> levelOrder() {
    List<T> result = new ArrayList<>(size);
    if (root == null) return result;
    Deque<Node<T>> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        Node<T> cur = queue.poll();
        result.add(cur.value);
        if (cur.left != null) queue.offer(cur.left);
        if (cur.right != null) queue.offer(cur.right);
    }
    return result;
}

使用例

public class Main {
    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        for (int v : new int[]{5, 3, 7, 1, 4, 6, 8}) {
            bst.insert(v);
        }
        System.out.println(bst.inOrder());  // [1, 3, 4, 5, 6, 7, 8]
        System.out.println(bst.contains(4)); // true
        bst.remove(3);
        System.out.println(bst.inOrder());  // [1, 4, 5, 6, 7, 8]
    }
}

バランス崩れという現実の罠

ソート済みデータを順に挿入すると:

insert 1, 2, 3, 4, 5
→ root=1
   └─ right=2
          └─ right=3
                 └─ right=4
                        └─ right=5

このとき contains(5) は O(n)。 単純な BST は入力次第で単なる連結リストに退化します。

この問題を解決する 「自動バランス木」 が以下です。

AVL 木

挿入/削除後に 各ノードの左右部分木の高さの差を 1 以内 に収めるため、 「回転 (rotation)」 で木を組み替える方式。厳格なバランスで探索は高速ですが、 挿入・削除時の回転コストがやや重い。

Red-Black Tree (TreeMap / TreeSet の中身)

各ノードに赤/黒の色を付け、以下の制約を保つ:

• 根は黒
• 赤ノードの子は黒 (赤が連続しない)
• 任意のノードから葉までの経路で黒ノード数が等しい

AVL より緩いバランス制約で、挿入/削除のコストが低め。 Java 標準の TreeMap/TreeSet/HashMap の衝突リスト長が閾値を超えたとき内部的に使われます。

実務ではまず TreeMap を使い、特別な理由がない限り BST の自作は避けましょう。

落とし穴

1. 再帰が深くなるとスタックオーバーフロー

木が極端に偏る (ソート済み大量挿入) と再帰呼び出しが n 回積まれて StackOverflowError。 数万件規模の BST を扱うなら、反復版 (スタックを自前で持つ) に書き直すか、 バランス木を使うのが安全。

2. Comparable の実装バグ

要素が自然順序を正しく実装していないと、挿入自体は通っても探索/削除で破綻します。 特に equals と compareTo の整合性 (a.compareTo(b) == 0 のとき a.equals(b) ) を忘れがち。

3. 削除時の 「後継ノード」 の取り違い

削除ケース 3 で 「右部分木の最小値」 ではなく 「左部分木の最大値」 を使ってもOKですが、 片方だけに統一しないと保守時に混乱します。コメントでどちらを採用しているか明記を。

4. マルチスレッド

ここで作った BST はスレッド安全ではありません。 並行アクセスがあるなら、ConcurrentSkipListMap (ロックフリーな BST 相当) か、 外側で synchronized ラップしてください。

---

まとめ: BST の自作は、計算量と再帰構造を体で覚えるトレーニングとして価値大。 一方、本番で BST そのものを使う機会はほぼなく、 TreeMap / TreeSet が内部で何をしているか理解する のが実務上のゴール。 「バランスが崩れると全てが遅くなる」 という事実は、 DB インデックス設計やキャッシュ構造を考えるときにも効いてきます。