• AVL 树的初步认识与基本操作

    历史

    AVL 树是一种自平衡二叉搜索树，由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字：Adelson-Velsky 和 Landis，他们是苏联数学家，于 1962 年发表了一篇论文，详细介绍了 AVL 树的概念和性质。

    在二叉搜索树中，如果插入的元素按照特定的顺序排列，可能会导致树变得非常不平衡，从而降低搜索、插入和删除的效率。为了解决这个问题，AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2，则通过旋转操作来重新平衡树。

    AVL 树是用于存储有序数据的一种重要数据结构，它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率，而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展，AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。

    什么叫平衡二叉搜索树?什么叫不平衡二叉搜索树？

    个人理解：

    答：当根节点两边左右孩子都有则为平衡二叉搜索树，如果有一边没有孩子就是不平衡，就像一个人如果缺胳膊少腿肯定就会看起来不平衡。

    温馨提示：对于二叉树还是不太认识的，作者推荐：二叉搜索树的初步认识_加瓦不加班的博客-CSDN博客

    前面介绍过，如果一棵二叉搜索树长的不平衡，那么查询的效率会受到影响，如下图

    比如，我们如果要从上述二叉树，根节点是3，它虽然有左孩子，你有没有发现它右孩子没有，那岂不就是缺胳膊少腿？所以这个就是不平衡二叉搜索树，

    那么为什么一棵二叉搜索树长的不平衡会查询的效率会受到影响？

    答：比如，你现在要搜索节点为1的情况，你要从根节点开始，从根往左，也就是搜索到最低层节点才能找到，也就是要走2步，如果，此时我将2做为根节点，那么从2开始查询，只需要一步到位查询到1.是不是相对平衡的二叉树搜索起来更加高效？

    通过旋转可以让树重新变得平衡，并且不会改变二叉搜索树的性质（即左边仍然小，右边仍然大）

    什么叫自平衡二叉搜索树？

    就是当二叉树出现不平衡时，我们二叉树能够检测不平衡，通过“旋转”，也就是自动将根节点调换，换成能够变成平衡二叉树的情况。

    /**

    • ​

      AVL 树

    • 二叉搜索树在插入和删除时，节点可能失衡

    • 如果在插入和删除时通过旋转, 始终让二叉搜索树保持平衡, 称为自平衡的二叉搜索树

    • AVL 是自平衡二叉搜索树的实现之一

    */

如何判断失衡？

如果一个节点的左右孩子，高度差超过 1，则此节点失衡，才需要旋转

处理高度

如何得到节点高度？一种方式之前做过的一道题目：E05. 求二叉树的最大深度（高度）二叉树--二叉树最大深度_加瓦不加班的博客-CSDN博客，但由于求高度是一个非常频繁的操作，因此将高度作为节点的一个属性，将来新增或删除时及时更新，默认为 1（按力扣说法）

  1. static class AVLNode {
  2.     int height = 1;
  3.     int key;
  4.     Object value;
  5.     AVLNode left;
  6.     AVLNode right;
  7.     // ...
  8. }

求高度代码：

这里加入了 height 函数方便求节点为 null 时的高度

  1. private int height(AVLNode node) {
  2.     return node == null ? 0 : node.height;
  3. }

更新高度代码

将来新增、删除、旋转时，高度都可能发生变化，需要更新。下面是更新高度的代码

