JavaScriptでAVL木（AVLツリー）にノードを挿入する方法

AVL木へのノード挿入の基本

AVL木へのノード挿入は、通常の二分探索木（BST）とほぼ同じ手順で行います。ただし、AVL木では挿入処理の中で木を下っていくたびに、「バランス調整（balance）」という追加のステップを実行する必要があります。

バランス調整にはバランスファクター（平衡係数）の計算が必要です。これは以前の記事で解説した通り、左部分木と右部分木の高さの差から求められます。計算結果に応じて、適切な回転操作（LL回転・LR回転・RR回転・RL回転）を呼び出すことで、木の平衡状態を保ちます。どの回転を選択すべきかは、条件分岐の構成を見れば直感的に理解できるでしょう。

insertメソッドの実装

それでは、クラスメソッドとしてinsertを実装し、再帰呼び出しのためのヘルパー関数も併せて作成しましょう。

insert(data) {
    let node = new this.Node(data);
    // 木が空かどうかをチェック
    if (this.root === null) {
        // 最初の要素として挿入
        this.root = node;
    } else {
        insertHelper(this, this.root, node);
    }
}

ヘルパー関数

function insertHelper(self, root, node) {
    if (root === null) {
        root = node;
    } else if (node.data < root.data) {
        // 左へ進む！
        root.left = insertHelper(self, root.left, node);
        // バランスファクターを確認し、適切な回転を実行
        if (root.left !== null && self.getBalanceFactor(root) > 1) {
            if (node.data > root.left.data) {
                root = rotationLL(root);
            } else {
                root = rotationLR(root);
            }
        }
    } else if (node.data > root.data) {
        // 右へ進む！
        root.right = insertHelper(self, root.right, node);
        // バランスファクターを確認し、適切な回転を実行
        if (root.right !== null && self.getBalanceFactor(root) < -1) {
            if (node.data > root.right.data) {
                root = rotationRR(root);
            } else {
                root = rotationRL(root);
            }
        }
    }
    return root;
}

この実装のポイントは以下の通りです。

• 左側への挿入後：バランスファクターが1より大きくなった場合、挿入されたノードの位置に応じてLL回転またはLR回転を選択します。
• 右側への挿入後：バランスファクターが-1より小さくなった場合、RR回転またはRL回転を選択します。
• 各再帰呼び出しの戻り値を親ノードの子ポインタに代入することで、回転によって部分木の根が変わっても、木全体の構造が正しく維持されます。

動作確認

実際にコードを動かして、挿入処理を確認してみましょう。

let AVL = new AVLTree();

AVL.insert(10);
AVL.insert(15);
AVL.insert(5);
AVL.insert(50);
AVL.insert(3);
AVL.insert(7);
AVL.insert(12);

AVL.inOrder();

出力結果

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

3
5
7
10
12
15
50

中間順走査（in-order traversal）の結果が昇順に並んでいることから、すべてのノードが正しく挿入され、木全体の平衡が保たれていることが確認できます。