Javaを使用してAVLツリーアルゴリズムを実装する方法

Java を使用して AVL ツリー アルゴリズムを実装する方法

はじめに:
AVL ツリーは、挿入と削除を実行できる自己平衡型二分探索ツリーです。運転中に自動バランス調整を実行し、木の高さが常に小さな範囲内に保たれるようにします。この記事では、Java を使用して AVL ツリー アルゴリズムを実装する方法を学び、具体的なコード例を示します。

1. AVL ツリーの基本的な説明と特徴:
AVL ツリーは、1962 年に G. M. Adelson-Velsky と Evgenii Landis によって提案されました。ツリーと右側のサブツリーは 1 を超えることはできません。1 を超える場合は、自動バランスをとるために回転操作が必要になります。通常の二分探索ツリーと比較して、AVL ツリーは検索、挿入、削除のパフォーマンスが優れています。

2. AVL ツリーのノード実装:
Java では、カスタム ノード クラスを使用して AVL ツリーを実装できます。各ノードには、値と左右のサブツリーへの参照、およびノー​​ドの高さを記録する変数が含まれています。

class AVLNode {
    int val;
    AVLNode left, right;
    int height;

    AVLNode(int val) {
        this.val = val;
        this.height = 1;
    }
}

3. ノードの高さを計算する:
AVL ツリー アルゴリズムを実装する前に、ノードの高さを計算する関数が必要です。この関数は、左のサブツリーと右のサブツリーの高さを再帰的に計算し、2 つの大きい方の値を取得して 1 を加算することにより、現在のノードの高さを取得します。

int getHeight(AVLNode node) {
    if (node == null) {
        return 0;
    }
    return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}

4. AVL ツリーの回転操作を実装します:
操作を挿入および削除するとき、ツリーのバランスを維持するために AVL ツリーを回転する必要があります。左手操作と右手操作の両方を実装します。

1. 左ローテーション操作:
   左ローテーションは、現在のノードの右サブツリーを新しいルート ノードにプロモートすることです。元のルート ノードは、新しいルート ノードの左サブツリーになります。元の新しいルート ノードのサブツリー サブツリーは、元のルート ノードの右側のサブツリーになります。

AVLNode leftRotate(AVLNode node) {
    AVLNode newRoot = node.right;
    AVLNode temp = newRoot.left;

    newRoot.left = node;
    node.right = temp;

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;

    return newRoot;
}

2. 右回転操作:
   右回転は、現在のノードの左のサブツリーを新しいルート ノードに昇格させることであり、元のルート ノードは新しいルート ノードの右のサブツリーになります。ルート ノード: 元の新しいルート ノードの右側のサブツリーが、元のルート ノードの左側のサブツリーになります。

AVLNode rightRotate(AVLNode node) {
    AVLNode newRoot = node.left;
    AVLNode temp = newRoot.right;

    newRoot.right = node;
    node.left = temp;

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;

    return newRoot;
}

5. 挿入操作の実装:
新しいノードを挿入するとき、最初に二分探索木の規則に従って挿入され、次に、二分探索木のバランス係数に従って調整されます。の調整には、回転操作とノードの高さの更新が含まれます。

AVLNode insert(AVLNode node, int val) {
    if (node == null) {
        return new AVLNode(val);
    }

    if (val < node.val) {
        node.left = insert(node.left, val);
    } else if (val > node.val) {
        node.right = insert(node.right, val);
    } else {
        // 如果节点已经存在，不进行插入
        return node;
    }

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    int balanceFactor = getBalanceFactor(node);

    // 左左情况，需要进行右旋
    if (balanceFactor > 1 && val < node.left.val) {
        return rightRotate(node);
    }

    // 左右情况，需要进行左旋后再进行右旋
    if (balanceFactor > 1 && val > node.left.val) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 右右情况，需要进行左旋
    if (balanceFactor < -1 && val > node.right.val) {
        return leftRotate(node);
    }

    // 右左情况，需要进行右旋后再进行左旋
    if (balanceFactor < -1 && val < node.right.val) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;
}

6. 削除操作の実装:
ノードを削除する場合、まず二分探索木のルールに従って削除され、次に削除時のノードのバランス係数に従って調整されます。パス。調整には回転が含まれます。ノードの高さを操作および更新します。

AVLNode delete(AVLNode node, int val) {
    if (node == null) {
        return node;
    }

    if (val < node.val) {
        node.left = delete(node.left, val);
    } else if (val > node.val) {
        node.right = delete(node.right, val);
    } else {
        if (node.left == null || node.right == null) {
            node = (node.left != null) ? node.left : node.right;
        } else {
            AVLNode successor = findMin(node.right);
            node.val = successor.val;
            node.right = delete(node.right, node.val);
        }
    }

    if (node == null) {
        return node;
    }

    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

    int balanceFactor = getBalanceFactor(node);

    // 左左情况，需要进行右旋
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
        return rightRotate(node);
    }

    // 左右情况，需要进行左旋后再进行右旋
    if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // 右右情况，需要进行左旋
    if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
        return leftRotate(node);
    }

    // 右左情况，需要进行右旋后再进行左旋
    if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    return node;
}

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

7. テスト例:
実装した AVL ツリー アルゴリズムの正しさを検証するために、次の例を使用してテストできます:

public static void main(String[] args) {
    AVLTree tree = new AVLTree();

    tree.root = tree.insert(tree.root, 10);
    tree.root = tree.insert(tree.root, 20);
    tree.root = tree.insert(tree.root, 30);
    tree.root = tree.insert(tree.root, 40);
    tree.root = tree.insert(tree.root, 50);
    tree.root = tree.insert(tree.root, 25);

    tree.inOrderTraversal(tree.root);
}

出力結果:
10 20 25 30 40 50

概要:
この記事では、Java を使用して AVL ツリー アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。挿入操作と削除操作を実装することで、AVL ツリーのバランスが常に保たれるようになり、検索、挿入、削除のパフォーマンスが向上します。この記事を学ぶことで、読者は AVL ツリー アルゴリズムをよりよく理解し、適用できるようになると思います。

以上がJavaを使用してAVLツリーアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。