原文链接:https://blog.csdn.net/u013067756/article/details/54236172

看到最后的帮忙点个赞👍🙏 谢谢,这个对我真的很重要！

1. 概述

1.1 定义

• 平衡二叉树，全称为平衡二叉搜索树
• 它是由苏联数学家Adelson-Velsky 和 Landis提出来的，因此平衡二叉树又叫AVL树

平衡二叉树的定义是一种递归定义，要求每个节点都具有以下特性：

1. 可以是一棵空树
2. 左子树和右子树高度之差的绝对值不超过1（左右子树的高度差可以为0、1和 -1）
3. 左子树和右子树均为平衡二叉树

为什么平衡二叉树是二叉搜索树？

• 之前，在学习二叉搜索树时，增删该查的效率最坏为$O(n)$。此时，二叉树退化成一条链
• 若二叉搜索树尽可能的平衡，增删改查的时间复杂度将稳定在$O(lo{g}_{2}N)$
• 因此，我们希望二叉搜索树是平衡的二叉树，我想这也是平衡二叉树是基于二叉搜索树提出来的原因

1.2 平衡因子与最小不平衡子树

平衡因子

• 定义中，左子树和右子树高度之差被称作平衡因子：左子树高度 - 右子树高度
• AVL树中，要求 $abs(平衡因子)<=1$，即左右子树的高度差为0、1和 -1
• 以上数值分别表示：左子树与右子树等高、左子树比右子树高、左子树比右子树矮

最小不平衡子树

• 平衡二叉树，要求平衡因子 $abs(平衡因子)<=1$
• 下图，新插入节点37，该树不再是平衡二叉树。因为，节点58的左右子树高度差为2
  
• 从新插入节点向上查找，第一个 $abs(平衡因子)>1$的节点为根的子树，被称为最小不平衡子树
• 上图中，新插入节点向上查找，节点58左右子树高度差为2，以节点58为根节点的子树，就是最小不平衡子树

关于最小不平衡子树的说明

1. 新插入节点，可能导致平衡二叉树出现多棵不平衡的子树
2. 此时，我们只需要调整最小不平衡子树，就能让整棵树平衡

2. 平衡二叉树的左旋/右旋

• 本章中，红色表示最小不平衡子树的根节点，蓝色表示新插入的节点

2.1 右旋

• 上图中，节点58为根节点的子树抽取出来。
• 想要让其变成二叉平衡树，最简单的想法，将根节点58向左儿子47的右下方下压（降低左子树高度）
• 下压后，根节点58成为左儿子47的右子树，将与左儿子原本的右子树51冲突
• 巧妙之处： 将原本的右子树51改成根节点58的左子树，整棵树恢复平衡
  
• 上述操作就是平衡二叉树的右旋：将根节点绕左儿子顺时针下压

右旋的规则

1. 根节点成为左子节点的右子树
2. 左子节点原本的右子树成为根节点的左子树（一个右子树被占据，一个左子树空闲，刚好可以互补）

• 新插入节点37的插入位置：根节点58的左儿子的左子树上，这种情况称为LL
• 后续，我们还将接触RR、LR、RL三种情况

2.2 左旋

• 下图中，新插入节点18，使得以12为根节点的树成为不平衡二叉树，最小不平衡子树的根节点也是12
• 此时，左子树比右子树矮2
• 要想平衡该二叉树，最直观的想法：将根节点12向右儿子15的左下方下压（降低右子树高度）
• 问题来了，此时根节点12成为右儿子的左子树，原本的左子节点13如何处理？
• 巧妙之处： 将原本的左子节13点变成节点12的右子树，整棵树恢复平衡
  
• 上述操作就是平衡二叉树的左旋：将根节点绕右儿子逆时针下压

左旋的规则

1. 根节点成为右儿子点的左子树
2. 右儿子原本的左子树成为根节点的右子树（一个左子树被占据，一个右子树空闲，刚好互补）

