C++进阶：AVL树详解及模拟实现（图示讲解旋转过程）

1.AVL树介绍

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

1.1概念介绍

1. AVL树定义：
   • 解释AVL树是一种自平衡的二叉搜索树，由G.M. Adelson-Velsky和E.M. Landis在1962年提出。
   • 强调AVL树中每个节点的平衡因子（Balance Factor），即左子树高度和右子树高度之差不超过1。
2. 平衡因子：
   • 解释平衡因子的概念，即一个节点的左子树高度减去右子树高度的值。
   • 平衡因子为{-1, 0, 1}时，树是平衡的。
3. 自平衡性质：
   • 说明AVL树具有自平衡性质，即在插入或删除节点时，会通过旋转操作来保持树的平衡。
   • 提及AVL树的平衡因子限制，确保树的高度保持在对数级别。

AVL1

1.2核心性质

1. 严格平衡：
   • 强调AVL树的严格平衡性质，即每个节点的左右子树高度差不超过1。
   • 严格平衡性质保证了AVL树的高度近似于对数级别，保证了高效的插入、删除和查找操作。
2. 插入和删除操作：
   • 介绍当插入或删除节点时，AVL树如何通过旋转操作来保持平衡。
   • 解释插入和删除操作可能会导致树失去平衡，需要通过单旋转、双旋转等操作进行调整。
3. 时间复杂度：
   • 说明AVL树的插入、删除和查找操作的时间复杂度都是O(log n)，其中n为树中节点的数量。
   • 强调AVL树在动态数据集合中的高效性，适用于需要频繁更新的场景。

2.项目文件规划

头文件AVLTree.h：进行模拟的编写 源文件test.cpp：进行测试，检查代码逻辑是否满足期望

3.整体框架（节点和Tree）

4.AVL树的新节点插入

基本步骤：

1. 查找插入位置： 首先，我们需要找到新节点应该插入的位置。从根节点开始，按照二叉搜索树的性质，逐级向左或向右比较键值，直到找到一个合适的位置。
2. 插入新节点： 找到插入位置后，我们创建一个新的节点，并将其插入到树中。如果树为空，则新节点成为树的根节点。否则，将新节点插入到合适的位置，使得树仍然保持二叉搜索树的性质。
3. 更新平衡因子： 在插入新节点后，需要沿着插入路径更新所有受影响节点的平衡因子。平衡因子是指节点的左右子树的高度差。如果插入导致某个节点的平衡因子超出范围（通常是 -1、0、1），则需要进行旋转操作来恢复平衡。
4. 平衡调整： 如果插入操作破坏了 AVL 树的平衡性，我们需要进行一系列的旋转操作来重新平衡树。旋转操作包括单旋转和双旋转，具体的旋转方式取决于插入节点的位置以及平衡因子的情况。
5. 旋转后继续向上： 插入节点后，可能需要对父节点、祖父节点等进行旋转操作，直到树恢复平衡为止。

更新平衡因子过程： 更新的原则如下：

• 如果新节点插入到父节点的左侧，则父节点的平衡因子减一。
• 如果新节点插入到父节点的右侧，则父节点的平衡因子加一。

更新后，需要检查父节点的平衡因子是否发生变化，如果发生变化，则继续向上检查祖先节点的平衡因子，直到根节点或者到达一个平衡因子为 ±1 的节点为止。根据更新后节点的平衡因子情况，可以采取以下处理措施：

• 如果节点的平衡因子为 0，表示节点所在子树的高度没有变化，不会影响祖先节点的平衡因子，更新结束。
• 如果节点的平衡因子为 ±1，表示节点所在子树的高度变化（本来是0，现在变成 ±1，子树高度变了），会影响祖先节点的平衡因子，需要继续向上更新祖先节点的平衡因子。
• 如果节点的平衡因子为 ±2，表示节点所在子树违反了平衡规则，需要进行平衡调整操作（如旋转），然后更新结束。

