1. AVL树的概念与性质
1.1 概念
二叉搜索树虽然能够缩短查找的效率，但是如果存入的数据有序，或者接近有序的时候，二叉搜索树将退化成单支树，查找元素就相当于遍历，查找效率将从O(log2N)退化成O(N)。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法 ：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整) ，即降低树的高度，从而让树更均匀，减少平均搜索长度。
1.2 性质
- AVL树的左右子树均是AVL树
- AVL树的左右子树的高度差(平衡因子)的绝对值不超过1(-1/0/1)
- 如果一颗二叉搜索树是高度平衡的，那他就是AVL树
- 如果有AVL树有n个节点，那么其高度可以保持在log2N，搜索时间复杂度保持在O(log2N)。
2. AVL树的实现
说明：由于AVL树在实际中的应用不多(map和set的底层是红黑树)，所以这里对于增删查改，我们只实现插入，理解插入和降低树的高度的原理即可。
2.1 树的节点和结构的定义
由于AVL树的操作比普通的二叉搜索树要复杂的多，所以在节点的结构设计上，增加了parent指针，形成三叉链的结构，另外，相较于普通二叉搜索树，需要管理平衡因子，所以增加了变量用来保存该节点的平衡因子
所以节点结构如下：
template<class K, class V> struct AVLTreeNode { pair<K,V> _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf;//balance factor AVLTreeNode(const pair<K,V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} };
树的结构中成员变量只有一个根节点即可，为了方便我们使用节点，所以顺便在类里面做一个typedef
template<class K, class V> class AVLTree { typedef AVLTreeNode<K,V> Node; typedef pair<K,V> data; public: //...... private: Node* _root; }
2.2 节点的插入（重点！！！）
AVL树就是在二叉搜索树的基础上引入了平衡因子用于控制树的结构，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为以下几步
- 按照二叉搜索树的插入方式插入节点
- 调整父节点的平衡因子，并判断是否符合要求
- 如果不符合要求，就调整树的结构
1️⃣首先，针对第一步，就是判断插入节点与当前节点的强弱关系，从而选择不同子树，直到找到空节点的时候，判断插入位置，然后new一个节点链接上去。
2️⃣对于第二步，调整插入节点的父节点的平衡因子：如果是在左子树插入，就让平衡因子自减1，如果是在右子树插入的，就让平衡因子自增1，然后向上迭代判断，直到父节点的平衡因子变成0，表明父节点的高度没有发生变化，就不需要更改上层节点的平衡因子了。每次更改完平衡因子之后都需要判断当前节点的平衡因子是否在正常范围内，如果不在正常范围内的话，就需要进行调整——旋转。由于调整完之后的树的结构一定是符合要求且高度不会发生变化的，所以不需要再次向上迭代调整。
3️⃣对于旋转操作，实际情况下有非常多种可能性，所以这里将所有种类进行一下分类，然后分别处理。
情况一：新节点插入较高左子树的左侧——右单旋
逻辑图：
解决方法：让60变成30的右节点，然后把30的原右节点交给60作为左节点，这样30的左右子树高度就相同了。
//右单旋代码实现 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppNode = parent->_parent; //处理subLR的部分 if(subLR)//当subLR不为空时 subLR->_parent = parent; parent->_left = subLR; //处理parent和subR之间的关系 parent->_parent = subL; subL->_right = parent; //处理subR的parent if(ppNode) { subL->_parent = ppNode; if(ppNode->_left == parent)//parent是左节点 { ppNode->_left = subL; } else//parent是右节点 { ppNode->_right = subL; } } else//parent是根节点的时候 { _root = subL; subL->_parent = nullptr; } //处理平衡因子 subL->_bf = parent->_bf = 0; }情况二：新节点插入较高右子树的右侧——左单旋
与情况一类似，就是左右互换一下。
//左单旋代码实现 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppNode = parent->_parent; //处理subRL的部分 parent->_right = subRL; if(subRL) subRL->_parent = parent; //处理parent和subR之间的关系 subR->_left = parent; parent->_parent = subR; //处理subR的parent if(ppNode)//parent不是根节点的时候，需要处理parent的父亲节点 { subR->_parent = ppNode; if(ppNode->_left == parent)//parent是左节点 { ppNode->_left = subR; } else//parent是右节点 { ppNode->_right = subR; } } else//parent是根节点的时候 { _root = subR; subR->_parent = nullptr; } //处理平衡因子 parent->_bf = subR->_bf = 0; }情况三：新节点插入较高左子树的右侧——左右双旋
对于这种情况，如果直接右单旋的话，那就会变成情况四，所以不能直接右单旋，所以这里的解决方案就是首先进行一次左单旋，将情况变成符合右单旋的情况，然后再进行一次右单旋，此时对平衡因子的处理将会杂乱无章，所以最后需要单独处理平衡因子。
void RotateLR(Node* parent)//左右双旋 { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; //先对parent的left进行左单旋，得到中间过程 RotateL(subL); //对中间过程的parent进行右单旋 RotateR(parent); //现在树的结构已经平衡了，然后处理平衡因子 //对于平衡因子的处理，这里只需要处理parent，subL和subLR，具体情况需要分插入的位置来决定 if(bf == 0)//当subLR即是新插入的节点时 { parent->_bf = subL->_bf = subLR->_bf = 0; } else if(bf == -1)//新插入的节点是subLR的左 { subL->_bf = subL->_bf = 0; parent->_bf = 1; } else if(bf == 1)//新插入的节点是subLR的右 { subL->_bf = -1; parent->_bf = subLR->_bf = 0; } else//出现意外情况 { assert(false); } }情况四：新节点插入较高右子树的左侧
此类情况和情况三非常相似，只是对称而已，所以这里是先对90进行右单旋，然后再对30进行左单旋。最后单独处理平衡因子即可。
void RotateRL(Node* parent)//右左双旋 { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); if(bf == 0) { parent->_bf = subR->_bf = subRL->_bf = 0; } else if(bf == 1) { subRL->_bf = subR->_bf = 0; parent->_bf = -1; } else if(bf == -1) { parent->_bf = subRL->_bf = 0; subR->_bf = 1; } else { assert(false); } }
由于每次节点的增删都会导致结构发生变化，平衡因子将会发生改变，而且只会增加1或者减少1，所以当平衡因子发生改变的时候出现的不合法的情况的值只能是2或者-2。此时，对应到上述的几种需要旋转的条件，最终得到的分类有
- parent->_bf == 2 && cur->_bf == 1
- parent->_bf == 2 && cur->_bf == -1
- parent->_bf == -2 && cur->_bf == 1
- parent->_bf == -2 && cur->_bf == -1
那么最终插入的代码实现如下：
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; } //走到需要插入的位置了，现在new一个节点插入 cur = new Node(kv); //判断在左树还是右树 if(parent->_kv.first < cur->_kv.first)//右边插入 { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } //处理平衡因子 while(parent) { //修改平衡因子 if(cur == parent->_left)//在左树插入就--，右树就++ { parent->_bf--; } else { parent->_bf++; } //判断是否合法，不合法就修改树的结构 if(parent->_bf == 0)//刚好平衡，子树的高度没变，不需要修改父亲的平衡因子 break; else if(parent->_bf == 1 || parent->_bf == -1)//子树高度改变，迭代修改父亲的平衡因子 { cur = parent; parent = parent->_parent; } else if(parent->_bf == 2 || parent->_bf == -2)//结构不符合AVLTree，修改结构 { //旋转 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//其他情况代表AVLTree实现出现问题 assert(false); } return true; }
补充说明：节点的删除原理
因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除(找替代节点)，然后再更新平衡因子，只不过与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
具体实现可以参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版
3.AVL树的验证与性能分析
3.1 AVL树的验证
AVL树本质上是再二叉搜索树上加上了平衡性的限制，所以在验证一棵树是不是AVL树的时候，就可以首先验证这棵树是否是BSTree，如果是BSTree的话，在验证每个节点左右子树的高度差是否小于等于1，这里不能直接验证平衡因子，因为平衡因子是单独修改的，所以也有可能出现错误。
bool isBalance()//这个函数需要在类外调用，无法传入private的参数，所以需要用一个无参的isBalance封装一下 { return isBalance(_root);//与无参的isBalance构成函数重载 } //中序遍历树 void InOrder(vector<pair<K,V>>& v, Node* root) { if(root == nullptr) return; InOrder(v, root->_left); v.push_back(root->_kv); InOrder(v, root->_right); } //判断是否是二叉搜索树，中序遍历然后判断结果是否有序，如果有序就说明是二叉搜索树 bool isBSTree(Node* root) { vector<pair<K,V>> v; InOrder(v,root); for(size_t i = 0; i < v.size() - 1; ++i) { if(v[i].first > v[i+1].first) return false; } return true; } //计算树的高度 int GetHeight(Node* root) { if(root == nullptr) return 0; int lh = GetHeight(root->_left); int rh = GetHeight(root->_right); return lh > rh ? lh + 1 : rh + 1; } bool isBalance(Node* root) { if(root == nullptr)//空树也是AVL树 return true; if(isBSTree(root))//当该树是二叉搜索树的时候才继续判断是否符合AVL树的条件，否则直接返回flase { int leftHeight = GetHeight(root->_left); int rightHeight = GetHeight(root->_right); return abs(leftHeight-rightHeight) < 2//当该节点的平衡因子小于2时，递归判断所有子树是否是AVL树，所有子树都是的时候，整棵树才是AVL树 && isBalance(root->_left) && isBalance(root->_right); } else return false; }
3.2AVL树的性能分析
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即l o g 2 ( N ) log_2 (N)log
2
(N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
最后，附上整个类的实现代码
#pragma once #include <iostream> #include <assert.h> using namespace std; template<class K, class V> struct AVLTreeNode { pair<K,V> _kv; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; AVLTreeNode(const pair<K,V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} }; template<class K, class V> class AVLTree { typedef AVLTreeNode<K,V> Node; public: AVLTree() :_root(nullptr) {} 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; } //走到需要插入的位置了，现在new一个节点插入 cur = new Node(kv); //判断在左树还是右树 if(parent->_kv.first < cur->_kv.first)//右边插入 { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } //处理平衡因子 while(parent) { //修改平衡因子 if(cur == parent->_left)//在左树插入就--，右树就++ { parent->_bf--; } else { parent->_bf++; } //判断是否合法，不合法就修改树的结构 if(parent->_bf == 0)//刚好平衡，子树的高度没变，不需要修改父亲的平衡因子 break; else if(parent->_bf == 1 || parent->_bf == -1)//子树高度改变，迭代修改父亲的平衡因子 { cur = parent; parent = parent->_parent; } else if(parent->_bf == 2 || parent->_bf == -2)//结构不符合AVLTree，修改结构 { //旋转 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//其他情况代表AVLTree实现出现问题 { assert(false); } } return true; } void RotateL(Node* parent)//左单旋 { Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppNode = parent->_parent; //处理subRL的部分 parent->_right = subRL; if(subRL) subRL->_parent = parent; //处理parent和subR之间的关系 subR->_left = parent; parent->_parent = subR; //处理subR的parent if(ppNode)//parent不是根节点的时候，需要处理parent的父亲节点 { subR->_parent = ppNode; if(ppNode->_left == parent)//parent是左节点 { ppNode->_left = subR; } else//parent是右节点 { ppNode->_right = subR; } } else//parent是根节点的时候 { _root = subR; subR->_parent = nullptr; } //处理平衡因子 parent->_bf = subR->_bf = 0; } void RotateR(Node* parent)//右单旋 { Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppNode = parent->_parent; if(subLR) subLR->_parent = parent; parent->_left = subLR; parent->_parent = subL; subL->_right = parent; if(ppNode) { subL->_parent = ppNode; if(ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; } } else { _root = subL; subL->_parent = nullptr; } subL->_bf = parent->_bf = 0; } void RotateLR(Node* parent)//左右双旋 { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; //先对parent的left进行左单旋，得到中间过程 RotateL(subL); //对中间过程的parent进行右单旋 RotateR(parent); //现在树的结构已经平衡了，然后处理平衡因子 //对于平衡因子的处理，这里只需要处理parent，subL和subLR，具体情况需要分插入的位置来决定 if(bf == 0)//当subLR即是新插入的节点时 { parent->_bf = subL->_bf = subLR->_bf = 0; } else if(bf == -1)//新插入的节点是subLR的左 { subL->_bf = subL->_bf = 0; parent->_bf = 1; } else if(bf == 1)//新插入的节点是subLR的右 { subL->_bf = -1; parent->_bf = subLR->_bf = 0; } else//出现意外情况 { assert(false); } } void RotateRL(Node* parent)//右左双旋 { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); if(bf == 0) { parent->_bf = subR->_bf = subRL->_bf = 0; } else if(bf == 1) { subRL->_bf = subR->_bf = 0; parent->_bf = -1; } else if(bf == -1) { parent->_bf = subRL->_bf = 0; subR->_bf = 1; } else { assert(false); } } bool isBalance() { return isBalance(_root); } void InOrder(vector<pair<K,V>>& v, Node* root) { if(root == nullptr) return; InOrder(v, root->_left); v.push_back(root->_kv); InOrder(v, root->_right); } bool isBSTree(Node* root) { vector<pair<K,V>> v; InOrder(v,root); for(size_t i = 0; i < v.size() - 1; ++i) { if(v[i].first > v[i+1].first) return false; } return true; } int GetHeight(Node* root) { if(root == nullptr) return 0; int lh = GetHeight(root->_left); int rh = GetHeight(root->_right); return lh > rh ? lh + 1 : rh + 1; } bool isBalance(Node* root) { if(root == nullptr) return true; if(isBSTree(root)) { int leftHeight = GetHeight(root->_left); int rightHeight = GetHeight(root->_right); return abs(leftHeight-rightHeight) < 2 && isBalance(root->_left) && isBalance(root->_right); } else return false; } private: Node* _root = nullptr; };
本节完