• 新插入节点18的位置：根节点12的右儿子的右子树，这种情况称为RR

2.3 调整的四种情况

• 上面小节中，我们通过右旋和左旋，见识了平衡二叉树调整的两种情况，分别是LL和RR

四种情况的描述

1. LL：新插入节点为最小不平衡子树根节点的左儿子的左子树上 $\to$ 右旋使其恢复平衡

2. RR：新插入节点为最小不平衡子树根节点的右儿子的右子树上 $\to$ 左旋使其恢复平衡

3. LR：新插入节点为最小不平衡子树根节点的左儿子的右子树上 $\to$ 以左儿子为根节点进行左旋，再按原始的根节点右旋
   

4. RL：新插入节点为最小不平衡子树根节点的右儿子的左子树上 $\to$ 以右儿子为根节点进行右旋，再按原始的根节点左旋
   

2.4 构建平衡二叉树

• 基于数组{3, 2, 1, 4, 5, 6, 7, 10, 9, 8}构建一棵平衡二叉树
• 具体的构建过程，参考博客：平衡二叉树实现原理 —— Best example 👍 👍👍👍
• 这是我见过的、唯一的从零开始构建一棵平衡二叉树，且LL、RR、LR、RL四种情况都包含的示例

参考链接：

• 什么是平衡二叉树（AVL）
• 平衡二叉树实现原理（链接失效）

3. 代码实现

3.1 树节点的定义

增加高度属性

• 二叉搜索树是否平衡，取决于左右子树的高度差
• 插入节点或删除节点时，想要知道二叉树是否保持平衡，需要计算左右子树的高度
• 计算左右子树的高度，一般通过自顶向下或自底向上的方式，递归计算（不对深度和高度加以区分）
• 这样将会存在一定的时间开销和空间开销
• 因此，需要在原有的TreeNode基础上，增加一个高度字段，用于记录当前节点的高度
• 规定： 空节点的高度为0，叶子节点的高度为1，

平衡二叉树，树节点的定义如下

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

    public AVLNode() {
    }

    public AVLNode(int val) {
        this.height = 1;
        this.left = null;
        this.right = null;
        this.val = val;
    }

    // 获取某个节点的高度
    public int getHeight(AVLNode node) {
        return node == null ? 0 : node.height;
    }
}

3.2 LL、RR、LR、RL的实现

3.2.1 LL

• 当待插入节点位于最小不平衡子树根节点的左儿子的左子树时，需要将根节点右旋
• （1）根节点成为左儿子的右子树；（2）左儿子原本的右子树成为根节点的左子树

代码实现：

1. 先执行步骤（2），空出左儿子的右子树位置给根节点；再将根节点放置到左儿子的右子树位置
2. 右旋后，根节点和左儿子的高度需要更新
3. 左儿子就是调整后树的新根节点

   // LL，右旋
   public AVLNode rightRotate(AVLNode root) {
       // 右旋，左儿子成为新的根节点
       AVLNode newRoot = root.left;
       // 左儿子的右子树称为根节点的左子树
       root.left = newRoot.right;
       // 根节点成为右儿子的右子树
       newRoot.right = root;
   
       // 更新高度
       root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1;
       newRoot.height = Math.max(getHeight(newRoot.left), root.height) + 1;
   
       return newRoot;
   }
   

3.2.2 RR

• 当待插入节点位于最小不平衡子树根节点的右儿子的右子树时，需要进行左旋
• （1）根节点成为右儿子的左子树；（2）右儿子原本的左子树成为根节点的右子树

代码实现

1. 先执行步骤（2），空出右儿子的左子树给根节点；再将根节点放到右儿子的左子树位置

2. 左旋后，需要更新根节点和右儿子的高度

