前言
前面我们介绍了STL中的关联式容器map/set/multimap/mutiset等，我们可以发现它们的底层都是按照二叉搜索树来实现的，但是二叉搜索树自身有一些缺陷，当往二叉搜索树中插入的元素有序或者接近有序二叉搜索树就会退化为单支，其检索的时间复杂度就会退化为O(n)。因此map、set等关联式容器的底层结构是对搜索二叉树进行平衡处理的平衡二叉搜索树。
本节我们就来了解平衡搜索二叉树AVL树的相关概念。
一、概念
普通的搜索二叉树一旦数据有序或者接近有序就会造成二叉搜索树退化为单支，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
**当向二叉搜索树中插入新结点后，如果能保证每个节点的左右子树高度之差不超过1（需要对树中结点进行调整）**即可降低树的高度，从而减少平均搜索长度。
一棵AVL树要具有以下性质：
- 该树如果是空树，那么它是AVL树；
- 它的左右子树是AVL树；
- 左右子树的高度差（命名为平衡因子）的绝对值不超过1（可以是1/0/-1）
上图的红色标识的是该结点的平衡因子（这里的平衡因子使用右子树的高度减左子树的高度计算的）。
如果一棵二叉搜索树是高度平衡的，那么他就是AVL树。
假设该树有n个结点，其高度应保持在O ( l o g 2 n ) O(log_2 n)O(log2n)，搜索时间复杂度为O(l o g 2 n log_2 nlog2n）。
二、AVL树结点的定义
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;//平衡因子 };
三、AVL树的插入
实际上，AVL树就是在二叉搜索树的基础上增加了平衡因子，因此AVL树的插入可以分为两步：
- 按照二叉搜索树的插入方式插入新结点
- 调整结点的平衡因子
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 > data) { cur = cur->_pleft; } else if (cur->_kv.first < data) { cur = cur->_pright; } else return false;//树中已经存在该元素，插入失败 } if (prev->_kv.first > data) { 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; } private: AVLnode<T>* _root; };
四、AVL树的旋转
1.右单旋的情况以及具体操作
抽象图
先看如下的抽象图：
图中a,b,c是高度为h的子树，红色数字是插入前该节点的平衡因子。
新增结点导致要向上更新平衡因子，如果父节点的平衡因子为-2，且当前结点的平衡因子为-1时，我们就要进行右单旋。
那么如何进行右单旋呢？旋转处理之后平衡因子又是如何更新的呢？
要由具体的解决方法推出抽象的解决方法，因此下面我们具体分析当h分别为0/1/2时，我们的解决方法：
h = 0
如图，当h = 0时，在a处新增节点，按照图中步骤使用右单旋对该子树进行调整，最后更新平衡因子即可。
h = 1
如图，当h = 1时，在a结点的左右子结点任意一个位置新增节点，按照图中步骤使用右单旋对该子树进行调整，最后更新平衡因子即可。
h = 2
如图，当h = 2时，在a子树的i/j/m/n等四个位置的任意一个位置新增节点，按照图中步骤使用右单旋对该子树进行调整，最后更新平衡因子即可。
总结：根据以上三种情况我们可以得出，新增节点向上调整平衡因子的过程中，如果出现父节点的平衡因子为-2，当前结点的平衡因子为-1的情况，就以父节点为轴进行右单旋，之后更新父节点和当前结点的平衡因子为0即可。
代码实现
//左单旋(父节点平衡因子为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.左单旋的情况以及具体操作
抽象图
图中a,b,c是高度为h的子树，红色数字是插入前该节点的平衡因子。
新增结点导致要向上更新平衡因子，如果父节点的平衡因子为2，且当前结点的平衡因子为1时，我们就要进行左单旋。
左单旋与右单旋的方法类似，没有特殊情况，因此这里只介绍当h = 0时的情况：
当h = 0时，在c位置新增结点
可以看出，当父节点为2且当前结点为1时，需要以父节点为轴进行左单旋，最后更新平衡因子。
代码实现
//右单旋(父节点平衡因子为-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; } } }
