3.右左双旋的情况以及具体操作
我们设定：结点值为30的结点是parent，结点值为90的结点是pR,结点值为60的结点是pRL（起名字后方便操作）
抽象图
右左双旋的抽象图，其中a/d是高度为h的子树，b/c是高度为h-1的子树
先以pR结点为轴进行右单旋，再以parent结点为轴进行左单旋，最后更新平衡因子即可。
h = 0
h = 1
如果在b处新增结点（在60的左子树新增结点）
旋转后平衡因子的更新如下：
30结点的平衡因子为0；
60结点的平衡因子为0；
90结点的平衡因子为-1.
如果在c处新增结点（在60的右子树新增结点）
旋转后平衡因子的更新如下：
30结点的平衡因子为0；
60结点的平衡因子为0；
90结点的平衡因子为-1.
h = 2
在60的左右子树新增节点导致的旋转后的平衡因子的更新情况与h = 1时是一致的，因此只简单介绍在e处新增的情况。
3.左右双旋的情况以及具体操作
我们设定：结点值为90的结点是parent，结点值为30的结点是pL,结点值为60的结点是pLR（起名字后方便操作）
抽象图
先以pL结点为轴进行左单旋，再以parent结点为轴进行右单旋，最后更新平衡因子即可。
如果新增的节点就是60，那么旋转后的平衡因子更新如下：
30结点/60结点/90结点的平衡因子都为0；
如果新增的节点在60结点的左子树，那么旋转后的平衡因子更新如下：
30结点的平衡因子为1；
60结点的平衡因子为0；
90结点的平衡因子为0。
如果新增的节点在60结点的右子树，那么旋转后的平衡因子更新如下：
30结点的平衡因子为0；
60结点的平衡因子为0；
90结点的平衡因子为-1。
左右双旋与右左双旋类似，可以参考理解，这里就不多赘述了。
5.总结
假如以parent为根的子树不平衡，即parent的平衡因子为2/-2，有以下几种情况：
- parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根节点为pR
- 当pR的平衡因子为1时，执行左单旋；
- 当pR的平衡因子为-1时，执行右左双旋。
- parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根节点为pL
- 当pL的平衡因子为-1，执行右单旋；
- 当pL的平衡因子为1，执行左右双旋。
旋转结束后，原parent为根的子树高度已平衡，不需要再向上更新。
6.完整实现代码
namespace Jinger { template<class K,class V> struct AVLnode//三叉链 { pair<K, V> _kv; AVLnode(const pair<K,V>& kv) :_kv(kv) , _bf(0) , _pleft(nullptr) , _pright(nullptr) , _pparent(nullptr) {} AVLnode<K, V>* _pleft;//左孩子 AVLnode<K, V>* _pright;//右孩子 AVLnode<K, V>* _pparent;//双亲结点 int _bf;//平衡因子 }; template<class K, class V> struct AVLTree { typedef AVLnode<K, V> node; AVLTree() :_root(nullptr) {} //左单旋(父节点平衡因子为2，右孩子平衡因子为1） void RotateL(node* parent) { node* SubR = parent->_pright; node* SubRL = SubR->_pleft; node* Grandpa = parent->_pparent;//祖父 parent->_pright = SubRL; if (SubRL) { SubRL->_pparent = parent; } SubR->_pleft = parent; parent->_pparent = SubR; SubR->_pparent = Grandpa; //更新祖父的孩子结点 if (Grandpa == nullptr)//pParent此时是根节点 { _root = SubR;//更新cur为根节点 _root ->_pparent = nullptr; } else { if (parent == Grandpa->_pleft) { Grandpa->_pleft = SubR; } else { Grandpa->_pright = SubR; } } } //右单旋(父节点平衡因子为-2，左孩子平衡因子为-1） void RotateR(node* parent) { node* SubL = parent->_pleft; node* SubLR = SubL->_pright; node* Grandpa = parent->_pparent;//祖父 parent->_pparent = SubL; SubL->_pright = parent; parent->_pleft = SubLR; if (SubLR) SubLR->_pparent = parent; SubL->_pparent = Grandpa; //更新祖父的孩子结点 if (Grandpa == nullptr)//pParent此时是根节点 { _root = SubL; SubL->_pparent = nullptr; } else { if (parent == Grandpa->_pleft) { Grandpa->_pleft = SubL; } else { Grandpa->_pright = SubL; } } } bool insert(const pair<K,V>& kv) { //1.按照二叉搜索树的规则将节点插入到AVL树中 node* newnode = new node(kv); node* cur = _root; if (_root == nullptr)//如果该树为空树，直接插入新节点，此时新节点是该树的根节点 { _root = newnode; return true; } node* prev = nullptr; while (cur) { prev = cur; if (cur->_kv.first > kv.first) { cur = cur->_pleft; } else if (cur->_kv.first < kv.first) { cur = cur->_pright; } else return false;//树中已经存在该元素，插入失败 } if (prev->_kv.first > kv.first) { prev->_pleft = newnode; newnode->_pparent = prev; } else { prev->_pright = newnode; newnode->_pparent = prev; } node* pParent = prev; cur =newnode; //2.对结点的平衡因子进行更新，并检测新插入的结点是否破坏了AVL树的平衡性 //调节平衡因子，在插入新结点前pparent的平衡因子有以下三种情况：-1, 0, 1 //如果cur插在pparent的左边，给pparent的结点的平衡因子-1； //如果cur插在pparent的右边，给pparent的结点的平衡因子+1； //此时，pparent的平衡因子有以下三种情况，0，±1，±2 //pparent平衡因子为0，说明新插入结点不影响该子树的高度，满足AVL树的性质，不再进行调整 //pparent平衡因子为±1，说明插入前pparent的平衡因子为0，此时以pparent为根的子树的高度加1，需要继续向上更新平衡因子 //pparent平衡因子为±2，说明插入前pparent的平衡因子为±1，此时pparent的平衡因子违反了AVL树的性质需要进行旋转操作 while (pParent)//当pParent为空时，pParent就是根节点的父节点，就不需要再进行调整了 { //更新父节点的平衡因子 if (cur == pParent->_pleft) { pParent->_bf--; } else if (cur == pParent->_pright) { pParent->_bf++; } //检测更新后的平衡因子 if (0 == pParent->_bf)//该子树的高度没变化，不用调整 { break; } else if (1 == pParent->_bf || -1 == pParent->_bf)//该子树的高度增加了1，因此要继续向上调整平衡因子 { cur = pParent; pParent = pParent->_pparent; } //3.破坏了AVL树的平衡性，我们就要对以pparent为根的子树就地旋转处理 //旋转的目的： //1)让这棵子树的左右高度差不超过1 //2）旋转过程中保持它是搜索树 //3）更新旋转后的平衡因子 //4）让这棵树的高度与插入前保持一致（不会继续影响上层，不用继续向上调整） else if (2 == pParent->_bf || -2 == pParent->_bf) { //右单旋 //我的平衡因子为-1；父节点的平衡因子为-2. if (-2 == pParent->_bf && -1 == cur->_bf) { RotateR(pParent); //更新平衡因子 cur->_bf = 0; pParent->_bf = 0; } //左单旋 else if (2 == pParent->_bf && 1 == cur->_bf) { RotateL(pParent); //更新平衡因子 cur->_bf = 0; pParent->_bf = 0; } //左右双旋 else if (-2 == pParent->_bf && 1 == cur->_bf) { node* SubR = cur->_pright; RotateL(cur); RotateR(pParent); //更新平衡因子 //新增结点就是SubR if (SubR ->_bf == 0) { cur->_bf = 0; pParent->_bf = 0; } //新增结点在SubR结点的左子树 else if (SubR->_bf == -1) { SubR->_bf = cur->_bf = 0; pParent->_bf = 1; } //新增结点在SubR结点的右子树 else if (SubR->_bf == 1) { SubR->_bf = pParent->_bf = 0; cur->_bf = -1; } else { assert(false); } } //右左双旋 else if (2 == pParent->_bf && -1 == cur->_bf) { node* SubL = cur->_pleft; RotateR(cur); RotateL(pParent); //更新平衡因子 //新增结点就是SubL if (SubL->_bf == 0) { cur->_bf = 0; pParent->_bf = 0; } //新增结点在SubL结点的左子树 else if (SubL ->_bf == -1) { SubL->_bf = pParent->_bf = 0; cur->_bf = 1; } //新增结点在SubL结点的右子树 else if (SubL->_bf == 1) { SubL->_bf = cur->_bf = 0; pParent->_bf = -1; } else { assert(false); } } return true; } else//如果以上的程序哪里出现问题就会直接报错 { assert(false); } } return true; } //获取根节点 node* Getroot() { return _root; } private: node* _root; }; }
7.验证
概念
AVL树是在搜索二叉树的基础上加入了平衡因子的限制，因此要验证AVL树可以分为以下两个步骤：
- 验证其是否为搜索二叉树
- 验证其是否为平衡树（平衡因子）
- 每个结点子树高度差的绝对值不超过1
- 判断结点中的平衡因子计算是否正确
- 验证用例：
一般情况（仅进行单旋）
{16, 3, 7, 11, 9, 26, 18, 14, 15}
特殊情况（进行双旋）
{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}
主程序代码
下面是测试用的主程序代码，大家可以用它来检验AVL树实现代码的正确性：
#define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; #include<vector> #include<algorithm> #include<assert.h> #include"AVL.h" int _Height(Jinger::AVLnode<int,int>* pRoot)//计算树的最大高度 { if (pRoot == nullptr) return 0; return 1 + max(_Height(pRoot->_pleft), _Height(pRoot->_pright)); } bool _IsBalanceTree(Jinger::AVLnode<int,int>* pRoot) { // 空树也是AVL树 if (nullptr == pRoot) return true; // 计算pRoot节点的平衡因子：即pRoot左右子树的高度差 int leftHeight = _Height(pRoot->_pleft); int rightHeight = _Height(pRoot->_pright); int diff = rightHeight - leftHeight; // 如果计算出的平衡因子与pRoot的平衡因子不相等，或者pRoot平衡因子的绝对值超过1，则一定不是AVL树 if (diff != pRoot->_bf || (diff > 1 || diff < -1)) return false; // pRoot的左和右如果都是AVL树，则该树一定是AVL树 return _IsBalanceTree(pRoot->_pleft) && _IsBalanceTree(pRoot ->_pright); } int main() { Jinger::AVLTree<int,int> tree; vector<int> v{ 16, 3, 7, 11, 9, 26, 18, 14, 15}; //vector<int> v{ 4, 2, 6, 1, 3, 5, 15, 7, 16, 14}; for (auto it : v) { cout << it << " "; tree.insert(make_pair(it,it)); } int a = 0; bool ret = _IsBalanceTree(tree.Getroot()); if (ret == 0) cout << "该树不是AVL树" << endl; else cout << "该树是AVL树" << endl; return 0; }
8.性能
AVL树是一棵绝对平衡的搜索二叉树，它要求每个结点的左右子树的高度差的绝对值不超过1，这样可以保证查询时的时间复杂度（l o g 2 ( N ) log_2(N)log2(N))。但是如果对AVL树做一些结构修改的操作，它的性能就会比较低下，例如，插入元素时要维护其绝对平衡的性质，旋转的次数会比较多。其中删除的效果最差，有可能让旋转一直持续到根节点。
因此，如果需要一种查询高效且有序的数据结构，并且数据结构的个数为静态的（不会发生改变），可以考虑使用AVL树，但是如果该结构需要经常被修改AVL树就不太适合了。
总结
以上就是今天要讲的内容，本文介绍了C++中的AVL树的相关概念。本文作者目前也是正在学习C++相关的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出，也欢迎大家在评论区提问、交流。
最后，如果本篇文章对你有所启发的话，希望可以多多支持作者，谢谢大家！