4.1新节点插入当前节点的右子树的右子树——左旋转

左旋 (Left Rotation)

左旋的情况是当一个节点的右子树过高，需要进行左旋来降低右子树的高度，同时保持树的平衡。

情况：

1. 新节点插入到当前节点的右子树的右子树中，导致当前节点的平衡因子为 +2。
2. 在双旋的过程中，当左子树的平衡因子为 -1，右子树的平衡因子为 +1。

操作：

左旋是指将当前节点向左旋转，使得当前节点的右子树的左子树成为当前节点的右子树，同时将当前节点成为其右子树的左子树。

AVL2

4.2新节点插入当前节点的左子树的左子树——右旋转

右旋 (Right Rotation)

右旋的情况是当一个节点的左子树过高，需要进行右旋来降低左子树的高度，同时保持树的平衡。

情况：

1. 新节点插入到当前节点的左子树的左子树中，导致当前节点的平衡因子为 -2。
2. 在双旋的过程中，当左子树的平衡因子为 -1，右子树的平衡因子为 +1。

操作：

右旋是指将当前节点向右旋转，使得当前节点的左子树的右子树成为当前节点的左子树，同时将当前节点成为其左子树的右子树。

4.3新节点插入当前节点的左子树的右子树——左右双旋

当新节点插入当前节点的左子树的右子树时，会触发左右双旋操作（LR旋转）。这种情况发生在当前节点的左子树的右子树上插入了新节点，导致当前节点的平衡因子不平衡（可能为+2或-2），且当前节点的左子树的右子树的平衡因子为正值（+1）。为了恢复 AVL 树的平衡性，需要先对当前节点的左子树进行一次左旋操作，然后再对当前节点进行一次右旋操作。

左右双旋（LR旋转）

具体步骤如下：

1. 对当前节点的左子树进行一次左旋操作。
2. 对当前节点进行一次右旋操作。

示例：

假设当前节点为 A，新节点插入在 A 的左子树的右子树的情况下，左右双旋操作如下：

4.4新节点插入当前节点的右子树的左子树——右左双旋

右左旋（RL旋转）

右左旋操作发生在节点的右子树过深，导致平衡因子为 -2 且其右子节点的平衡因子为 +1 的情况下。具体步骤如下：

1. 对 A 的右子树进行一次左旋操作。
2. 再对 A 进行一次右旋操作。

示例：

4.5组装完整版Insert（）

5.中序方便过会测试

6.编写函数看是否满足要求

只要有一个节点的左子树与右子树的高度差距大于等于2，那么就不满足了 从这里也能看出要写一个求高度函数更方便

6.1求高度

这段代码实现了 AVL 树的高度计算和平衡性检查功能。 _Height 函数: 这个函数用于计算给定树的高度。递归地计算左右子树的高度，然后返回较大的子树高度加上 1。这个函数被用于计算整棵树的高度。 Height 函数: 这个函数是对外提供的接口，用于获取 AVL 树的高度。它调用 _Height 函数并传入根节点，返回整棵 AVL 树的高度。

6.2 平衡否

_IsBalance 函数: 这个函数用于检查 AVL 树的平衡性。它递归地检查树的每个节点，计算左右子树的高度并比较它们的差值，如果差值大于等于 2，则表示不平衡。此外，还检查每个节点的平衡因子是否正确，即右子树高度减去左子树高度等于节点的平衡因子。如果平衡因子异常，则表示树不平衡。 IsBalance 函数: 这个函数是对外提供的接口，用于检查整棵 AVL 树的平衡性。它调用 _IsBalance 函数并传入根节点，返回整棵 AVL 树是否平衡的结果。 这些函数的实现是 AVL 树的重要部分，用于确保 AVL 树保持平衡性和正确性。

7.测试

8.全部代码

8.1 AVLTree.h

8.2 test.cpp

今天就到这里啦！！下一次肯定是红黑树啦！！！