3. 右儿子成为新的根节点

   // RR，左旋
   public AVLNode leftRotate(AVLNode root) {
       // 左旋，右儿子成为新的根节点
       AVLNode newRoot = root.right;
       // 右儿子的左子树成为根节点的右子树
       root.right = newRoot.left;
       // 根基点成为右儿子的左子树
       newRoot.left = root;
   
       // 更新根节点和新根节点的高度
       root.height = Math.max(getHeight(root.left), getHeight(root.left)) + 1;
       newRoot.height = Math.max(getHeight(newRoot.right), root.height) + 1;
   
       return newRoot;
   }
   

3.2.3 LR

• 当插入节点位于最小不平衡子树根节点的左儿子的右子树时，先左旋左儿子，再右旋根节点

• LL和RR操作已经实现，再实现LR就很简单了

  // LR，左旋左儿子，再右旋根节点
  public AVLNode leftRightRotate(AVLNode root) {
      // 左旋左儿子
      root.left = leftRotate(root.left);
      // 右旋根节点
      return rightRotate(root);
  }
  

3.2.4 RL

• 当插入节点位于最小不平衡子树根节点的右儿子的左子树时，先右旋右儿子，再左旋根节点

• LL和RR操作已经实现，再实现RL就很简单了

  // RL, 右旋右儿子，再左旋根节点
  public AVLNode rightLeftRotate(AVLNode root) {
      // 右旋右儿子
      root.right = rightRotate(root.right);
      // 左旋根节点
      return leftRotate(root);
  }
  

3.3 插入节点

3.3.1 插入节点

• 插入节点时，与二叉搜索的插入一样，需要先根据大小关系确定插入位置

• 完成插入后，如果导致当前树不平衡，需要旋转使其平衡
  （1）左儿子插入的，有LL、LR两种情况
  （2）右儿子插入的，有RR、RL两种情况

• 不管是否调整平衡因子，都需要更新根节点的高度

  public AVLNode insert(int val, AVLNode root) {
      // 根节点为空，直接新建节点
      if (root == null) {
          return new AVLNode(val);
      }
  
      // 根据大小关系确定插入位置
      if (root.val > val) {
          // 在左儿子中插入，可能会使得左儿子变高
          root.left = insert(val, root.left);
  
          // 插入后，不平衡需要调整
          if (getHeight(root.left) - getHeight(root.right) == 2) {
              // 插入的位置是左儿子的左子树，需要右旋
              if (root.left.val > val) {
                  root = rightRotate(root);
              } else { // 左儿子的右子树，需要先左旋再右旋
                  root = leftRightRotate(root);
              }
          }
      } else if (root.val < val) {
          root.right = insert(val, root.right);
  
          // 插入后，不平衡需要调整
          if (getHeight(root.right) - getHeight(root.left) == 2) {
              // 右儿子的右子树，左旋
              if (root.right.val < val) {
                  root = leftRotate(root);
              } else {
                  root = rightLeftRotate(root);
              }
          }
      }
  
      // 完成插入更新高度
      root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1;
  
      return root;
  }
  

3.3.2 构建平衡二叉树

• 基于插入节点功能，可以输入一组节点值，构建一棵平衡二叉树

• 代码如下

  public AVLNode buildTree(int[] nums) {
     // 创建一个空的根节点
     AVLNode root = null;
  
     // 依次完成节点插入
     for (int i = 0; i < nums.length; i++) {
         root = insert(nums[i], root);
     }
  
     return root;
  }
  

3.3.3 功能验证

• 为了验证构建好的二叉树，是否是我们预期的结构，需要打印二叉树

• 由于使用上一章节中的数组{3, 2, 1, 4, 5, 6, 7, 10, 9, 8}

• 二叉树的节点值和最终的树结构已知，作者选择通过层次遍历打印二叉树

