前言
前言
前面我们讲了C语言的基础知识，也了解了一些初阶数据结构，并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载，引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ，也了解了C++中的模版，以及学习了几个STL的结构也相信大家都掌握的不错，接下来博主将会带领大家继续学习有关C++比较重要的知识点—— AVL 树（自平衡二叉搜索树） 。下面话不多说坐稳扶好咱们要开车了😍
一、AVL树的概念
AVL树是一种自平衡的二叉搜索树，它在插入或删除节点时通过旋转操作来保持树的平衡。AVL树的名称来自发明者 Adelson-Velsky 和 Landis 的姓氏的首字母。
在AVL树中，每个节点都有一个平衡因子（balance factor），表示其左子树高度和右子树高度之间的差值。平衡因子可以是-1、0或1，如果平衡因子的绝对值超过1，则该节点被认为是不平衡的。
⭕AVL树维护以下性质：
- 树的每个节点的平衡因子必须在-1、0和1之间。
- 所有左子树的高度与右子树的高度之差的绝对值不超过1。
- 如果它有n个结点，其高度可保持在 O(log_2 n)，搜索时间复杂度O(log2n)
当向AVL树中插入或删除节点时，可能会破坏树的平衡。为了恢复平衡，AVL树使用四种旋转操作：左旋、右旋、左右旋和右左旋。通过这些旋转操作，AVL树可以在插入或删除操作后保持平衡，从而提供较为稳定和高效的搜索、插入和删除操作。
由于AVL树的自平衡特性，它适用于需要频繁插入和删除操作的场景，尤其是对于需要快速搜索和有序遍历的数据集合。如果一棵二叉搜索树是高度平衡的，它就是AVL树。
二、AVL树节点的定义
AVL树的节点定义包括以下几个属性：
- 值：每个节点存储的值，可以是任意类型，通常是一个关键字或数据。
- 左子节点指针：指向当前节点的左子节点的指针。左子节点的值应该小于或等于当前节点的值。
- 右子节点指针：指向当前节点的右子节点的指针。右子节点的值应该大于当前节点的值。
- 父节点指针：指向当前节点的父节点的指针。根节点的父节点指针为空。
- 平衡因子：表示当前节点的左子树高度和右子树高度之差。平衡因子可以为-1、0或1。
下面是一个示例代码来定义一个AVL树的节点结构：
template<class K, class V> struct AVLTreeNode { AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; pair<K, V> _kv; int _bf; // balance factor AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {} };
三、AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
下面是AVL树的插入的基本算法：
- 如果AVL树为空，将新节点作为根节点插入，并更新其高度和平衡因子。
- 如果插入的值小于当前节点的值，则将其插入到当前节点的左子树中。如果左子节点为空，直接插入；否则，递归执行插入操作。
- 如果插入的值大于当前节点的值，则将其插入到当前节点的右子树中。如果右子节点为空，直接插入；否则，递归执行插入操作。
- 在递归返回的过程中，更新每个节点的高度和平衡因子，然后检查平衡因子是否超过了范围。
如果发现平衡因子超出范围，进行旋转操作来修复平衡。
下面是一个基于C++实现的AVL树插入算法的伪代码：
bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { // 如果根节点为空，创建新节点作为根节点，并返回插入成功 _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { // 当前节点的键值小于插入节点的键值，继续向右子树查找 parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { // 当前节点的键值大于插入节点的键值，继续向左子树查找 parent = cur; cur = cur->_left; } else { // 当前节点的键值等于插入节点的键值，插入失败（不允许键值重复） return false; } } // 创建新节点并插入到树中 cur = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; // 更新平衡因子 while (parent) { if (cur == parent->_right) { parent->_bf++; // 右子树增加一个节点，平衡因子加1 } else { parent->_bf--; // 左子树增加一个节点，平衡因子减1 } if (parent->_bf == 1 || parent->_bf == -1) { // 平衡因子为1或-1，说明子树高度增加，继续更新父节点的平衡因子 parent = parent->_parent; cur = cur->_parent; } else if (parent->_bf == 0) { // 平衡因子为0，说明子树高度没有变化，不需要进行旋转操作，结束循环 break; } else if (parent->_bf == 2 || parent->_bf == -2) { // 平衡因子为2或-2，需要进行旋转处理来恢复平衡 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); // 左旋 } else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); // 右旋 } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); // 先左旋再右旋 } else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); // 先右旋再左旋 } else { assert(false); // 不应该出现的情况 } break; } else { assert(false); // 不应该出现的情况 } } return true; }
⭕代码解释：
- 首先检查根节点是否为空，在空树中直接创建新节点作为根节点。
- 如果不是空树，则通过循环在适当的位置找到插入节点应该放置的父节点。
- 在插入节点时，根据父节点的键值与插入节点的键值的比较结果，确定插入节点是父节点的左子节点还是右子节点。
- 更新插入节点的父指针，并更新父节点及其祖先节点的平衡因子。
- 根据平衡因子的变化情况，决定是否需要进行旋转操作来调整树的平衡。
- 旋转操作分为左旋、右旋、先左旋再右旋和先右旋再左旋四种情况，具体根据平衡因子的值来确定。
四、AVL树的旋转（重点）
1. 右单旋（新节点插入较高左子树的左侧）
- 右单旋是AVL树的一种旋转操作，用于解决插入节点位于较高左子树的左侧的情况。
下面是右单旋的具体实现代码：
void RotateR(Node* parent) { Node* subL = parent->_left; // 获取父节点的左子节点 Node* subLR = subL->_right; // 获取左子节点的右子节点 Node* ppnode = parent->_parent; // 获取父节点的父节点 parent->_left = subLR; // 将左子节点的右子节点作为父节点的左子节点 if (subLR) subLR->_parent = parent; // 更新左子节点的右子节点的父指针 subL->_right = parent; // 将父节点作为左子节点的右子节点 parent->_parent = subL; // 更新父节点的父指针 if (parent == _root) { _root = subL; // 如果原父节点是根节点，更新根节点 _root->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; // 如果原父节点是其父节点的左子节点，更新父节点的左子节点 } else { ppnode->_right = subL; // 如果原父节点是其父节点的右子节点，更新父节点的右子节点 } subL->_parent = ppnode; // 更新左子节点的父指针 } subL->_bf = parent->_bf = 0; // 更新平衡因子 }
⭕具体而言，右单旋的操作步骤如下：
- 获取当前节点的左子节点，并将其保存在变量
subL中。 - 获取左子节点的右子节点，并将其保存在变量
subLR中。 - 获取当前节点的父节点，并将其保存在变量
ppnode中。 - 将左子节点的右子节点作为当前节点的左子节点。
- 如果左子节点的右子节点存在，则将其父指针更新为当前节点。
- 将当前节点作为左子节点的右子节点。
- 更新当前节点的父指针为左子节点。
- 如果当前节点是根节点，则更新根节点为左子节点，并将根节点的父指针置为空。
- 如果当前节点不是根节点，则根据其在父节点的位置，更新父节点的相应子节点为左子节点，并将左子节点的父指针更新为父节点。
- 将左子节点和当前节点的平衡因子都设置为0，表示树已经平衡。
右单旋操作通过对节点间的指针进行调整，重新平衡了AVL树的结构。这样做的目的是保持AVL树的平衡性，从而提高树的查询和插入等操作的效率。
2. 左单旋（新节点插入较高右子树的右侧）
- 左单旋是AVL树的一种旋转操作，用于解决插入节点位于较高右子树的右侧的情况。
下面是左单旋的具体实现代码：
void RotateL(Node* parent) { // 保存父节点的右子节点 Node* subR = parent->_right; // 保存右子节点的左子节点 Node* subRL = subR->_left; // 保存父节点的父节点 Node* ppnode = parent->_parent; // 将右子节点的左子节点作为父节点的右子节点 parent->_right = subRL; if (subRL) subRL->_parent = parent; // 将父节点作为右子节点的左子节点 subR->_left = parent; parent->_parent = subR; // 判断原父节点是否为根节点 if (ppnode == nullptr) { // 更新根节点为右子节点 _root = subR; // 将新根节点的父指针置为空 _root->_parent = nullptr; } else { // 判断原父节点是其父节点的左子节点还是右子节点 if (ppnode->_left == parent) { // 更新父节点的左子节点为右子节点 ppnode->_left = subR; } else { // 更新父节点的右子节点为右子节点 ppnode->_right = subR; } // 更新右子节点的父指针为父节点的父节点 subR->_parent = ppnode; } // 将父节点和右子节点的平衡因子都设置为0，表示树已经平衡 parent->_bf = subR->_bf = 0; }
⭕具体而言，左单旋的操作步骤如下：
- 保存了需要进行旋转操作的父节点、父节点的右子节点和右子节点的左子节点。
- 更新父节点的右子节点为右子节点的左子节点，并将右子节点的左子节点的父指针指向父节点。
- 将父节点的父指针指向右子节点，并将右子节点的左子节点指向父节点。
- 判断原父节点是否为根节点，若是，更新根节点为右子节点，并将新根节点的父指针置为空；若不是，根据父节点在其父节点的位置，分别更新其父节点的左子节点或右子节点为右子节点，并将右子节点的父指针指向父节点的父节点。
- 最后，将父节点和右子节点的平衡因子都设置为0，表示树已经平衡。
3. 先左单旋再右单旋（新节点插入较高左子树的右侧）
将双旋变成单旋后再旋转，即：先对30这个节点进行左单旋，然后再对90这个节点进行右单旋，旋转完成后再考虑平衡因子的更新。
下面是先左单旋再右单旋的具体实现代码：
void RotateLR(Node* parent) { // 获取节点C的左子节点A和节点A的右子节点D Node* subL = parent->_left; Node* subLR = subL->_right; // 获取节点D的平衡因子，以便后续调整平衡因子时使用 int bf = subLR->_bf; // 对节点A进行左单旋，注意此时节点C的左子节点为节点D，节点D的右子节点为节点A RotateL(parent->_left); // 对节点C进行右单旋，此时节点D成为新的子树头节点，节点C成为节点D的右子节点 RotateR(parent); // 调整平衡因子 if (bf == 1) // 如果节点D的平衡因子为1，说明节点D的左子树比右子树高 { parent->_bf = 0; // 节点C的平衡因子变为0 subLR->_bf = 0; // 节点D的平衡因子变为0 subL->_bf = -1; // 节点A的平衡因子变为-1，因为它的右子树高度比左子树高度大1 } else if (bf == -1) // 如果节点D的平衡因子为-1，说明节点D的右子树比左子树高 { parent->_bf = 1; // 节点C的平衡因子变为1 subLR->_bf = 0; // 节点D的平衡因子变为0 subL->_bf = 0; // 节点A的平衡因子变为0，因为它的左右子树高度相等 } else if (bf == 0) // 如果节点D的平衡因子为0，说明节点D的左右子树高度相等 { parent->_bf = 0; // 节点C的平衡因子变为0 subLR->_bf = 0; // 节点D的平衡因子变为0 subL->_bf = 0; // 节点A的平衡因子变为0，因为它的左右子树高度相等 } else // 如果节点D的平衡因子不是1、-1或者0，则说明AVL树已经失去了平衡，这是一个不合法的状态，应该立即报错退出程序。 { assert(false); } }
⭕具体而言，先左单旋再右单旋的操作步骤如下：
- 首先获取节点C的左子节点A（
subL）和节点A的右子节点D（subLR）； - 然后对节点A进行左单旋（
RotateL），此时节点C的左子节点应为节点D，节点D的右子节点应为节点A；
- 最后对节点C进行右单旋（
RotateR），此时节点D成为新的子树头节点，节点C成为节点D的右子节点。
最后一部分使用了if语句判断旋转后各个节点的平衡因子，并进行相应的调整，以便使AVL树保持平衡。
- 如果节点D的平衡因子为1，说明节点D的左子树比右子树高，需要进行右旋操作，这一次旋转中节点C和节点A都向右移动了一位，而节点D的平衡因子变为0，节点A和节点C的平衡因子都变为-1；
- 如果节点D的平衡因子为-1，说明节点D的右子树比左子树高，需要进行左旋操作，这一次旋转中节点C和节点A都向左移动了一位，而节点D的平衡因子变为0，节点A和节点C的平衡因子都变为1；
- 如果节点D的平衡因子为0，说明节点D的左右子树高度相等，不需要进行旋转操作，各个节点的平衡因子均设置为0；
- 如果节点D的平衡因子不是1、-1或者0，则说明AVL树已经失去了平衡，这是一个不合法的状态，应该立即报错退出程序。
- 经过这两次旋转后，AVL树重新保持了平衡性和有序性。
4. 先右单旋再左单旋（新节点插入较高右子树的左侧）
将双旋变成单旋后再旋转，即：先对90这个节点进行右单旋，然后再对30这个节点进行左单旋，旋转完成后再考虑平衡因子的更新。
下面是先右单旋再左单旋的具体实现代码：
void RotateRL(Node* parent) { // 获取节点C的右子节点B和节点B的左子节点E Node* subR = parent->_right; Node* subRL = subR->_left; // 获取节点E的平衡因子，以便后续调整平衡因子时使用 int bf = subRL->_bf; // 对节点B进行右单旋，注意此时节点C的右子节点为节点E，节点E的左子节点为节点B RotateR(parent->_right); // 对节点C进行左单旋，此时节点E成为新的子树头节点，节点C成为节点E的左子节点 RotateL(parent); // 调整平衡因子 if (bf == 1) // 如果节点E的平衡因子为1，说明节点E的左子树比右子树高 { parent->_bf = -1; // 节点C的平衡因子变为-1 subRL->_bf = 0; // 节点E的平衡因子变为0 subR->_bf = 0; // 节点B的平衡因子变为0，因为它的左右子树高度相等 } else if (bf == -1) // 如果节点E的平衡因子为-1，说明节点E的右子树比左子树高 { parent->_bf = 0; // 节点C的平衡因子变为0 subRL->_bf = 0; // 节点E的平衡因子变为0 subR->_bf = 1; // 节点B的平衡因子变为1，因为它的右子树高度比左子树高度大1 } else if (bf == 0) // 如果节点E的平衡因子为0，说明节点E的左右子树高度相等 { parent->_bf = 0; // 节点C的平衡因子变为0 subRL->_bf = 0; // 节点E的平衡因子变为0 subR->_bf = 0; // 节点B的平衡因子变为0，因为它的左右子树高度相等 } else // 如果节点E的平衡因子不是1、-1或者0，则说明AVL树已经失去了平衡，这是一个不合法的状态，应该立即报错退出程序。 { assert(false); } }
具体过程跟先左单旋再右单旋的过程一样，只不过是顺序有所不一样，这里就不多赘述了。
五、AVL树的删除（了解）
AVL树节点的删除是一个相对复杂的操作，需要考虑多种情况来保持树的平衡性，下面是对它的步骤简单的介绍：
- 首先，按照二叉搜索树的规则找到需要删除的节点。如果目标节点不存在，则删除操作结束。
- 如果删除的节点是叶子节点（没有子节点），可以直接删除它。此时，只需将其父节点指向它的指针置为空即可。
- 如果删除的节点有一个子节点，可以用子节点替代删除的节点。此时，只需将删除节点的父节点指向删除节点的子节点，并删除删除节点。
- 如果删除的节点有两个子节点，需要选择一个合适的替代节点来代替删除的节点。一般可以选择删除节点的中序遍历前驱或后继节点作为替代节点。
- 选择中序遍历的前驱节点作为替代节点的一种常见策略是：在删除节点的左子树上找到最大的节点，它将成为替代节点。如果选择后继节点作为替代节点，则在删除节点的右子树上找到最小的节点。
- 将选择的替代节点的值复制到删除的节点上，并删除替代节点。这样相当于删除了目标节点，但保持了二叉搜索树的结构。
- 此时可能导致树失去平衡，需要进行平衡调整。从替代节点的父节点开始，向上遍历到根节点，在每个遍历的节点上根据需要进行左旋、右旋或双旋转等操作。
- 在每个遍历节点上，需要更新其高度和平衡因子。如果删除节点后，遍历节点的平衡因子绝对值大于1，则需要进行旋转操作来恢复平衡。
- 最后，验证树是否仍然满足AVL树的平衡性和二叉搜索树的性质。可以从根节点开始递归地检查每个节点的平衡因子是否在[-1, 1]的范围内，且左子树的所有节点值小于节点值，右子树的所有节点值大于节点值。
🚨🚨注意：AVL树的节点删除可能触发多次旋转以保持树的平衡，这可能导致性能开销较大。因此，在实际应用中，可以考虑使用其他平衡二叉搜索树的变种，如红黑树，它在插入和删除操作上可能更加高效。后面博主也会对红黑树进行详细的介绍。
六、AVL树的性能
1.查找操作：AVL树是一种二叉搜索树，查找操作的平均时间复杂度为O(l o g n log nlogn)，其中n是树中节点的数量。由于AVL树保持了平衡性，树的高度较低，因此在大多数情况下，查找操作非常高效。
2.插入和删除操作：由于插入和删除操作可能引起树的不平衡，需要进行旋转操作来恢复平衡。这些旋转操作的时间复杂度为O(1 11)或O(l o g n log nlogn)，但由于旋转操作只在沿着路径上最多影响O(l o g n log nlogn)个节点，所以插入和删除操作的平均时间复杂度仍然是O(l o g n log nlogn)。
3.空间复杂度：AVL树与普通二叉搜索树相比，需要额外存储平衡因子来维护树的平衡性。平衡因子通常使用一个额外的字节来表示，因此额外的空间消耗也是O(n nn)。
4.平衡维护开销：当进行插入和删除操作时，AVL树需要保持树的平衡性，这可能导致一系列旋转操作。这些旋转操作的开销取决于树的深度和失衡点的位置。在最坏情况下，进行插入和删除操作时可能需要进行O(l o g n log nlogn)次旋转操作，因此平衡维护的开销相对较高。
附：详细的AVL模拟代码
template<class K, class V> struct AVLTreeNode { AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; pair<K, V> _kv; int _bf; // balance factor AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {} }; template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; // 更新平衡因子 while (parent) { if (cur == parent->_right) { parent->_bf++; } else { parent->_bf--; } if (parent->_bf == 1 || parent->_bf == -1) { // 继续更新 parent = parent->_parent; cur = cur->_parent; } else if (parent->_bf == 0) { break; } else if (parent->_bf == 2 || parent->_bf == -2) { // 需要旋转处理 -- 1、让这颗子树平衡 2、降低这颗子树的高度 if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } else { assert(false); } break; } else { assert(false); } } return true; } void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance() { return _IsBalance(_root); } int Height() { return _Height(_root); } private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } int _Height(Node* root) { if (root == NULL) return 0; int leftH = _Height(root->_left); int rightH = _Height(root->_right); return leftH > rightH ? leftH + 1 : rightH + 1; } bool _IsBalance(Node* root) { if (root == nullptr) return true; int leftH = _Height(root->_left); int rightH = _Height(root->_right); if (rightH - leftH != root->_bf) { cout << root->_kv.first << "节点平衡因子异常" << endl; return false; } return abs(leftH - rightH) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppnode = parent->_parent; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; parent->_parent = subR; if (ppnode == nullptr) { _root = subR; _root->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } parent->_bf = subR->_bf = 0; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppnode = parent->_parent; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (parent == _root) { _root = subL; _root->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } subL->_bf = parent->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); if (bf == 1) { parent->_bf = 0; subLR->_bf = 0; subL->_bf = -1; } else if (bf == -1) { parent->_bf = 1; subLR->_bf = 0; subL->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subLR->_bf = 0; subL->_bf = 0; } else { assert(false); } } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 1) { parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } else if (bf == 0) { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 0; } else { assert(false); } } Node* _root = nullptr; };
温馨提示
感谢您对博主文章的关注与支持！另外，我计划在未来的更新中持续探讨与本文相关的内容，会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新，不要错过任何精彩内容！
再次感谢您的支持和关注。期待与您建立更紧密的互动，共同探索C++、算法和编程的奥秘。祝您生活愉快，排便顺畅！
