JavaScriptで二分探索木のノードを削除する方法

木構造（ツリー）からノードを削除する処理は、一見すると複雑に感じられます。ノードの削除では、次の3つの場合分けを考慮する必要があります。これらは後述する関数のコメントにも記載しています。これまでの実装と同様に、クラス本体にメソッドを作成し、再帰的に呼び出すためのヘルパー関数を用意する形で実装していきます。

クラスメソッド

deleteNode(key) {
    // ノードが正常に削除されると、参照が返されます。
    return !(deleteNodeHelper(this.root, key) === false);
}

ヘルパーメソッド

削除対象のノードの状態によって、以下の3つのケースに分かれます。

ケース1：葉（リーフ）ノードの場合

子を持たないノードは、親からの接続を切断するだけで削除できます。

    A
   / \
  B   C
 /   / \
D   E   F

※ F を削除する場合

    A
   / \
  B   C
 /   /
D   E

ケース2：子を1つだけ持つ場合

子が1つだけあるノードは、その子ノードを親ノードの位置に置き換えることで削除できます。

      A
     / \
    B   C
   /   / \
  D   E   F

※ B を削除する場合

      A
     / \
    D   C
       / \
      E   F

ケース3：両方の子を持つ場合

これは最も扱いが難しいケースです。この場合は、削除対象ノードの「後継者（successor）」または「先行者（predecessor）」を見つけ、そのノードと置き換えます。例えば後継者を採用する場合、それは対象より大きい要素のうち最小のもの、すなわち右部分木の最小要素となります。削除後の木は次のようになります。

        A
       / \
      B   C
     /   / \
    D   E   F
       /   / \
      G   H   I

※ C を削除する場合

        A
       / \
      B   H
     /   / \
    D   E   F
       /     \
      G       I

この削除を実現するには、後継者の親を特定してリンクを解除し、後継者の左・右参照を現在のノードの左・右に向け直す必要があります。ただし、より簡単な方法として、削除対象ノードのデータを後継者の値で上書きし、その後継者ノードだけを削除する方法もあります。

/**
 * ルートとキーを受け取り、キーを再帰的に検索します。
 * キーが見つかった場合、次の3つのケースが考えられます：
 *
 * 1. 葉ノード → 親との接続を切るだけでよい
 * 2. 子が1つ → 子ノードを親の位置に置き換える
 * 3. 子が2つ → 後継者（右部分木の最小値）で置き換える
 */
function deleteNodeHelper(root, key) {
    if (root === null) {
        // 空の木の場合は false を返す
        return false;
    }
    if (key < root.data) {
        root.left = deleteNodeHelper(root.left, key);
        return root;
    } else if (key > root.data) {
        root.right = deleteNodeHelper(root.right, key);
        return root;
    } else {
        // 子がない場合
        // ケース1 - 葉ノード
        if (root.left === null && root.right === null) {
            root = null;
            return root;
        }
        // 子が1つの場合
        if (root.left === null) return root.right;
        if (root.right === null) return root.left;

        // 子が2つあるため、後継者を探す必要がある
        let currNode = root.right;
        while (currNode.left !== null) {
            currNode = currNode.left;
        }
        root.data = currNode.data;
        // 右部分木からその値を削除する
        root.right = deleteNodeHelper(root.right, currNode.data);
        return root;
    }
}

実行例

実際の動作は、次のコードで確認できます。

let BST = new BinarySearchTree();

BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);

BST.inOrder();

BST.deleteNode(15);
BST.deleteNode(10);
BST.deleteNode(3);

BST.inOrder();

出力結果

このコードを実行すると、次のような出力が得られます。

5
7
12
50

このように、削除後も二分探索木の性質（左の子 < 親 < 右の子）が保たれていることが、昇順に出力される結果から確認できます。