MySql索引之二叉树详解

寻梦xunm| 671| 收集

3年前

超过1211天温馨提示

本文最后更新于2021年05月27日，已超过1211天没有更新，若内容或图片失效，请留言反馈。

一、基本概念理解

1. 二叉查找树：又称二叉排序树/二叉搜索树

二叉查找树实际上是数据域有序的二叉树，即对树上的每个结点，都满足其左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。具有以下性质：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

2.满二叉树：

在一颗二叉树中，如果所有的分支节点都存在左子树和右子树，并且所有的叶子节点都在同一层上，这样的二叉树，我们称之为满二叉树。

3.完全二叉树：

对一颗具有n个结点的二叉树按层进行编号，如果编号为i

(1 <= i <= n)的结点与同样深度的满二叉树节点编号为i的结点

在二叉树中的位置完全相同，则这颗树，我们称之为完全二叉树。

4.AVL树既是平衡二叉树：

平衡二叉树建立在二叉排序树的基础上，目的是使二叉排序树的平均查找长度更小，即让各结点的深度尽可能小，因此，树中每个结点的两棵子树的深度不要偏差太大。

平衡二叉树的递归定义：
平衡二叉树是一棵二叉树，其可以为空，或满足如下2个性质：

①左右子树深度之差的绝对值不大于1。
②左右子树都是平衡二叉树。

平衡因子的概念：
结点的平衡因子 = 结点的左子树深度 — 结点的右子树深度。
若平衡因子的取值为-1、0或1时，该节点是平衡的，否则是不平衡的。

二、AVL树旋转

在进行插入和删除之前需要先了解AVL树的旋转操作。旋转操作主要包括LL（左左）旋转、LR（左右）旋转、RR（右右）旋转、RL（右左）旋转，LL旋转与RR旋转对称，LR旋转与RL旋转对称。
旋转操作是在插入结点或删除结点导致原AVL树不平衡时进行的。
我的理解是当二叉树失衡的原因出现在“最低失衡根结点左子树的左子树”（所谓“最低失衡根结点”，则是从新增结点开始向根部回溯，所遇到的第一个失衡的根节点）时，则使用LL旋转来调整；当失衡出现在“最低失衡根节点左子树的右子树”，则使用LR旋转调整；RR旋转，RL旋转同理。

2.1 LL旋转

如上图所示，找到“最低失衡根结点”，上图是结点5，二叉树失衡的原因是因为结点1的存在，而结点1位于结点5“左子树的左子树”，所以要使用LL旋转来调节，只需一次旋转即可达到平衡。
具体的方法是：
LL旋转的对象是“最低失衡根结点”，也就是结点5，找到5的左孩子3，将3的右孩子4变成5的左孩子，最后将5变成3的右孩子，调整后的AVL树如下所示：

2.2 RR旋转

RR旋转与LL旋转对称。

如上图所示，“最低失衡根结点”是结点2，二叉树的失衡是结点6导致的，而结点6位于结点2“右子树的右子树”，所以要使用RR旋转来调节，只需一次旋转即可达到平衡。
方法与LL旋转类似：
RR旋转的对象是“最低失衡根结点”，这里是结点2，找到2的右孩子4，将4的左孩子3变成2的右孩子，最后将2变成4的右孩子，旋转后的结果如下图所示：

2.3 LR旋转

LR旋转和RL旋转这个比较难理解，笔者也是查了好多资料才搞懂，下面一起看下。
LL旋转和RR旋转只需一次旋转即可达到平衡，而LR旋转和RL旋转需两次旋转才能达到平衡。

如上图所示，“最低失衡根结点”为结点5，二叉树失衡是因为结点3的存在，结点3位于结点5“左子树的右子树”，所以使用LR旋转来调节。
方法：
（1）先对最低失衡根结点的左孩子（结点2）进行RR旋转
（2）再对最低失衡根结点（结点5）进行LL旋转。下图演示了调整过程

2.4 RL旋转

RL旋转与LR旋转对称，先LL旋转，在RR旋转。

分析过程与LR相似。
旋转步骤：
（1）先对最低失衡结点右孩子（结点5）LL旋转；
（2）在对最低失衡结点（结点2）RR旋转。
旋转过程如下：

由于AVL树需要做到平衡，所以每次插入叶子节点，如果发现不平衡，都需要进行旋转以保持平衡。
上面如果还未理解，这里转载了一个图片，描述了AVL树旋转平衡的操作——