Explication détaillée de l'arborescence AVL de la structure de données Java

Cet article vous apporte des connaissances pertinentes sur java, qui présente principalement les connaissances pertinentes sur les arbres binaires équilibrés (arbres AVL) qui sont essentiellement des arbres de recherche binaires avec des fonctions équilibrées. Jetez-y un coup d'œil, espérons-le. aide tout le monde.

Étude recommandée : "Tutoriel vidéo Java"

Introduction de l'arbre AVL

La recherche d'arbres binaires a une efficacité de recherche extrêmement élevée, mais la recherche d'arbres binaires conduira aux situations extrêmes suivantes :

Un tel arbre binaire l'efficacité de la recherche est encore inférieure à celle des listes chaînées. L'arbre binaire équilibré (arbre AVL) qui apparaît sur la base de l'arbre binaire de recherche résout ce problème. Lorsque la valeur absolue de la différence de hauteur entre les sous-arbres gauche et droit d'un nœud dans un arbre binaire équilibré (arbre AVL) est supérieure à 1, leur différence de hauteur sera réduite grâce à une opération de rotation.

Concept de base

L'arbre AVL est essentiellement un arbre de recherche binaire. Ses caractéristiques sont :

1. Il est lui-même d'abord un arbre de recherche binaire.
二叉搜索树。
2. 每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
3. 当插入一个节点或者删除一个节点时，导致某一个节点的左右子树高度差的绝对值大于1，这时需要通过左旋和右旋的操作使二叉树再次达到平衡状态。

平衡因子(balanceFactor)

• 一个结点的左子树与右子树的高度之差。
• AVL树中的任意结点的BF只可能是-1，0和1。

基础设计

下面是AVL树需要的简单方法和属性：

public class AVLTree <e>>{
    class Node{
        E value;
        Node left;
        Node right;
        int height;
        public Node(){}
        public Node(E value){
            this.value = value;
            height = 1;
            left = null;
            right = null;
        }
        public void display(){
            System.out.print(this.value + " ");
        }
    }
    Node root;
    int size;
    public int size(){
        return size;
    }
    public int getHeight(Node node) {
        if(node == null) return 0;
        return node.height;
    }
    //获取平衡因子(左右子树的高度差，大小为1或者0是平衡的，大小大于1不平衡)
    public int getBalanceFactor(){
        return getBalanceFactor(root);
    }
    public int getBalanceFactor(Node node){
        if(node == null) return 0;
        return getHeight(node.left) - getHeight(node.right);
    }

    //判断一个树是否是一个平衡二叉树
    public boolean isBalance(Node node){
        if(node == null) return true;
        int balanceFactor = Math.abs(getBalanceFactor(node.left) - getBalanceFactor(node.right));
        if(balanceFactor > 1) return false;
        return isBalance(node.left) && isBalance(node.right);
    }
    public boolean isBalance(){
        return isBalance(root);
    }

    //中序遍历树
    private  void inPrevOrder(Node root){
        if(root == null) return;
        inPrevOrder(root.left);
        root.display();
        inPrevOrder(root.right);
    }
    public void inPrevOrder(){
        System.out.print("中序遍历：");
        inPrevOrder(root);
    }}</e>

RR(左旋)

往一个树右子树的右子树上插入一个节点，导致二叉树变得不在平衡，如下图，往平衡二叉树中插入5，导致这个树变得不再平衡，此时需要左旋操作，如下：

代码如下：

//左旋,并且返回新的根节点
    public Node leftRotate(Node node){
        System.out.println("leftRotate");
       Node cur = node.right;
       node.right = cur.left;
       cur.left = node;
       //跟新node和cur的高度
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
        return cur;
    }

LL(右旋)

往一个AVL树左子树的左子树上插入一个节点，导致二叉树变得不在平衡，如下图，往平衡二叉树中插入2，导致这个树变得不再平衡，此时需要左旋操作，如下：

代码如下：

 //右旋，并且返回新的根节点
    public Node rightRotate(Node node){
        System.out.println("rightRotate");
        Node cur = node.left;
        node.left = cur.right;
        cur.right = node;
        //跟新node和cur的高度
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
        return cur;
    }

LR(先左旋再右旋)

往AVL树左子树的右子树上插入一个节点，导致该树不再平衡，需要先对左子树进行左旋，再对整棵树右旋，如下图所示，插入节点为5.

RL(先右旋再左旋)

