AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构奇妙旅程之二叉平衡树进阶---AVL树

2024-04-29 31
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构奇妙旅程之二叉平衡树进阶---AVL树

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱

ʕ̯•͡˔•̯᷅ʔ大家好，我是xiaoxie.希望你看完之后,有不足之处请多多谅解，让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客

本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶

个人主页：xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客

系列专栏：xiaoxie的JAVA系列专栏——CSDN博客●'ᴗ'σσணღ*

我的目标:"团团等我💪( ◡̀_◡́ ҂)"

( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞👍 + 收藏⭐️ + 留言📝+关注（互三必回）!

一.AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺 序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种 解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。 一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

1.它的左右子树都是AVL树

2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

这里我们规定节点的左孩子的平衡因子为--,右孩子为++;

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 ，搜索时间复杂 度O(logN)。

二.AVL树节点的定义

public class AVLTree {
 public static class TreeNode {
     public int val; 
     public TreeNode left;
     public TreeNode right;
     public int bf;// 当前节点的平衡因子=右子树高度-左子树的高度
     public TreeNode parent;
     public TreeNode(int val) {
         this.val = val;
     }
 }
 public TreeNode root;

当前节点的平衡因子=右子树高度-左子树的高度。但是，不是每棵树，都必须有平衡因子，这只是其中的一种实现方式,并且这只是一种表示方式。

三.AVL树节点的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可 以分为两步：

1.按照二叉搜索树的方式插入新节点

 TreeNode node = new TreeNode(val);
     if(root == null) {
         root = node;
         root.parent = null;
     }
     TreeNode parent = null;
     TreeNode cur = root;
     while (cur != null) {
         if(node.val < cur.val) {
             parent = cur;
             cur = cur.left;
         } else if (node.val > cur.val) {
             parent = cur;
             cur = cur.right;
         }else {
             System.out.println("节点值 " + val + " 已经存在于树中，不进行插入操作");
             return false;
         }
     }
     //cur == null
      //找到node是parent的左孩子还是右孩子
      if(node.val < parent.val) {
          parent.left = node;
      }else {
          parent.right = node;
      }
      node.parent = parent;
      cur = node;

2.调整节点的平衡因子

新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树 的平衡性.

此时cur节点插入,parent节点的平衡因子就需要调整, 有以下两种情况

1.Cur插入到Parent的左侧，只需给Parent的平衡因子-1即可

2. 如果Cur插入到Parent的右侧，只需给Parent的平衡因子+1即可

此时：Parent的平衡因子可能有三种情况：0，正负1， 正负2

1.如果parent的平衡因子为0,那么就说明在插入前parent的平衡因子为正负1,插入后被调整成0，此时满足 AVL树的性质，插入成功

2.如果Parent的平衡因子为正负1，说明插入前Parent的平衡因子一定为0，插入后被更新成正负1，此 时以Parent为根的子树的高度增加，需要继续向上更新

3.如果Parent的平衡因子为正负2，则Parent的平衡因子违反平衡树的性质，需要对其进行旋转处理

  while (parent != null) {
          //计算节点的平衡因子
          //如果是左孩子就--
          //右孩子就++;
          if(cur == parent.left) {
              parent.bf--;
          }else {
              parent.bf++;
          }
          //根据不同的平衡因子有不同的情况
          //1.如果平衡因子为0
          if(parent.bf == 0) {
              break;
          } else if (parent.bf == 1 || parent.bf == -1) {
              cur = parent;
              parent = cur.parent;
          }else {
              if(parent.bf == 2) { //就代表右树高,需要调整右树的高度,就是左单旋,或者右左双旋
                  if(cur.bf == 1) {
                      rotateLeft(parent);
                  }else {
                      rotateRL(parent);//cur.bf = -1
                  }
              }else {//parent.bf == -2//就代表左树高,需要调整左树的高度,就是左单旋,或者左右双旋
                  if(cur.bf == 1) {
                      rotateLR(parent);
                  }else {//cur.bf == -1
                      rotateRight(parent);
                  }
              }
          }

四.AVL树的旋转(重点)

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据 节点插入位置的不同，AVL树的旋转分为四种：

1.新节点插入较高左子树的左侧---右单旋

上图在插入前，AVL树是平衡的，新节点插入到20的左子树(注意：此处不是左孩子)中，20左子树增加 了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层， 即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值 一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下 几种情况需要考虑： 1. 30节点的右孩子可能存在，也可能不存在 2. 60可能是根节点，也可能是子树 如果是根节点，旋转完成后，要更新根节点 如果是子树，可能是某个节点的左子树，也可能是右子树 

 /**
   * 右单旋左树高的话需要调整左树的高度
   * @author xiaoxie
   * @date 2024/3/6 15:01
   * @param parent
   */
  private void rotateRight(TreeNode parent) {
      TreeNode subL = parent.left;
      TreeNode subLR = subL.right;
      subL.right = parent;
      parent.left = subLR;
      if(subLR != null) {
          subLR.parent = parent;
      }
      TreeNode Pparent = parent.parent;
      parent.parent = subL;
      if(parent == root) {
          root = subL;
          root.parent = null;
      }else {
           if(Pparent.left == parent) {
              Pparent.left = subL;
          }else {
              Pparent.right = subL;
          }
          subL.parent = Pparent;
      }
      parent.bf = 0;
      subL.bf = 0;
  }

2. 新节点插入较高右子树的右侧---左单旋

 

上图在插入前，AVL树是平衡的,新的节点80,插入到70的右子树,70右子树增加 了一层，导致以30为根的二叉树不平衡,要让30平衡，只能将30右子树的高度减少一层，左子树增加一层， 即将右子树往上提，这样30转下来，因为30比60小，只能将其放在60的左子树，而如果60有左子树，左子树根的值 一定大于30，小于60，只能将其放在30的右子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下 几种情况需要考虑： 1. 60节点的右孩子可能存在，也可能不存在 2. 30可能是根节点，也可能是子树 如果是根节点，旋转完成后，要更新根节点 如果是子树，可能是某个节点的左子树，也可能是右子树 

/** 左单旋
   * 左旋,右树高的情况,需要调整右树的高度
   * @author xiaoxie
   * @date 2024/3/6 14:14
   * @param parent
   */
  private void rotateLeft(TreeNode parent) {
      TreeNode subR = parent.right;
      TreeNode subRL = subR.left;
      subR.left = parent;
      parent.right = subRL;
      if(subRL != null) {
          subRL.parent = parent;
      }
      //先记录parent节点的父亲节点
      TreeNode Pparent = parent.parent;
      parent.parent = subR;
      if(parent == root) {
          root = subR;
          subR.parent = null;
      }else {
          if(Pparent.left == parent) {
              Pparent.left = subR;
          }else {
              Pparent.right = subR;
          }
          subR.parent = Pparent;
      }
      parent.bf = 0;
      subR.bf = 0;
  }

3.新节点插入较高左子树的右侧：先左单旋再右单旋【左右双旋】

当一个节点的左子树比右子树高度高2个以上时，且这个节点的左子节点的右子树高于左子树时，需要进行左右双旋

1.情况一 subLR的平衡因子为1

在上图插入前,AVL树是平衡的,但在插入节点50后,插入到40的右子树上时,40的左子树的高度就增加一层了,以60为根的子树就不平衡了,这个时候我们就需要增加60的右子树的高度,降低左子树的高度,我们就需要用到右单旋,但60节点的左子节点的右子树高于左子树时,我们仅仅通过简单的右单旋并不能使这棵树变成高度平衡的二叉搜索树,我们就需要先进行左单旋,使这个节点的左节点的左子树和右子树的平衡后再进行右单旋,可以从上图看出,在进行左单旋后这颗树的情况和情况1一样,只是在最后需要我们调整 subL,parent,subLR的平衡因子即可

2.情况二subLR的平衡因子为-1

情况二和情况一的旋转过程大致一样,只不对 subL,parent,subLR的平衡因子的调整不同

/**
   * 左右双旋
   * @author xiaoxie
   * @date 2024/3/6 16:04
   * @param parent
   */
  private void rotateLR(TreeNode parent) {
      TreeNode subL = parent.left;
      TreeNode subLR = subL.right;
      int bf = subLR.bf;
      rotateLeft(parent.left);//左旋
      rotateRight(parent);//右旋
      if(bf == 1) {
          subLR.bf = 0;
          subL.bf = -1;
          parent.bf = 0;
      }else if(bf == -1) {
          subLR.bf = 0;
          subL.bf = 0;
          parent.bf = 1;
      }
  }

4.新节点插入较高右子树的左侧---右左：先右单旋再左单旋【右左双旋】

当一个节点的右子树比左子树高度高2个以上时，且这个节点的右子节点的左子树高于右子树时，需要进行右左双旋

1.情况一 subRL的平衡因子为1

在上图插入前,AVL树是平衡的,但在插入节点75后,插入到70的右子树上时,70的右子树的高度就增加一层了,以60为根的子树就不平衡了,这个时候我们就需要增加60的左子树的高度,降低右子树的高度,我们就需要用到左单旋,但60节点的右子节点的左子树高于右子树时,我们仅仅通过简单的左单旋并不能使这棵树变成高度平衡的二叉搜索树,我们就需要先进行右单旋,使这个节点的右节点的右子树和左子树的平衡后再进行左旋,可以从上图看出,在进行右单旋后这颗树的情况和情况2一样,只是在最后需要我们调整 subR,parent,subRL的平衡因子即可

2.情况二subRL的平衡因子为-1

况二和情况一的旋转过程大致一样,只不对 subR,parent,subRL的平衡因子的调整不同

/**
   * 右左双旋
   * @author xiaoxie
   * @date 2024/3/6 16:19
   * @param parent
   */
  private void rotateRL(TreeNode parent) {
      TreeNode subR = parent.right;
      TreeNode subRL = subR.left;
      int bf = subRL.bf;
      rotateRight(parent.right);
      rotateLeft(parent);
      if(bf == -1) {
          parent.bf = 0;
          subR.bf = 1;
          subRL.bf = 0;
      }else if(bf == 1) {
          parent.bf = -1;
          subRL.bf = 0;
          subR.bf = 0;
      }
  }

5.旋转的总结

新节点插入后，假设以Parent为根的子树不平衡，即Parent的平衡因子为2或者-2，分以下情况考虑

1. Parent的平衡因子为2，说明Parent的右子树高，设Parent的右子树的根为SubR 当SubR的平衡因子为1时，执行左单旋 当SubR的平衡因子为-1时，执行右左双旋

2. Parent的平衡因子为-2，说明Parent的左子树高，设Parent的左子树的根为SubL 当SubL的平衡因子为-1是，执行右单旋 当SubL的平衡因子为1时，执行左右双旋

即：Parent与其较高子树节点的平衡因子时同号时单旋转，异号时双旋转。

旋转完成后，原Parent为根的子树个高度降低，已经平衡，不需要再向上更新

五.总的代码实现及总结

1.Java代码实现

public class AVLTree {
 public static class TreeNode {
     public int val;
     public TreeNode left;
     public TreeNode right;
     public int bf;
     public TreeNode parent;
     public TreeNode(int val) {
         this.val = val;
     }
 }
 public TreeNode root;
 /**
  * 插入节点,并调整平衡因子
  * 使用旋转的方法调整平衡因子
  * @author xiaoxie
  * @date 2024/3/6 13:13
  * @param val
  * @return boolean
  */
  public boolean insertNode(int val) {
      TreeNode node = new TreeNode(val);
     if(root == null) {
         root = node;
         root.parent = null;
     }
     TreeNode parent = null;
     TreeNode cur = root;
     while (cur != null) {
         if(node.val < cur.val) {
             parent = cur;
             cur = cur.left;
         } else if (node.val > cur.val) {
             parent = cur;
             cur = cur.right;
         }else {
             System.out.println("节点值 " + val + " 已经存在于树中，不进行插入操作");
             return false;
         }
     }
     //cur == null
      //找到node是parent的左孩子还是右孩子
      if(node.val < parent.val) {
          parent.left = node;
      }else {
          parent.right = node;
      }
      node.parent = parent;
      cur = node;
      while (parent != null) {
          //计算节点的平衡因子
          //如果是左孩子就--
          //右孩子就++;
          if(cur == parent.left) {
              parent.bf--;
          }else {
              parent.bf++;
          }
          //根据不同的平衡因子有不同的情况
          //1.如果平衡因子为0
          if(parent.bf == 0) {
              break;
          } else if (parent.bf == 1 || parent.bf == -1) {
              cur = parent;
              parent = cur.parent;
          }else {
              if(parent.bf == 2) { //就代表右树高,需要调整右树的高度,就是左单旋,或者右左双旋
                  if(cur.bf == 1) {
                      rotateLeft(parent);
                  }else {
                      rotateRL(parent);//cur.bf = -1
                  }
              }else {//parent.bf == -2
                  if(cur.bf == 1) {
                      rotateLR(parent);
                  }else {//cur.bf == -1
                      rotateRight(parent);
                  }
              }
          }
      }
      return true;
  }
  /** 左单旋
   * 左旋,右树高的情况,需要调整右树的高度
   * @author xiaoxie
   * @date 2024/3/6 14:14
   * @param parent
   */
  private void rotateLeft(TreeNode parent) {
      TreeNode subR = parent.right;
      TreeNode subRL = subR.left;
      subR.left = parent;
      parent.right = subRL;
      if(subRL != null) {
          subRL.parent = parent;
      }
      //先记录parent节点的父亲节点
      TreeNode Pparent = parent.parent;
      parent.parent = subR;
      if(parent == root) {
          root = subR;
          subR.parent = null;
      }else {
          if(Pparent.left == parent) {
              Pparent.left = subR;
          }else {
              Pparent.right = subR;
          }
          subR.parent = Pparent;
      }
      parent.bf = 0;
      subR.bf = 0;
  }
  /**
   * 右单旋左树高的话需要调整左树的高度
   * @author xiaoxie
   * @date 2024/3/6 15:01
   * @param parent
   */
  private void rotateRight(TreeNode parent) {
      TreeNode subL = parent.left;
      TreeNode subLR = subL.right;
      subL.right = parent;
      parent.left = subLR;
      if(subLR != null) {
          subLR.parent = parent;
      }
      TreeNode Pparent = parent.parent;
      parent.parent = subL;
      if(parent == root) {
          root = subL;
          root.parent = null;
      }else {
           if(Pparent.left == parent) {
              Pparent.left = subL;
          }else {
              Pparent.right = subL;
          }
          subL.parent = Pparent;
      }
      parent.bf = 0;
      subL.bf = 0;
  }
  /**
   * 左右双旋
   * @author xiaoxie
   * @date 2024/3/6 16:04
   * @param parent
   */
  private void rotateLR(TreeNode parent) {
      TreeNode subL = parent.left;
      TreeNode subLR = subL.right;
      int bf = subLR.bf;
      rotateLeft(parent.left);
      rotateRight(parent);
      if(bf == 1) {
          subLR.bf = 0;
          subL.bf = -1;
          parent.bf = 0;
      }else if(bf == -1) {
          subL.bf = 0;
          parent.bf = 1;
          subLR.bf = 0;
      }
  }
  /**
   * 右左双旋
   * @author xiaoxie
   * @date 2024/3/6 16:19
   * @param parent
   */
  private void rotateRL(TreeNode parent) {
      TreeNode subR = parent.right;
      TreeNode subRL = subR.left;
      int bf = subRL.bf;
      rotateRight(parent.right);
      rotateLeft(parent);
      if(bf == -1) {
          parent.bf = 0;
          subR.bf = 1;
          subRL.bf = 0;
      }else if(bf == 1) {
          parent.bf = -1;
          subRL.bf = 0;
          subR.bf = 0;
      }
  }
    private int height(TreeNode root) {
        if(root == null) return 0;
        int leftH = height(root.left);
        int rightH = height(root.right);
 
        return leftH > rightH ? leftH+1 : rightH+1;
    }
    /**
     * 验证是否正确AVLTree
     * @author xiaoxie
     * @date 2024/3/6 16:49
     * @param root
     * @return boolean
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int leftH = height(root.left);
        int rightH = height(root.right);
 
        if(rightH-leftH != root.bf) {
            System.out.println("这个节点："+root.val+" 平衡因子异常");
            return false;
        }
 
        return Math.abs(leftH-rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
}

2.AVL树总结

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 logN。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要 维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改就不太适合。

以上就是博主关于AVL树的全部总结了,希望能够对你有所帮助!

 

 


文章标签：
Java
关键词：
数据结构树
数据结构avl
数据结构avl树
数据结构进阶
数据结构旅程
小谢在努力
目录
相关文章
XIAZHI
|
1月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索（DFS）算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历，按预序（根、左、右）输出节点值。接着，通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表，展示了如何将树结构转换为线性结构。最后，讨论了此算法的优点，如实现简单和内存效率高，同时也指出了潜在的内存管理问题，并分析了算法的时间复杂度。
XIAZHI
51 0
龙大吉
|
24天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
45 5
ephemerals__
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
79 16
XIAZHI
|
1月前
|
算法
数据结构之文件系统模拟（树数据结构）
本文介绍了文件系统模拟及其核心概念，包括树状数据结构、节点结构、文件系统类和相关操作。通过构建虚拟环境，模拟文件的创建、删除、移动、搜索等操作，展示了文件系统的基本功能和性能。代码示例演示了这些操作的具体实现，包括文件和目录的创建、移动和删除。文章还讨论了该算法的优势和局限性，如灵活性高但节点移除效率低等问题。
XIAZHI
51 0
java冯坚持
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
31 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
2月前
|
存储 算法 数据管理
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
这篇文章通过需求分析、代码实现和测试验证，详细介绍了二叉排序树的创建、遍历和删除操作，以及二叉平衡树（AVL）的自平衡特性和单旋转操作，旨在提高树结构在数据管理中的效率和性能。
java冯坚持
52 0
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
Dylaniou
|
2月前
|
Java C++
【数据结构】探索红黑树的奥秘：自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理，介绍其五大原则，并通过图解和代码示例展示其内部机制。同时，对比红黑树与二叉查找树的性能差异，帮助读者更好地理解这两种数据结构的特点和应用场景。
Dylaniou
39 0
java冯坚持
|
2月前
|
编解码 算法 Java
数据结构与算法学习十九：赫夫曼树树（图文很详细）、赫夫曼编码、应用实践（数据压缩、数据解压）、这一章自我感觉看懂就好。。。
赫夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩和编码。
java冯坚持
52 0
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
188 9
那年春天
|
1月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
32 1