在这里我们之前其实已经学习了如何获取节点的高度----二叉树最大深度-力扣104二叉树--二叉树最大深度_加瓦不加班的博客-CSDN博客

  1. /*
  2.    思路：
  3.    1. 得到左子树深度, 得到右子树深度, 二者最大者加一, 就是本节点深度
  4.    2. 因为需要先得到左右子树深度, 很显然是后序遍历典型应用
  5.    3. 关于深度的定义：从根出发, 离根最远的节点的总边数,这个总边数指的就是下面的线段数
  6.        注意: 力扣里的深度定义要多一,在你现在看来下面的深度确实是1 2 0  但是力扣官方觉得：在你看来的基础上+1才是正确的深度
  8.  你的视角：      深度:1         深度:2         深度:0
  9.  力扣的视角：      深度:2         深度:3         深度:1
  10.                    1            1            1
  11.                   / \          / \
  12.                  2   3        2   3
  13.                                    \
  14.                                     4
  15. */
  16.    public int maxDepth(TreeNode node) {
  17.        if (node == null) {
  18.            return 0; // 非力扣题目改为返回 -1
  19.        }
  20.        int d1 = maxDepth(node.left);
  21.        int d2 = maxDepth(node.right);
  22.        return Integer.max(d1, d2) + 1;
  23.    }

举例说明：

当二叉树只有根节点时，高度是1：

当二叉树有根节点跟一边的子节点时，根节点高度是2 子节点是1：（实际上是想告诉你的是，任何一个节点在新增以后的高度都是要变化的）：

但是有一种情况是不会变化的，那就是当在同一层加节点，高度不变：

  1. private void updateHeight(AVLNode node) {
  2.     node.height = Integer.max(height(node.left), height(node.right)) + 1;
  3. }

何时触发失衡判断？

定义平衡因子（balance factor）如下

当平衡因子

  • bf = 0，1，-1 时，表示左右平衡

为什么会有0，1，-1的情况？

举例说明：

对于0这个情况：

对于4节点为参考，它的左右孩子高度相减就是0

对于1这个情况：

对于4根节点为参考，它的左孩子高度为2，右孩子高度为1，而我们相减的顺序是（左-右） ，相减就是1

对于-1这个情况：

对于2根节点为参考，它的左孩子高度为1，右孩子高度为2，而我们相减的顺序是（左-右） ，相减就是-1

  • bf > 1 时，表示左边太高

  • bf < -1 时，表示右边太高

对应代码

  1. private int bf(AVLNode node) {
  2.     return height(node.left) - height(node.right);
  3. }

当插入新节点，或删除节点时，引起高度变化时，例如

目前此树平衡，当再插入一个 4 时，节点们的高度都产生了相应的变化，8 节点失衡了

在比如说，下面这棵树一开始也是平衡的

当删除节点 8 时，节点们的高度都产生了相应的变化，6 节点失衡了

失衡的四种情况

LL

  • 失衡节点（图中 8 红色）的 bf > 1，即左边更高

  • 失衡节点的左孩子（图中 6）的 bf >= 0 ，即图中 6的左孩子这边也是左边更高或等高

LR

  • 失衡节点（图中 8）的 bf > 1，即左边更高

  • 失衡节点的左孩子（图中 3 红色）的 bf < 0 ，即左孩子（图中 3 红色）这边是右边孩子更高

对称的还有两种情况

接下来的两个情况和上面两种情况是对称的：

RL

  • 失衡节点（图中 3）的 bf <-1，即右边更高

  • 失衡节点的右孩子（图中 6 红色）的 bf > 0，即右孩子（图中 6 红色）这边左边更高

RR

  • 失衡节点（图中 3）的 bf <-1，即右边更高

  • 失衡节点的右孩子（图中 5 红色）的 bf <= 0，即右孩子（图中 5 红色）这边右边更高或等高

解决失衡

失衡可以通过树的旋转解决。什么是树的旋转呢？它是在不干扰元素顺序的情况下更改结构，通常用来让树的高度变得平衡。

观察下面一棵二叉搜索树，可以看到，旋转后，并未改变树的左小右大特性，但根、父、孩子节点都发生了变化

      4                                          2
     / \             4 right                  / \
    2   5      -------------------->    1   4
   / \         <--------------------      / \
  1   3              2 left               3   5

右旋

  • 红色节点，旧根（失衡节点）

  • 黄色节点，旧根的左孩子，将来作为新根，旧根是它右孩子

  • 绿色节点，新根的右孩子，将来要换爹作为旧根的左孩子

旋转后