• 稳妥的做法： 通过二叉树是否平衡、中序遍历是否为升序来确定构建效果

  // 层次遍历二叉树
  public List<Integer> levelTraverse(AVLNode root) {
      List<Integer> list = new ArrayList<>();
      // 特殊情况，直接返回结果
      if (root == null) {
          return list;
      }
  
      // 借助队列实现层次遍历
      Queue<AVLNode> queue = new LinkedList<>();
      queue.offer(root);
      list.add(root.val);
  
      while (!queue.isEmpty()) {
          // 出队，访问左右子节点
          AVLNode node = queue.poll();
          if (node.left != null) {
              queue.offer(node.left);
              list.add(node.left.val);
          }
  
          if (node.right != null) {
              queue.offer(node.right);
              list.add(node.right.val);
          }
      }
  
      return list;
  }
  

• 完成构建函数的实现后，通过以下代码验证是否成功构建平衡二叉树

  int[] nums = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
  AVLNode root = new AVLNode();
  // 构建平衡二叉树
  root = root.buildTree(nums);
  // 打印二叉树，判断构建是否ok
  System.out.println(root.levelTraverse(root));
  

• 执行结果：[4, 2, 7, 1, 3, 6, 9, 5, 8, 10]，与真实树结构的层次遍历结果一致
  

十分感谢大佬的博客，给我构建平衡二叉树的灵感。看了很多博客，还是这篇博客写得比较符合我的需求

• java数据结构与算法之平衡二叉树(AVL树)的设计与实现

3.4 删除节点

3.4.1 删除节点分析及代码实现

• 对于删除节点，之前学习过如何删除二叉搜索树中的节点
  （1）被删除节点是叶子节点，直接删除
  （2）被删除节点有右子树，将后继节点上提，再递归删除后继节点
  （3）被删除节点只有左子树，将前驱节点上提，在递归删除前驱节点

• 现在问题来了，删除节点以后，可能会使得平衡二叉树失去平衡，如何调整使其依然保持平衡？

• 感谢博客：[Java]平衡二叉树的插入与删除，给我灵感

完成节点删除后：

1. 如果 $height(左子树)-height(右子树)>=2$，说明被删除节点位于右子树。因为右子树变矮，才变得不平衡
2. 如果 $height(右子树)-height(左子树)>=2$，说明被删除节点位于左子树。因为左子树变矮，才变得不平衡
3. 删除节点可以看做插入节点：在右子树删除节点 $\to$ 在左子树插入节点；在左子树删除节点 $\to$ 在右子树插入节点
4. 左子树插入节点：$height(左儿子的左子树)>height(左儿子的右子树)$，说明是在左儿子的左子树插入，属于LL；否则， 属于LR
5. 右子树插入节点：$height(右儿子的右子树)>height(右儿子的左子树)$，说明是在右儿子的右子树插入，属于RR；否则，属于RL

• 代码实现如下

  public AVLNode remove(AVLNode root, int val) {
      // 停止条件：节点为null，无法继续删除
      if (root == null) {
          return null;
      }
  
      // 通过大小关系，确定删除节点的位置
      if (root.val > val) {
          // 在左子树进行节点删除
          root.left = remove(root.left, val);
      } else if (root.val < val) {
          root.right = remove(root.right, val);
      } else {
          // 找到了对应的节点，按情况删除
          if (root.left == null && root.right == null) {
              root = null;
          } else if (root.right != null) {
              // 后继节点上提，再删除后继节点
              AVLNode successor = successor(root);
              root.val = successor.val;
  
              // 在右子树中删除后继节点
              root.right = remove(root.right, successor.val);
          } else {
              // 前驱节点上提，再删除前驱节点
              AVLNode preSuccessor = preSuccessor(root);
              root.val = preSuccessor.val;
  
              // 在左子树中删除前驱节点
              root.left = remove(root.left, preSuccessor.val);
          }
      }
  
      // 删除完成后，可能需要调整平衡度
      if (root == null) {
          return null;
      }
  
      // 左子树比右子树高，说明删除的是右子树的节点
      if (getHeight(root.left) - getHeight(root.right) >= 2) {
          // 模拟在左子树插入的情况：在左儿子的左子树插入，在左儿子的右子树插入
          if (getHeight(root.left.left) > getHeight(root.left.right)) {
              return rightRotate(root);
          } else {
              return leftRightRotate(root);
          }
      } else if (getHeight(root.right) - getHeight(root.left) >= 2) { // 在左子树删除节点
          // 模拟在右子树插入节点
          if (getHeight(root.right.right) > getHeight(root.right.left)) {
              return leftRotate(root);
          } else {
              return rightLeftRotate(root);
          }
      }
  
      // 无需调整，直接更新root的高度并返回
      root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1;
      return root;
  }
  
  // 寻找前驱节点
  private AVLNode preSuccessor(AVLNode root) {
      // 特殊情况
      if (root == null) {
          return null;
      }
      // 左子树寻找最右节点
      root = root.left;
      while (root.right != null) {
          root = root.right;
      }
      return root;
  }
  
  // 寻找后继节点
  private AVLNode successor(AVLNode root) {
      // 特殊情况
      if (root == null) {
          return null;
      }
      // 在右子树寻找最左节点
      root = root.right;
      while (root.left != null) {
          root = root.left;
      }
  
      return root;
  }
  

