はじめに (対象読者・この記事でわかること)

この記事は、Javaでデータ構造を実装したい方、または2分探索木の削除処理がいまいち理解できていない方を対象にしています。
この記事を読むことで、2分探索木からノードを削除する際に起こり得る3つのケース（葉ノード、子を1つ持つノード、子を2つ持つノード）の違いと、それぞれに対応するJavaコードの実装方法が理解できます。
また、削除後も2分探索木の性質（左部分木 < 親 < 右部分木）が保たれるようにするためのポイントを、図解と共に解説します。

前提知識

  • Javaの基本的な文法（クラス・メソッド・再帰）
  • 2分探索木の基本的な仕組み（挿入・探索）
  • 再帰的な処理の考え方

2分探索木の削除が複雑な理由

2分探索木（Binary Search Tree, BST）では、単にノードを削除するだけでなく、削除後も「左部分木のすべての値が親より小さく、右部分木のすべての値が親より大きい」という性質を保つ必要があります。
削除対象のノードによって、処理が大きく異なるため、ケース別に考える必要があります。

ケース 削除対象の特徴 処理の概要
ケース1 葉ノード（子を持たない） 単純に削除するだけ
ケース2 子を1つだけ持つ 子を自分の位置に繋ぎ直す
ケース3 子を2つ持つ 右部分木の最小ノードで置換する

Javaで実装する3つの削除ケース

ここからは、実際にJavaで削除処理を実装していきます。
まず、ノードを表すNodeクラスと、木全体を操作するBinarySearchTreeクラスを定義します。

ステップ1：基本的なクラス構造

Java

public class BinarySearchTree {
    private Node root;

    private static class Node {
        int value;
        Node left, right;
        Node(int value) { this.value = value; }
    }

    // 公開メソッド
    public void delete(int key) {
        root = deleteRec(root, key);
    }

    // 再帰的な削除処理
    private Node deleteRec(Node node, int key) {
        if (node == null) return null;

        if (key < node.value) {
            node.left = deleteRec(node.left, key);
        } else if (key > node.value) {
            node.right = deleteRec(node.right, key);
        } else {
            // 削除対象を発見
            return handleDeletion(node);
        }
        return node;
    }

ステップ2：ケース別の削除処理

handleDeletionメソッドで、3つのケースに分岐させます。

Java

private Node handleDeletion(Node target) {
    // ケース1: 葉ノード
    if (target.left == null && target.right == null) {
        return null;
    }
    // ケース2: 子を1つ持つ
    if (target.left == null) return target.right;
    if (target.right == null) return target.left;

    // ケース3: 子を2つ持つ
    Node successor = findMin(target.right);  // 右部分木の最小ノード
    target.value = successor.value;        // 値を置換
    target.right = deleteRec(target.right, successor.value); // 重複を削除
    return target;
}

private Node findMin(Node node) {
    while (node.left != null) node = node.left;
    return node;
}

ハマった点：再帰戻り値のミス

最初の実装で、ケース3でtarget.right = deleteRec(...)とした後にreturn successor;としてしまい、木の構造が崩れてしまいました。
これにより、削除対象のノードが2重に登場する状態になってしまいました。

解決策：正しい戻り値

削除対象のノード自体を返すことで、親ノードからの参照が正しく保たれます。
つまり、return target;が正解です。

まとめ

本記事では、Javaによる2分探索木の削除処理を3つのケースに分けて実装しました。

  • 葉ノードは単純にnullを返す
  • 子を1つ持つノードは、その子を返す
  • 子を2つ持つノードは、右部分木の最小ノードで置換する

この記事を通して、2分探索木の性質を保ちながら削除する仕組みが理解できたはずです。
次回は、AVL木や赤黒木のような自己平衡二分探索木での削除処理について深掘りします。

参考資料