代码

  1. //参数：要旋转的节点 也就是失衡节点 
  2. private AVLNode rightRotate(AVLNode red) {
  3.     //黄色节点，旧根的左孩子
  4.     AVLNode yellow = red.left;
  5.     //绿色节点：当黄色节点有右孩子不是null，则要执行下面的red.left = green;  如果黄色节点有右孩子是null，就不需要执行red.left = green; 
  6.     //但是如果黄色节点有右孩子是null 执行red.left = green; 指向Null也没事
  7.     AVLNode green = yellow.right;
  8.     yellow.right = red;
  9.     red.left = green;
  10.     //做完失衡调整以后 记得要做更新高度操作 更新高度的操作不能改变
  11.     updateHeight(red);
  12.     updateHeight(yellow);
  13.     return yellow;
  14. }

左旋

旋转前

  • 红色节点，旧根（失衡节点）

  • 黄色节点，旧根的右孩子，将来作为新根，旧根是它左孩子

  • 绿色节点，新根的左孩子，将来要换爹作为旧根的右孩子

旋转后

代码 ：与右旋的代码相对

  1. private AVLNode leftRotate(AVLNode red) {
  2.     AVLNode yellow = red.right;
  3.     AVLNode green = yellow.left;
  4.     yellow.left = red;
  5.     red.right = green;
  6.     //做完失衡调整以后 记得要做更新高度操作 更新高度的操作不能改变
  7.     updateHeight(yellow);
  8.     updateHeight(red);
  9.     return yellow;
  10. }

左右旋

指先左旋左子树，再右旋根节点（失衡），这时一次旋转并不能解决失衡

左子树旋转后

根右旋前

根右旋后

代码

  1. private AVLNode leftRightRotate(AVLNode root) {
  2.     root.left = leftRotate(root.left);
  3.     return rightRotate(root);
  4. }

右左旋

指先右旋右子树，再左旋根节点（失衡）

右子树右旋后

 根左旋前

根左旋后

代码

  1. private AVLNode rightLeftRotate(AVLNode root) {
  2.     root.right = rightRotate(root.right);
  3.     return leftRotate(root);
  4. }

你发现有这四种不平衡情况，其实基本操作就是左旋和右旋这两种。

判断及调整平衡代码

  1. //检查节点是否失衡，重新平衡代码
  2. private AVLNode balance(AVLNode node) {
  3.     if (node == null) {
  4.         return null;
  5.     }
  6.     int bf = bf(node);
  7.     
  8.     if (bf > 1 && bf(node.left) >= 0) { //LL
  9.         return rightRotate(node);
  10.     } else if (bf > 1 && bf(node.left) < 0) { //LR
  11.         return rightLeftRotate(node);
  12.     } else if (bf < -1 && bf(node.right) > 0) { //RL
  13.         return leftRightRotate(node);
  14.     } else if (bf < -1 && bf(node.right) <= 0) {//RR
  15.         return rightRotate(node);
  16.     }
  17.     return node;
  18. }

以上四种旋转代码里，都需要更新高度，需要更新高度的节点只有红色、黄色，而绿色节点与其他无色节点高度是不变的

新增操作

  1. AVLNode root;
  2. public void put(int key, Object value) {
  3.     root = doPut(root, key, value);
  4. }
  5. //传来的根节点
  6. private AVLNode doPut(AVLNode node, int key, Object value) {
  7.     //1.找到空位  创建新节点
  8.     if (node == null) {
  9.         return new AVLNode(key, value);
  10.     }
  11.     //2.Key已存在，则更新
  12.     if (key == node.key) {
  13.         node.value = value;
  14.         return node;
  15.     }
  16.     if (key < node.key) {
  17.         node.left = doPut(node.left, key, value);
  18.     } else {
  19.         node.right = doPut(node.right, key, value);
  20.     }
  21.     updateHeight(node);
  22.     return balance(node);
  23. }

