Comment implémenter l'algorithme d'arborescence AVL en utilisant Java

Comment utiliser Java pour implémenter l'algorithme de l'arbre AVL

Introduction :
L'arbre AVL est un arbre de recherche binaire auto-équilibré qui peut automatiquement s'équilibrer pendant les opérations d'insertion et de suppression pour garantir que la hauteur de l'arbre est toujours maintenue . dans un périmètre plus restreint. Dans cet article, nous apprendrons comment implémenter l'algorithme d'arborescence AVL à l'aide de Java et fournirons des exemples de code concrets.

1. Description de base et caractéristiques de l'arbre AVL :
L'arbre AVL a été proposé par G. M. Adelson-Velsky et Evgenii Landis en 1962. Dans l'arbre AVL, pour chaque nœud, son sous-arbre gauche et son sous-arbre droit La différence de hauteur ne peut pas dépasser 1. S'il dépasse 1, une opération de rotation est nécessaire pour l'équilibrage automatique. Par rapport aux arbres de recherche binaires ordinaires, les arbres AVL ont de meilleures performances de recherche, d'insertion et de suppression.

2. Implémentation de nœuds de l'arborescence AVL :
En Java, nous pouvons utiliser des classes de nœuds personnalisées pour implémenter des arborescences AVL. Chaque nœud contient une valeur et une référence aux sous-arbres gauche et droit, ainsi qu'une variable pour enregistrer la hauteur du nœud.

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

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

3. Calculer la hauteur du nœud :
Avant d'implémenter l'algorithme de l'arbre AVL, nous avons besoin d'une fonction pour calculer la hauteur du nœud. Cette fonction obtient la hauteur du nœud actuel en calculant récursivement la hauteur du sous-arbre gauche et du sous-arbre droit, puis en prenant la plus grande valeur des deux et en ajoutant 1.

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

4. Implémentez l'opération de rotation de l'arborescence AVL :
Lors de l'insertion et de la suppression d'opérations, l'arborescence AVL doit être pivotée pour maintenir l'équilibre de l'arborescence. Nous mettrons en œuvre des opérations à gauche et à droite.

1. Opération de rotation à gauche :
   La rotation à gauche consiste à promouvoir le sous-arbre droit du nœud actuel vers le nouveau nœud racine d'origine. Le nœud racine d'origine devient le sous-arbre gauche du nouveau nœud racine et le sous-arbre gauche du nouveau nœud racine d'origine. devient le sous-arbre droit du sous-arbre racine d'origine.

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. Opération de rotation à droite :
   La rotation à droite consiste à promouvoir le sous-arbre gauche du nœud actuel vers le nouveau nœud racine, le nœud racine d'origine devient le sous-arbre droit du nouveau nœud racine et le sous-arbre droit du nouveau nœud racine d'origine. Le nœud racine devient l'original Le sous-arbre gauche du nœud racine.

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. Mise en œuvre de l'opération d'insertion :
Lors de l'insertion d'un nouveau nœud, il est d'abord inséré selon les règles de l'arbre de recherche binaire, puis ajusté en fonction du facteur d'équilibre du nœud sur le chemin d'insertion. comprend les opérations de rotation et de mise à jour des nœuds.

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. Mise en œuvre de l'opération de suppression :
Lors de la suppression d'un nœud, il est d'abord supprimé selon les règles de l'arbre de recherche binaire, puis ajusté en fonction du facteur d'équilibre du nœud sur le chemin de suppression. opérations et mise à jour de la hauteur du nœud.

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. Exemple de test :
Afin de vérifier l'exactitude de l'algorithme d'arbre AVL que nous avons implémenté, nous pouvons utiliser l'exemple suivant pour tester :

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);
}

Résultats de sortie :
10 20 25 30 40 50

Résumé :
Cet article présente comment utiliser Java pour implémenter l'algorithme d'arborescence AVL, et des exemples de code spécifiques sont fournis. En implémentant des opérations d'insertion et de suppression, nous pouvons garantir que l'arborescence AVL est toujours équilibrée, ce qui entraîne de meilleures performances de recherche, d'insertion et de suppression. Je pense qu'en étudiant cet article, les lecteurs pourront mieux comprendre et appliquer l'algorithme de l'arborescence AVL.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!