平衡搜索二叉树（AVL树）

前言 二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。 一、AVL树的概念 一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树： 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）                  如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(log n)，搜索时间复杂度O(log n)。 二、AVL树的定义

AVL树节点的定义：

我们这里直接实现KV模型的AVL树，为了方便后续的操作，这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子（右子树高度-左子树高度）。除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，于是将新构造结点的平衡因子初始设置为0即可。

template<class K, class V> class AVLTreeNode { AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; pair<K, V> _kv; int _bf; // 平衡因子 AVLTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _bf(0) {} }; 三、AVL树的插入 AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为三步： 按照二叉搜索树的插入方法，找到待插入位置。找到待插入位置后，将待插入结点插入到树中。更新平衡因子，如果出现不平衡，则需要进行旋转。 因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照 二叉搜索树的插入规则： 待插入结点的key值比当前结点小就插入到该结点的左子树。待插入结点的key值比当前结点大就插入到该结点的右子树。待插入结点的key值与当前结点的key值相等就插入失败。 与二叉搜索树插入结点不同的是，AVL树插入结点后需要 更新树中结点的平衡因子 ，因为插入新结点后可能会影响树中某些结点的平衡因子。 pCur 插入后， pParent 的平衡因子一定需要调整，在插入之前， pParent 的平衡因子分为三种情况：-1 ， 0, 1, 分以下两种情况：

  1. 如果 pCur 插入到 pParent 的左侧，只需给 pParent 的平衡因子 -1 即可   2. 如果 pCur 插入到 pParent 的右侧，只需给 pParent 的平衡因子 +1 即可 此时： pParent 的平衡因子可能有三种情况： 0 ，正负 1 ， 正负 2   1. 如果 pParent 的平衡因子为 0 ，说明插入之前 pParent 的平衡因子为正负 1 ，插入后被调整成0 ，此时满足     AVL 树的性质，插入成功   2. 如果 pParent 的平衡因子为正负 1 ，说明插入前 pParent 的平衡因子一定为 0 ，插入后被更 新成正负1 ，此 时以 pParent 为根的树的高度增加，需要继续向上更新   3. 如果 pParent 的平衡因子为正负 2 ，则 pParent 的平衡因子违反平衡树的性质，需要对其进 行旋转处理 而在最坏情况下，我们更新平衡因子时会一路更新到根结点。例如下面这种情况： 说明一下： 由于我们插入结点后需要倒着往上进行平衡因子的更新，所以我们将AVL树结点的结构设置为了三叉链结构，这样我们就可以通过父指针找到其父结点，进而对其平衡因子进行更新。当然，我们也可以不用三叉链结构，可以在插入结点时将路径上的结点存储到一个栈当中，当我们更新平衡因子时也可以通过这个栈来更新祖先结点的平衡因子，但是相对较麻烦。 若是在更新平衡因子的过程当中，出现了平衡因子为-2/2的结点，这时我们需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种，在进行分类之前我们首先需要进行以下分析： 我们将插入结点称为cur，将其父结点称为parent，那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新，那么我们必定要执行以下逻辑： cur = parent; parent = parent->_parent; 这里我想说明的是： 当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。

理由如下： 若cur的平衡因子是0，那么cur一定是新增结点，而不是上一次更新平衡因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新。 而cur是新增结点的话，其父结点的平衡因子更新后一定是-1/0/1，而不可能是-2/2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：

其父结点是一个左右子树均为空的叶子结点，其平

衡因子是0，新增结点插入后其平衡因子更新为-1/1。 其父结点是一个左子树或右子树为空的结点，其平衡因子是-1/1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中较矮的一棵子树增高了，新增结点后其平衡因子更新为0。 综上所述，当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0  

根据此结论，我们可以将旋转处理分为以下四类：  

当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。 并且，在进行旋转处理后就无需继续往上更新平衡因子了，因为旋转后树的高度变为插入之前了，即树的高度没有发生变化，也就不会影响其父结点的平衡因子了。 插入函数代码： //插入函数 bool Insert(const pair<K, V>& kv) { if (_root == nullptr) //若AVL树为空树，则插入结点直接作为根结点 { _root = new Node(kv); return true; } //1、按照二叉搜索树的插入方法，找到待插入位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值 { //往该结点的左子树走 parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值 { //往该结点的右子树走 parent = cur; cur = cur->_right; } else //待插入结点的key值等于当前结点的key值 { //插入失败（不允许key值冗余） return false; } } //2、将待插入结点插入到树中 cur = new Node(kv); //根据所给值构造一个新结点 if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值 { //插入到parent的左边 parent->_left = cur; cur->_parent = parent; } else //新结点的key值大于parent的key值 { //插入到parent的右边 parent->_right = cur; cur->_parent = parent; } //3、更新平衡因子，如果出现不平衡，则需要进行旋转 while (cur != _root) //最坏一路更新到根结点 { if (cur == parent->_left) //parent的左子树增高 { parent->_bf--; //parent的平衡因子-- } else if (cur == parent->_right) //parent的右子树增高 { parent->_bf++; //parent的平衡因子++ } //判断是否更新结束或需要进行旋转 if (parent->_bf == 0) //更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致） { break; //parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子 } else if (parent->_bf == -1 || parent->_bf == 1) //需要继续往上更新平衡因子 { //parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子 cur = parent; parent = parent->_parent; } else if (parent->_bf == -2 || parent->_bf == 2) //需要进行旋转（此时parent树已经不平衡了） { if (parent->_bf == -2) { if (cur->_bf == -1) { RotateR(parent); //右单旋 } else //cur->_bf == 1 { RotateLR(parent); //左右双旋 } } else //parent->_bf == 2 { if (cur->_bf == -1) { RotateRL(parent); //右左双旋 } else //cur->_bf == 1 { RotateL(parent); //左单旋 } } break; //旋转后就一定平衡了，无需继续往上更新平衡因子(旋转后树高度变为插入之前了) } else { assert(false); //在插入前树的平衡因子就有问题 } } return true; //插入成功 } 四、AVL树的旋转 4.1、右单旋

新节点插入较高左子树的左侧---左左：

右单旋的步骤： 让subL的右子树作为parent的左子树。让parent作为subL的右子树。让subL作为整个子树的根。更新平衡因子。

右单旋后满足二叉搜索树的性质：

subL的右子树当中结点的值本身就比parent的值小，因此可以作为parent的左子树。parent及其右子树当中结点的值本身就比subL的值大，因此可以作为subL的右子树。 可以看到，经过右单旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以右单旋后无需继续往上更新平衡因子。 右单旋代码： void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) //右孩子可能为空 subLR->_parent = parent; Node* ppnode = parent->_parent; //记录父节点的父节点 subL->_right = parent; parent->_parent = subL; if (ppnode == nullptr) //如果父节点是根节点 { _root = subL; //改变根节点 _root->_parent = nullptr; } else //如果父节点不是根节点 { if (ppnode->_left == parent) //如果父节点是左孩子 { ppnode->_left = subL; } else //如果父节点是右孩子 { ppnode->_right = subL; } subL->_parent = ppnode; } parent->_bf = subL->_bf = 0; //最后更新平衡因子 } 4.2、左单旋 . 新节点插入较高右子树的右侧---右右 左单旋的步骤如下： 让subR的左子树作为parent的右子树。让parent作为subR的左子树。让subR作为整个子树的根。更新平衡因子。

