JavaScriptで二分探索木（BST）から目的のノードを削除する方法

本記事では、JavaScriptで実装した二分探索木（Binary Search Tree：BST）から、指定した値を持つノードを削除する方法を解説します。

問題

まず、以下のコードを見てください。このコードは二分探索木のデータ構造を生成し、ノードを挿入する機能を提供します。

class Node{
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    };
};
class BinarySearchTree{
    constructor(){
        // 二分探索木のルート
        this.root = null;
    }
    insert(data){
        var newNode = new Node(data);
        if(this.root === null){
            this.root = newNode;
        }else{
            this.insertNode(this.root, newNode);
        };
    };
    insertNode(node, newNode){
        if(newNode.data < node.data){
            if(node.left === null){
                node.left = newNode;
            }else{
                this.insertNode(node.left, newNode);
            };
        } else {
            if(node.right === null){
                node.right = newNode;
            }else{
                this.insertNode(node.right,newNode);
            };
        };
    };
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);

このコードを実行すると、BSTは次のような構造になります。

5
/ \
3 6
/ \ \
2 4 7

ここで、任意のBSTのルートを第1引数に、数値を第2引数として受け取る deleteNode() 関数を新たに実装する必要があります。

第2引数で指定された値がツリー内に存在する場合は、その値を持つノードを削除します。存在しない場合は何も行いません。どちらの場合でも、関数は更新後のBSTのルートを返す必要があります。

実装例

コードは以下のようになります。

class Node{
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    };
};
class BinarySearchTree{
    constructor(){
        // 二分探索木のルート
        this.root = null;
    }
    insert(data){
        var newNode = new Node(data);
        if(this.root === null){
            this.root = newNode;
        }else{
            this.insertNode(this.root, newNode);
        };
    };
    insertNode(node, newNode){
        if(newNode.data < node.data){
            if(node.left === null){
                node.left = newNode;
            }else{
                this.insertNode(node.left, newNode);
            };
        } else {
            if(node.right === null){
                node.right = newNode;
            }else{
                this.insertNode(node.right,newNode);
            };
        };
    };
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);
const printTree = (node) => {
    if(node !== null) {
        printTree(node.left);
        console.log(node.data);
        printTree(node.right);
    };
};
const deleteNode = function(root, key) {
    if(!root){
        return null;
    };
    if(root.data > key){
        if(!root.left){
            return root;
        }else{
            root.left = deleteNode(root.left, key);
        };
    } else if(root.data < key){
        if(!root.right) return root;
        else root.right = deleteNode(root.right, key);
    } else {
        if(!root.left || !root.right){
            return root.left || root.right;
        } else {
            let nd = new Node();
            let right = root.right;
            nd.left = root.left;
            while(right.left){
                right = right.left;
            }
            nd.data = right.data;
            nd.right = deleteNode(root.right, right.data);
            return nd;
        }
    }
    return root;
};
console.log('ノードを削除する前');
printTree(BST.root);
console.log('データが4のノードを削除した後');
printTree(deleteNode(BST.root, 4));

コードの解説

対象となるノードが見つかったときに考慮すべきケースは、合計で3つあります。

• 葉ノードである（左にも右にも子がない）

• 左の子のみを持つ、または右の子のみを持つ

• 左右両方の子を持つ

1と2のケースは簡単です。nullを返すか、持っている子（左または右）をそのまま返すだけで対応できます。

一方、最後のケースでは、対象ノードを削除した後にどのノードがその位置を引き継ぐのかを考える必要があります。単純に左の子や右の子を持ち上げてくると、BSTの性質（左側の子孫は親より小さく、右側の子孫は親より大きい）が崩れてしまいます。そこで、「右部分木の中の最小値」か「左部分木の中の最大値」のどちらかを探してきて置き換える必要があります。今回の実装では、右部分木の最小値（中間順走査における次のノード、いわゆる後継ノード）を採用しています。

なお、このアルゴリズムの計算量は木の高さを h とすると O(h) となり、バランスの取れたBSTであれば O(log n) で効率的に動作します。

出力結果

コンソールには次のように出力されます。

ノードを削除する前
2
3
4
5
6
7
データが4のノードを削除した後
2
3
5
6
7