3.4.2 功能验证

• 仍然基于上面的二叉树，进行节点删除

情况一：依次删除8, 5, 6

• 代码如下

  int[] nums = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
  AVLNode root = new AVLNode();
  // 构建平衡二叉树
  root = root.buildTree(nums);
  System.out.println(root.levelTraverse(root));
  // 节点的删除
  root = root.remove(root, 8);
  System.out.println(root.levelTraverse(root));
  
  root = root.remove(root, 5);
  System.out.println(root.levelTraverse(root));
  
  root = root.remove(root, 6);
  System.out.println(root.levelTraverse(root));
  

• 删除节点后的结果
  

• 情况二：删除5, 6
  

• 相关代码

  int[] nums = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};
  AVLNode root = new AVLNode();
  // 构建平衡二叉树
  root = root.buildTree(nums);
  System.out.println(root.levelTraverse(root));
  // 删除节点5和6
  root = root.remove(root, 5);
  System.out.println(root.levelTraverse(root));
  
  root = root.remove(root, 6);
  System.out.println(root.levelTraverse(root));
  

• 打印结果
  

4. 后记

• 平衡二叉树是基于二叉搜索树定义的，其结构必须满足父节点与左右子节点之间的val要求
• 平衡二叉树，要求左右子树的高度超不超过1；如果超过，则处于不平衡状态
• 插入节点时，调整都是基于最小不平衡子树进行的。
• 包括LL、RR、LR、RL四种情况，前面两种情况只需要一次旋转；后面两种情况，需要两次旋转
• 节点删除，二叉搜索节点删除 + 模拟节点插入二者的结合
• 后续，可以通过leetcode上与二叉搜索树/平衡二叉树有关的题目加深理解
  • 108. 将有序数组转换为二叉搜索树
  • 1382. 将二叉搜索树变平衡
  • 110. 平衡二叉树 ，相同题目：剑指 Offer 55 - II. 平衡二叉树
  • 面试题 04.05. 合法二叉搜索树

考试重点（选择题）：
1.我们在二叉排序树中，插入一个新结点之后，怎么保证这棵树依然是“平衡二叉树”。
2.高为h的平衡二叉树，最少有几个结点——递推求解

一、定义

平衡二叉树，简称平衡树（AVL树）： 树上任一结点的左子树和右子树的高度之差不超过1。
ps:AVL是平衡树 ——ASL是：平均查找长度 =》不要混淆。

结点的平衡因子某结点的左子树高-右子树高
二叉树是平衡的话，各个结点的平衡银子只能是：“-1,0,1”。
例如：如下图，50根节点，左子树高度是2，而右子树高度为3.所以：结点的平衡银子=左子树2-右子树3=-1

让一颗二叉排序树保持平衡，就可以保证查找效率：log2n

二、插入操作