删除操作

  1. public void remove(int key) {
  2.     root = doRemove(root, key);
  3. }
  4.  
  5. //node:传入的根节点
  6. private AVLNode doRemove(AVLNode node, int key) {
  7.     // 1. node == null
  8.     if (node == null) {
  9.         return null;
  10.     }
  11.     // 2. 没找到 key
  12.     if (key < node.key) {
  13.         node.left = doRemove(node.left, key);
  14.     } else if (node.key < key) {
  15.         node.right = doRemove(node.right, key);
  16.     } else {
  17.         // 3. 找到 key  1) 没有孩子 2) 只有一个孩子 3) 有两个孩子
  18.         if (node.left == null && node.right == null) { //1) 没有孩子
  19.             return null;
  20.         } else if (node.left == null) { //2) 只有一个孩子
  21.             node = node.right;
  22.         } else if (node.right == null) {//2) 只有一个孩子
  23.             node = node.left;
  24.         } else { //3) 有两个孩子
  25.             AVLNode s = node.right; //初始是待删除的右子树  
  26.             //当后继节点与待删除节点不是相邻的
  27.             while (s.left != null) {
  28.                 s = s.left;
  29.             }
  30.             //找到后继节点:s
  31.             s.right = doRemove(node.right, s.key);//如果后继节点也有孩子，要把后继节点的孩子处理好
  32.             s.left = node.left;
  33.             //后继节点代替待删除节点
  34.             node = s;
  35.         }
  36.     }
  37.     if (node == null) {
  38.         return null;
  39.     }
  40.     // 4. 更新高度
  41.     updateHeight(node);
  42.     // 5. balance
  43.     return balance(node);
  44. }

完整代码备份

  1. public class AVLTree {
  2.     static class AVLNode {
  3.         int height = 1;
  4.         int key;
  5.         Object value;
  6.         AVLNode left;
  7.         AVLNode right;
  8.  
  9.         public AVLNode(int key) {
  10.             this.key = key;
  11.         }
  12.  
  13.         public AVLNode(int key, Object value) {
  14.             this.key = key;
  15.             this.value = value;
  16.         }
  17.  
  18.         public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
  19.             this.key = key;
  20.             this.value = value;
  21.             this.left = left;
  22.             this.right = right;
  23.         }
  24.     }
  25.  
  26.     AVLNode root;
  27.  
  28.     private AVLNode leftRotate(AVLNode p) {
  29.         AVLNode r = p.right;
  30.         AVLNode b = r.left;
  31.         r.left = p;
  32.         p.right = b;
  33.         //做完失衡调整以后 记得要做更新高度操作 更新高度的操作不能改变
  34.         updateHeight(p);
  35.         updateHeight(r);
  36.         return r;
  37.     }
  38.  
  39.     private void updateHeight(AVLNode node) {
  40.         node.height = Integer.max(height(node.left), height(node.right)) + 1;
  41.     }
  42.  
  43.     private AVLNode rightRotate(AVLNode r) {
  44.         AVLNode a = r.left;
  45.         AVLNode b = a.right;
  46.         a.right = r;
  47.         r.left = b;
  48.         //做完失衡调整以后 记得要做更新高度操作  更新高度的操作不能改变
  49.         updateHeight(r);
  50.         updateHeight(a);
  51.         return a;
  52.     }
  53.  
  54.     private AVLNode leftRightRotate(AVLNode p) {
  55.         AVLNode r = p.left;
  56.         p.left = leftRotate(r);
  57.         return rightRotate(p);
  58.     }
  59.  
  60.     private AVLNode rightLeftRotate(AVLNode p) {
  61.         AVLNode r = p.right;
  62.         p.right = rightRotate(r);
  63.         return leftRotate(p);
  64.     }
  65.  
  66.     private int height(AVLNode node) {
  67.         return node == null ? 0 : node.height;
  68.     }
  69.  
  70.  
  71.  
  72.     public void remove(int key) {
  73.         root = doRemove(root, key);
  74.     }
  75.  
  76.     private AVLNode doRemove(AVLNode node, int key) {
  77.         if (node == null) {
  78.             return null;
  79.         }
  80.         if (key < node.key) {
  81.             node.left = doRemove(node.left, key);
  82.         } else if (node.key < key) {
  83.             node.right = doRemove(node.right, key);
  84.         } else {
  85.             if (node.left == null) {
  86.                 node = node.right;
  87.             } else if (node.right == null) {
  88.                 node = node.left;
  89.             } else {
  90.                 AVLNode s = node.right;
  91.                 while (s.left != null) {
  92.                     s = s.left;
  93.                 }
  94.                 s.right = doRemove(node.right, s.key);
  95.                 s.left = node.left;
  96.                 node = s;
  97.             }
  98.         }
  99.         if (node == null) {
  100.             return null;
  101.         }
  102.         updateHeight(node);
  103.         return balance(node);
  104.     }
  105.  
  106.     public void put(int key, Object value) {
  107.         root = doPut(root, key, value);
  108.     }
  109.  
  110.     private AVLNode doPut(AVLNode node, int key, Object value) {
  111.         if (node == null) {
  112.             return new AVLNode(key, value);
  113.         }
  114.         if (key == node.key) {
  115.             node.value = value;
  116.             return node;
  117.         }
  118.         if (key < node.key) {
  119.             node.left = doPut(node.left, key, value);
  120.         } else {
  121.             node.right = doPut(node.right, key, value);
  122.         }
  123.         updateHeight(node);
  124.         return balance(node);
  125.     }
  126.  
  127.     private int bf(AVLNode node) {
  128.         return height(node.left) - height(node.right);
  129.     }
  130.  
  131.     private AVLNode balance(AVLNode node) {
  132.         if (node == null) {
  133.             return null;
  134.         }
  135.         int bf = bf(node);
  136.         if (bf > 1 && bf(node.left) >= 0) {
  137.             return rightRotate(node);
  138.         } else if (bf > 1 && bf(node.left) < 0) {
  139.             return rightLeftRotate(node);
  140.         } else if (bf < -1 && bf(node.right) > 0) {
  141.             return leftRightRotate(node);
  142.         } else if (bf < -1 && bf(node.right) <= 0) {
  143.             return rightRotate(node);
  144.         }
  145.         return node;
  146.     }
  147. }