左单旋后满足二叉搜索树的性质：

subR的左子树当中结点的值本身就比parent的值大，因此可以作为parent的右子树。parent及其左子树当中结点的值本身就比subR的值小，因此可以作为subR的左子树。 可以看到，经过左单旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以左单旋后无需继续往上更新平衡因子。 左单旋代码： //左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* parentParent = parent->_parent; //1、建立subR和parent之间的关系 parent->_parent = subR; subR->_left = parent; //2、建立parent和subRL之间的关系 parent->_right = subRL; if (subRL) subRL->_parent = parent; //3、建立parentParent和subR之间的关系 if (parentParent == nullptr) { _root = subR; subR->_parent = nullptr; //subR的_parent指向需改变 } else { if (parent == parentParent->_left) { parentParent->_left = subR; } else //parent == parentParent->_right { parentParent->_right = subR; } subR->_parent = parentParent; } //4、更新平衡因子 subR->_bf = parent->_bf = 0; } 4.3、左右双旋 新节点插入较高左子树的右侧---左右： 将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再 考虑平衡因子的更新。 左右双旋的步骤如下： 以subL为旋转点进行左单旋。以parent为旋转点进行右单旋。更新平衡因子。

左右双旋后满足二叉搜索树的性质：

左右双旋后，实际上就是让subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根

1、subLR的左子树当中的结点本身就比subL的值大，因此可以作为subL的右子树。 2、subLR的右子树当中的结点本身就比parent的值小，因此可以作为parent的左子树。 3、经过步骤1/2后，subL及其子树当中结点的值都就比subLR的值小，而parent及其子树当中结点的值都就比subLR的值大，因此它们可以分别作为subLR的左右子树