往AVL树右子树的左子树上插入一个节点，导致该树不再平衡，需要先对右子树进行右旋，再对整棵树左旋La valeur absolue (facteur d'équilibre) de la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud est d'au plus 1. En d'autres termes, l'arbre AVL est essentiellement un arbre de recherche binaire (arbre de tri binaire, arbre de recherche binaire) avec fonction d'équilibre.
Lors de l'insertion d'un nœud ou de la suppression d'un nœud, la valeur absolue de la différence de hauteur entre les sous-arbres gauche et droit d'un nœud est supérieure à 1. Dans ce cas, rotation gauche et rotation à droite permet à l'arbre binaire de retrouver un état d'équilibre. Facteur d'équilibre (balanceFactor)

La différence de hauteur entre le sous-arbre gauche et le sous-arbre droit d'un nœud.

Le BF de n'importe quel nœud de l'arborescence AVL ne peut être que -1, 0 et 1.

Conception de base

Voici les méthodes et attributs simples requis par l'arborescence AVL :

//添加元素
    public  void add(E e){
        root = add(root,e);
    }
    public Node add(Node node, E value) {
        if (node == null) {
            size++;
            return new Node(value);
        }
        if (value.compareTo(node.value) > 0) {
            node.right = add(node.right, value);
        } else if (value.compareTo(node.value)  1 && getBalanceFactor(node.left) >= 0) {
            return rightRotate(node);
        }
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上，此时需要进行左旋
        else if (balanceFactor  1 && getBalanceFactor(node.left)  0
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树的左子树上，此时需要先对右子树右旋，再整个树左旋
        else if(balanceFactor  0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

RR (rotation à gauche)

🎜Insérez un arbre dans le sous-arbre droit de l'arbre AVL. nœud de sous-arbre droit, provoquant un déséquilibre de l'arbre binaire. Comme le montre la figure ci-dessous, l'insertion de 5 dans l'arbre binaire équilibré provoque le déséquilibre de l'arbre. À ce stade, une opération de virage à gauche est nécessaire, comme suit : 🎜<. img src="https://img.php.%20cn/upload/article/000/000/067/5ed8f74b95398ff7e44e93a97b5ca6d7-1.png" alt="Insérer la description de l'image ici">🎜 Le code est le suivant : 🎜

 //删除节点
    public E remove(E value){
        root = remove(root,value);
        if(root == null){
            return null;
        }
        return root.value;
    }
    public Node remove(Node node, E value){
        Node retNode = null;
        if(node == null)
            return retNode;
        if(value.compareTo(node.value) > 0){
            node.right = remove(node.right,value);
            retNode = node;
        }
        else if(value.compareTo(node.value)  1 && getBalanceFactor(retNode.left) >= 0) {
            return rightRotate(retNode);
        }
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上，此时需要进行左旋
        else if (balanceFactor  1 && getBalanceFactor(retNode.left)  0) {
            retNode.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return  retNode;
    }

🎜 LL (rotation à droite)🎜🎜Vers le sous-arbre gauche d'un arbre AVL L'insertion d'un nœud dans le sous-arbre gauche provoque le déséquilibre de l'arbre binaire, comme le montre la figure ci-dessous. L'insertion de 2 dans l'arbre binaire équilibré entraîne le déséquilibre de l'arbre. . À ce stade, une opération de virage à gauche est requise, comme suit : 🎜🎜 Le code est le suivant : 🎜rrreee🎜LR (tournez d'abord à gauche puis à droite)🎜🎜Insérez un nœud dans le sous-arbre droit du sous-arbre gauche de l'arborescence AVL, provoquant un déséquilibre de l'arbre. Vous devez d'abord faire pivoter le sous-arbre gauche vers la gauche, puis L'arbre entier pivote vers la droite, comme le montre la figure ci-dessous. le nœud inséré est 5.🎜🎜🎜RL (d'abord tourner à droite puis tourner à gauche)🎜🎜Insérez un nœud dans le sous-arbre gauche du sous-arbre droit de l'arborescence AVL, par conséquent, l'arbre n'est plus équilibré. Vous devez d'abord effectuer un. rotation à droite sur le sous-arbre droit, puis effectuez une rotation à gauche sur l'arbre entier Comme le montre la figure ci-dessous, le nœud inséré est 2.🎜🎜 🎜🎜Ajouter. node🎜rrreee🎜Supprimer le nœud🎜rrreee🎜Apprentissage recommandé : "🎜Tutoriel vidéo Java🎜"🎜

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!