小结

AVL树的优点：

  1. AVL树是一种自平衡树，保证了树的高度平衡，从而保证了树的查询和插入操作的时间复杂度均为O(logn)。

  2. 相比于一般二叉搜索树，AVL树对查询效率的提升更为显著，因为其左右子树高度的差值不会超过1，避免了二叉搜索树退化为链表的情况，使得整棵树的高度更低。

  3. AVL树的删除操作比较简单，只需要像插入一样旋转即可，在旋转过程中树的平衡性可以得到维护。

AVL树的缺点：

  1. AVL树每次插入或删除节点时需要进行旋转操作，这个操作比较耗时，因此在一些应用中不太适用。

  2. 在AVL树进行插入或删除操作时，为保持树的平衡需要不断进行旋转操作，在一些高并发环节和大数据量环境下，这可能会导致多余的写锁导致性能瓶颈。

  3. AVL树的旋转操作相对较多，因此在一些应用中可能会造成较大的空间浪费。

  • 相关阅读:
    另一棵树的子树
    大数据技术基础实验四：HDFS实验——读写HDFS文件
    Java多线程专题之Callable、Future与FutureTask(含源码分析)
    【示波器专题】数字示波器的主要指标——带宽
    九、Linux高阶命令
    【设计模式】【创建型5-2】【工厂方法模式】
    Algorithms practice：Basic Calculator 224
    安装银河麒麟桌面系统V10【超详细图文教程】
    10、IOC 之类路径扫描和托管组件
    【产品设计】APP提升用户注册率的五个方案探讨结论
  • 原文地址：https://blog.csdn.net/m0_60333804/article/details/133788058