左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：

1、当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0。

2、当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0。 3、当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0。 可以看到，经过左右双旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以左右双旋后无需继续往上更新平衡因子。 左右双旋代码： //左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; //subLR不可能为nullptr，因为subL的平衡因子是1 //1、以subL为旋转点进行左单旋 RotateL(subL); //2、以parent为旋转点进行右单旋 RotateR(parent); //3、更新平衡因子 if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == -1) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false); //在旋转前树的平衡因子就有问题 } } 4.4、右左双旋 新节点插入较高右子树的左侧---右左： 右左双旋的步骤如下： 以subR为旋转点进行右单旋。以parent为旋转点进行左单旋。更新平衡因子。 右左双旋后满足二叉搜索树的性质：

右左双旋后，实际上就是让subRL的左子树和右子树，分别作为parent和subR的右子树和左子树，再让parent和subR分别作为subRL的左右子树，最后让subRL作为整个子树的根

1、subRL的左子树当中的结点本身就比parent的值大，因此可以作为parent的右子树。

2、subRL的右子树当中的结点本身就比subR的值小，因此可以作为subR的左子树

3、经过步骤1/2后，parent及其子树当中结点的值都就比subRL的值小，而subR及其子树当中结点的值都就比subRL的值大，因此它们可以分别作为subRL的左右子树

右左双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：和左右双旋情况一样，这里就不过多分析。

右左双旋代码：

//右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; //1、以subR为轴进行右单旋 RotateR(subR); //2、以parent为轴进行左单旋 RotateL(parent); //3、更新平衡因子 if (bf == 1) { subRL->_bf = 0; parent->_bf = -1; subR->_bf = 0; } else if (bf == -1) { subRL->_bf = 0; parent->_bf = 0; subR->_bf = 1; } else if (bf == 0) { subRL->_bf = 0; parent->_bf = 0; subR->_bf = 0; } else { assert(false); //在旋转前树的平衡因子就有问题 } } 五、AVL树的验证 AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步： 5.1、 验证其为二叉搜索树         如果中序遍历可得到一个有序的序列，就说明为二叉搜索树 //中序遍历 void Inorder() {     _Inorder(_root); } //中序遍历子函数 void _Inorder(Node* root) {     if (root == nullptr)         return;     _Inorder(root->_left);     cout << root->_kv.first << " ";     _Inorder(root->_right); } 5.2、 验证其为平衡树                  每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)         节点的平衡因子是否计算正确 //判断是否为AVL树 bool IsAVLTree() { int hight = 0; //输出型参数 return _IsBalanced(_root, hight); } //检测二叉树是否平衡 bool _IsBalanced(Node* root, int& hight) { if (root == nullptr) //空树是平衡二叉树 { hight = 0; //空树的高度为0 return true; } //先判断左子树 int leftHight = 0; if (_IsBalanced(root->_left, leftHight) == false) return false; //再判断右子树 int rightHight = 0; if (_IsBalanced(root->_right, rightHight) == false) return false; //检查该结点的平衡因子 if (rightHight - leftHight != root->_bf) { cout << "平衡因子设置异常：" << root->_kv.first << endl; } //把左右子树的高度中的较大值+1作为当前树的高度返回给上一层 hight = max(leftHight, rightHight) + 1; return abs(rightHight - leftHight) < 2; //平衡二叉树的条件 } 六、AVL树的性能

平衡性：AVL树保持了一种平衡性，对于任意节点，其左子树和右子树的高度差不超过1。这种平衡性保证了在最坏情况下，AVL树的插入、删除和查找操作的时间复杂度都是O(log n)。

插入和删除效率：由于AVL树的平衡性，插入和删除操作可能会导致树进行旋转操作，使得树重新达到平衡状态。虽然旋转操作会增加一定的开销，但是由于树的平衡性，插入和删除操作的时间复杂度仍然是O(log n)。

查找效率：由于AVL树是一种二叉搜索树，查找操作的时间复杂度也是O(log n)。这使得AVL树非常适合需要高效的查找操作的场景。

尽管AVL树具有良好的平衡性和较高的查找效率，但是由于需要维护平衡性，插入和删除操作的性能可能会受到一定的影响。在一些特定的插入、删除操作频繁的场景下，可能会考虑使用其他平衡树结构（如红黑树）来获得更好的性能表现。