在我们插入一个新结点后，如何保持二叉树的平衡？
方法：我们可以从新插入的结点开始往上找，找到第一个不平衡的结点，进行调整以该结点为根的子树——最小不平衡子树。
最小不平衡子树：最小的结点的左右子树高度相差大于1

三、插入后调整“不平衡”问题

在插入操作中，只要将最小不平衡树调整平衡，则其他祖先结点都会恢复平衡。
二叉排序树的特性：
左子树结点值< 根节点的值 < 右子树结点的值
目标：
1.插入新结点后，恢复平衡
2.保持二叉排序树的特性。

1.LL左孩子左子树平衡旋转（右单旋转）

由于结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子从1增2，导致A为根的子树失去平衡，需要一次向右的旋转操作：
将A的左孩子B向右上旋转代替A称为根节点，将A结点向右下旋转称为B的右子树的根节点，而B的原右子树则作为A结点的左子树。

自己简述：
在调整LL最小不平衡子树中，让目前根的左子树B结点成为根节点，并让左子树的右子树BR，成为原根A结点的左子树。（原根节点A，之前左子树是B，现在A成了根节点B的右子树了）

1.LL代码：

f是指向原根节点
P指向根节点的左子树



f->lchild=p->rchild;
B的右子树，成为A结点的左子树。 
下一步是为了，让A结点成为B结点的右子树

p->rchild=f
A结点变成B的右孩子。
是因为F存放的是原根节点A的地址，现在将F的值赋值给B的右孩子了。
也就是说B的右孩子是A

gf->lchild/rchild=p
A的父结点原本指向A的孩子指针，指向P（也就是B）
也就是将根节点的上一结点指向根节点。
。从而B成了根节点

2.RR右孩子右子树平衡旋转（左单旋转）

RR 平衡旋转（左单旋转）。由于结点A的右孩子（R）的右子树（R）上插入了新结点，高度有-1变-2了，导致了A为根的子树失去了平衡，需要一次向左的旋转操作。将A根节点的右孩子B向左上旋转，代替A称为根节点。将A向左下旋转成为B的左孩子，将之前B的左子树，变成A的右子树
自己叙述：
在调整RR最小不平衡子树中，让目前根节点A的右子树成为根节点，现在B成为了根节点。再让B的右子树的左子树，成为现在根节点的左子树A结点的右子树。

1.RR代码：

不平衡之前
A是：根节点
B是：根节点A的右孩子

变平衡：
将B的左孩子变为A的右孩子，让A结点变成B的左孩子，在修改A的父结点指针，指向B结点。
（是因为根节点之前是A ，现在根节点是B。让父结点从A变成B）

平衡之后
B是：根节点
A是：根节点B的左孩子

3.LR左孩子右子树平衡旋转（ 旋转）

C结点就是  根节点的左子树的右孩子

先让C结点左旋转，顶替B的位置，
再让C结点在进行一个右上旋转。
替换A的位置。
---------------

首先是C左旋替换B的位置，然后B变成C的左孩子。
然后是C右旋替换A的位置，然后C的右孩子变成A的左孩子。
从而：A变成C的右孩子

4.RL右孩子的左子树平衡旋转（旋转）

先让C结点，右旋转顶替B，在左旋顶替A
--
右旋顶替B：
C的右孩子，成为B的左孩子。
C的右子树，成为B

左旋顶替A：
先让C的左子树，成为A的右子树。
再让C的左子树，成为A

5.练习：调整完以后，一定验算是否符合左中右依次递增。

1.

2.

3.

将60结点的左子树，交给他的父结点的右子树。
将60结点的右子树，交给他的爷结点的左子树。

四、查找效率分析

假设nh表示深度为h的平衡树中含有的最少结点数。

n1= 1
n2= 1+n1= =2
n3= n2+n1+1 =4
n4= n3+n2+1 =7
n5= n4+n3+1 = 7+4+1=12

平均查找长度（查找的时间复杂度）和树高是同一个数量级。