C++——AVL平衡树
我们之前已经讲解过了二叉搜索树了。知道它的基本特性后，这次，我们来认识一下AVL平衡树。
在此之前，我们先来想想目前为止，我们可以通过哪些方式来寻找一个数？（有些我们还没有学，大概率后面会更新，包括B树（如果我有时间学到的话，可作为拓展补充学习））
1.暴力搜索（pass掉，时间复杂度太大了）
2.二分查找：（但是有个问题：要求有序，而且伴随着插入删除，它的维护成本比较大）
3.二叉搜索树：（因为有些极端情况下会变成类似链表结构，也会导致它的效率极低，这也是为什么会出现平衡树的原因之一）
4.平衡树（包括AVL平衡树、红黑树）
5.多叉平衡树（B树系列）
6.哈希表
那么，我们现在就来了解一下关于本次的相关内容——AVL平衡树。
了解为什么出现AVL？
我们可以用下面的图来就可以明白：
我们可以看到，当作为极端情况的时候：这是不是就相当于类似链表的结构了，这也就相当于从有序的二叉搜索树退化为单支树了，而且查找元素相当于在顺序表中搜索元素了，效率大大降低。因此为了解决这种极端问题， 俄国的两位数学家发明了这么一种方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(log_2 n)$，搜索时间复杂度O($log_2 n$)
这么记录它的平衡因子呢？看下图：
一般都是按照：
平衡因子=右子树的高度-左子树的高度
现在，我们来计算一下时间复杂度：
满二叉树 2^h-1=N
AVL树 2^h-x=N
因为高度差的绝对值不超过1，所以：
x的范围是：[1,2^(h-1)-1]
那么2^h-1=N, 两边都除以2---->2^(h-1)=(N-1)/2
因此算得它们的时间复杂度都约等于logN。
那么，可能有人会有疑问：为什么它的高度的绝对值是不超过1呢？
事实上，最佳的平衡条件是每个节点左右子树有着相同的高度，但是，现实很残酷，这会对树的要求太苛刻了，现实我们生活中，很难能够保持插入新元素后，仍保持它们的高度保持平衡的条件，因此，通常会将它的条件退一步：即高度差绝对值不为1.
插入的问题：
现在我们来分析一下它插入过程中的几种情况：
ps：我们的平衡因子主要以这样的运算规则：
平衡因子=右子树-左子树；
上图说到平衡因子==2/-2时需要旋转的情况：
这里根据它的位置分为左旋转与右旋转：
左单旋：
（下面动图来自于网上浏览器）
上面是具体的数，那么当我们化为抽象的，看作一个整体的话是不是也是这样的一个规律呢？现在我们就来具体看看：
我们可以看到：它是一样可以适用的。
可能第一次看到上面的组合有点懵，确实这个是比较抽象的，我们我们不妨去画出具体的图来理解它：
像上面的话，你可以想想，a和b是三种情况都是可以的，并且都是不影响它们之间的。而c的话只能是z情况那种。如果它可以是x和y其中一种的话：就会出现平衡因子是3的情况了。
因此就得出了：插入之前的组合：3*3*1
插入情况是有4种的：两个都有左子树与右子树，一共是4.
所以一共的组合是：3*3*1*4=36种。
所以说这些情况组合是非常多的，我们不可能是完全一一列举出来的，只能通过抽象图来统一计算。
右单旋：
右单旋的情况：跟左单旋的本质是差不多的，只不过逻辑相反而已。
同样，我们来关于它们的组合：也是36种（左单旋那里已经很清楚了）。
接着更加复杂的情况：
双旋转：
我们经过上面的图分析：当插入的位置不同时，它得出的结果有时符合我们的预期，有时却不符合我们的预期。说明有些情况我们并不适合仅仅用单一的单旋来解决。那么我们该如何去解决呢？我们接着来分析：
好了，有了上面的分析，我们现在来模拟实现一下：
创建结点：
template<class K,class V>
struct AVTreeNode
{pair<K, V> _kv;AVTreeNode<K, V>* _left;AVTreeNode<K, V>* _right;AVTreeNode<K, V>* _parent;int bf;AVTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),bf(0){ }
};1.这里我们使用KV键值模型。
2.通过上面的介绍，我们需要的成员有：键值对_kv，左指针_left,右指针_right，父亲_parent，平衡因子_bf.
3.对于为什么我们直接使用struct？我们之前就已经讲过了，因为后面我们会在它的类外使用到它们的成员，与其把它弄成public,不如直接利用struct默认是public的特性。来满足我们的需求。
4.构造函数进行初始化。把_kv置成kv，指针初始化成空，bf置0.
构造函数这块比较常规就不多讲解了。
AVLTree部分
构造类的成员变量
template<class K,class V> class AVLTree {typedef AVTreeNode<K, V> Node; public: private:Node* _root; }1.这里typedef一下，避免写得太长。
2.它的成员是_root根节点
构造函数
AVLTree():_root(nullptr){}插入部分
bool insert(const pair<K, V>& kv)
{//找到插入的位置if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;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->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//控制平衡因子while (parent){//新增节点在左子树，平衡因子就减减if (cur == parent->_left){parent->bf--;}//新增节点在右子树，平衡因子就加加else //if (cur == parent->_right){parent->bf++;}//如果当前父亲节点的平衡因子变成了0，说明它不会再影响到它祖先的节点了if (parent->bf == 0){break;}//当前父亲节点的平衡因子变为-1/1时，说明它是由原本的0变成的，这说明了，它必将 //会影响到它的祖先，所以需要向上更新它的平衡因子else if (parent->bf == 1 || parent->bf == -1){cur = parent;parent = parent->_parent;}//平衡因子变成了2后，说明需要旋转了。else if (parent->bf == 2 || parent->bf == -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){RotateRL(parent);}//先左旋再右旋else if (parent->bf == -2 && cur->bf == 1){RotateLR(parent);}break;}else{assert(false);}}}至于什么时候左旋？右旋？先左旋后右旋？先右旋再左旋？
我们可以看到最开始那里，按照图里的情况：来得出它的条件：
即：
左旋
右旋
先右后左
先左再右
旋转部分：
左旋转
对着图写代码：不然特别容易错误！！！！
void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left; parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;//记录当前父亲的父亲节点，方便旋转后，cur的链接Node* ppnode = parent->_parent;parent->_parent = cur;// 1是prent，3是cur// // 1 3// 3 -----> 1 5// 5//if (parent == _root)//出错点1if(ppnode==nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}//更新平衡因子parent->bf = cur->bf = 0;}
右旋转：
ps:看这图来写！！！！不然容易出错！！！！1
void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;// 1是prent，3是cur// // 1 3// 3 -----> 5 1// 5if(ppnode==nullptr)//错误点1//if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->bf = cur->bf = 0;}上面分析图里已经很详细了，这里就不多讲解了。
双旋转
先右再左
void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->bf;RotateR(parent->_right);//写错了//RotateR(parent);RotateL(parent);if (bf == 0){cur->bf = 0;parent->bf = 0;curleft->bf = 0;}else if (bf == -1){cur->bf = 1;curleft->bf = 0;parent->bf = 0;}else if (bf == 1){parent->bf = -1;cur->bf = 0;curleft->bf = 0;}else{assert(false);}}1.这里要看清楚你要旋转的是那个节点！！！
2.这里的旋转部分不是很大问题。反而更新平衡因子那里有难度问题。而我们这里直接通过观察法，直接强制更新了。
先左再右
void RotateLR(Node* parent){Node* cur = parent->_left;Node* ccurright = cur->_right;int bf = ccurright->bf;RotateL(parent->_left);RotateR( parent);if (bf == -1){parent->bf = 1;cur->bf = 0;ccurright->bf = 0;}else if (bf == 0){parent->bf = 0;cur->bf = 0;ccurright->bf = 0;}else if (bf == 1){cur->bf = -1;parent->bf = 0;ccurright->bf = 0;}else{assert(false);}}同上解法。
其他情况自己推就可以知道了
那么，我们怎么知道，我们写的AVL树是否正确呢？有什么方法检验它的正确性呢？
这儿提供了一种方法来检验：
检验它的高度差：
int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int LeftHeight = Height(root->_left);int RightHeight = Height(root->_right);return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;}检验是否平衡的方法：
bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;int leftheight = Height(root->_left);int rightheight = Height(root->_right);if (rightheight - leftheight != root->bf){cout << "平衡因子异常" << root->_kv.first << "->" << root->bf << " ";return false;}return abs(rightheight - leftheight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}这里使用：我们使用的公式：平衡因子=右树高度-左树高度
若这个等式并不相等，说明错误了。即造成平衡因子异常。返回错误。
就这样层层递归检查。一旦发现错误立即返回false。
测试：
//int main() //{ // //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; // AVLTree<int, int> t; // for (auto& e : a) // { // //ֶϵ // if (e == 14) // { // int a = 0; // } // t.insert(make_pair(e,e)); // cout << e << "->" << t.IsBalance() << endl; // } // return 0; //}上面还是有很大的偶然性的，所以我们这里使用大量的随机数来检验，减少误差：
int main() {const int N = 10000;vector<int> v;v.reserve(N);srand(time(0));for (int i = 0; i < N; i++){v.push_back(i);}AVLTree<int, int> t;for (auto e : v){t.insert(make_pair(e, e));//cout << e << "->" << t.IsBalance() << endl;}cout << t.IsBalance() << endl;cout << t.Height() << endl;return 0; }
好了，关于AVL平衡树就分析到这里了，希望大家都有所收获！
最后，到了本次鸡汤环节：
