AVL双旋转思路分析与图解

AVL树双旋转思路分析与图解

首先我们要知道什么情况之下我们是要进行双旋转?

当最小不平衡子树为LR型或者RL型的时候, 那么什么时候最小不平衡子树是RL型或者什么时候又是LR型的?

• 下面我们就先给出LR型, RL型, LL型, RR型最小不平衡子树的概念:
  1. LR型最小不平衡子树: 首先拿到一个最小不平衡子树, ①我们判断这个最小不平衡子树的左子树高还是右子树高, 如果左子树高, 这个时候就是L, ②然后之后我们再判断这个最小不平衡子树的根节点的左子节点的左子树和右子树谁高, 如果这个时候右子树高, 那么就是R, ①②两步结合到一起之后就会得到LR, 就说明这个最小不平衡子树是一个LR型的
  2. LL型最小不平衡子树: 首先拿到一个最小不平衡子树, ①我们判断这个最小不平衡子树的左子树高还是右子树高, 如果左子树高, 这个时候就是L, ②然后之后我们再判断这个最小不平衡子树的根节点的左子节点的左子树和右子树谁高, 如果这个时候还是左子树高, 那么就是L, ①②两步结合到一起之后就会得到LL, 就说明这个最小不平衡子树是一个LL型的
  3. RL型最小不平衡子树: 首先拿到一个最小不平衡子树, ①我们判断这个最小不平衡子树的左子树高还是右子树高, 如果右子树高, 这个时候就是R, ②然后之后我们再判断这个最小不平衡子树的根节点的右子节点的左子树和右子树谁高, 如果这个时候左子树高, 那么就是L, ①②两步结合到一起之后就会得到RL, 就说明这个最小不平衡子树是一个RL型的
  4. RR型最小不平衡子树: 首先拿到一个最小不平衡子树, ①我们判断这个最小不平衡子树的左子树高还是右子树高, 如果右子树高, 这个时候就是R, ②然后之后我们再判断这个最小不平衡子树的根节点的右子节点的左子树和右子树谁高, 如果这个时候还是右子树高, 那么就是R, ①②两步结合到一起之后就会得到RR, 就说明这个最小不平衡子树是一个RR型的
• 注意: 上面的前提是一个最小不平衡子树
  • 最小不平衡子树就是距离添加或者删除结点最近的BF > |1|的结点为根节点的子树
    • BF为平衡因子: 某个结点的平衡因子就是某个结点的左子树高度减去对应的右子树高度的插值, 我们的平衡二叉树的每个结点的BF都要是满足: -1 <= BF <= 1

对于数列{10, 11, 7, 6, 8, 9}, 当添加9之后就不是一个AVL树了, 也就是不平衡了, 那么这个时候我们要如何将其重新平衡化? 也就是如何重新让其变为一个AVL树?

• 因为此时最小不平衡子树是LR型的， 所以我们要先对当前最小不平衡子树的根节点的左子树进行一个左旋，然后我们就能得到一个LL型的最小不平衡子树， 然后针对LL型的最小不平衡子树我们直接调用一个右旋算法即可（如下图）

  1. 先对原本为LR型的最小不平衡子树的根节点的左子节点进行一个左旋, 得到一个LL型的最小不平衡子树(如下)

  

  • 此时因为我们的最小不平衡子树是一个LR型的, 所以这个时候我们的正确解法就是:

    1. 先对这个LR型的最小不平衡子树的左子节点进行一个左旋, 左旋之后我们就得到了一个LL型的最小不平衡子树

    2. 对于得到的LL型的最小不平衡子树, 我们只需要再对此LL型最小不平衡子树的跟结点执行一个右旋算法就可以了 —> 我们此时就是经过了两次旋转, 我们将这样的算法就称之为"双旋转"(其实就是用了一次左旋 + 右旋而已)

    • 这个时候有的人就会有问题, 那么这个时候这个LR型最小不平衡子树不也是最小不平衡子树根节点的左子树高度 > 最小不平衡子树根节点的右子树高度吗? 所以我们直接对这个LR型的最小不平衡子树的根节点执行一个右旋算法不行吗, 按理我们的右旋算法会降低左子树的高度增加右子树的高度呀, 这个时候问题不就解决了?

      • 是个想法是错误的, 我们的左旋和右旋算法只适用于单一倾斜的子树的根节点的左子树和右子树的高度转换, 这个时候如果非要对此LR型的最小不平衡子树的根节点执行一个右旋之后我们就可以发现, 我们的LR型的最小不平衡子树又会变为一个RL型的最小不平衡子树(这个过程中我们的左子树的高度在右旋中直接减少了2, 而右子树的高度在右旋中直接加了2) —> 所以这就告诉我们对于RL型和LR型最小不平衡子树的平衡化, 我们直接对不平衡子树根节点进行一次单一的旋转是行不通的

  2. 对得到的LL型最小不平衡子树, 我们只需要对LL型不平衡子树的根节点执行一个右旋之后就可以得到一颗平衡二叉树了(如下:)

  

  • 这样我们最终就得到了一个平衡的AVL树了

对于RL型的最小不平衡子树我们也是采用上述的双旋转操作, 只是通过如下的两步实现:

1. 对RL型的最小不平衡子树的根节点的右子树进行一个左旋, 就能得到一个RR型的最小不平衡子树
2. 对得到的RR型的最小不平衡子树的根节点进行一个右旋, 就能得到一个AVL树(二分平衡搜索树)

补充:

我们最后会在完成AVL树的代码实现时, 将左旋和右旋,双旋转的调用都加到AVL树添加结点的操作中

• 那么分别是什么时候调用这几种旋转?

  1. LL型 --> 右旋
  2. LR型和RL型 —> 双旋转
  3. RR型 —> 左旋
  • 我们分别在不同的情况之下调用不同的方法即可
    • 判断是那种情况我们就直接根据前面的这四种最小不平衡子树的定义来判断, 这里我们判断最小不平衡子树的时候要通过树的高度来判断, 所以我们还需要编写一个求解树的高度的方法

• 其实双旋转肯定也只不过是在调用我们的左旋和右旋操作而已, 所以说AVL树中其实只需要掌握左旋和右旋操作即可