> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 目标：能直接手撕AVL树。
> 毒鸡汤：放弃自己，相信别人，这就是失败的原因。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言
相信大家肯定听过在C++大名鼎鼎的两颗树，这两颗树分别是AVL树和红黑树，学过的小伙伴听到都是瑟瑟发抖，像一些大厂中可能会考手撕AVL树或红黑树。学习这两棵树确实难度很大，正所谓难度越大动力就越大，那本篇我们学习这两棵树的一颗树--AVL树。
⭐主体
学习AVL树咱们按照下面的图解：
🌙AVL树的概念
在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。
AVL树的定义
- 一棵空的树是AVL树
- 如果T是一棵非空的二叉树，T(L)和T(R)分别是其左子树高和右子树高，那么当T满足以下条件时，T是一棵AVL树，|h(L)-h(R)|<=1，其中h(L)和h(R)分别是T(L)和T(R)的高（简称平衡因子）
AVL树的状态：
AVL树的特性：
- 一棵n个元素的AVL树，其高度是O(logn)
- 对于每一个n，n>=0，都存在一棵AVL树
- 对一棵n元素的AVL搜索树，在O(高度)=O(logn)的时间内可以完成查找
- 将一个新元素插入一棵n元素的AVL搜索树中，可以得到一棵n+1个元素的AVL树，而且插入用时为O(logn)
- 一个元素从一棵n元素的AVL搜索树中删除，可以得到一棵n-1个元素的AVL树，而且删除用时为O(logn)
🌙AVL树的结点
- 按照 KV 模型来构造 AVL 树，需要把结点定义为 三叉链结构（左、右、父）。
- 构造函数，由于新构造结点的左右子树均为空树，所以将新构造结点的平衡因子初始设置为 0 。
代码示例：
// 创建AVL树的结点 template<class K,class V> struct 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 树插入一个新结点以后，需要更新插入结点的祖先的平衡因子，因为新结点（也就是叶子结点）的平衡因子为 0，但是它影响的是它的父亲，它父亲的父亲…，所以要更新到祖先结点。
上面的图就需要改变父亲爷爷的平衡因子，我们知道，树的状态有很多，无法穷举，但是我们也有规律可寻，这个规律就在于我们的平衡因子，所以我总结如下：
- 如果新增结点插入在 parent 的右边，只需要给 parent 的平衡因子 +1 即可
- 如果新增结点插入在 parent 的左边，只需要给 parent 的平衡因子 -1 即可
当 parent 的平衡因子更新完以后，可能出现三种情况：0，正负 1，正负 2。
（1）parent 的平衡因子为 0
如果parent的平衡因子是0：说明之前parent的平衡因子是1或-1，说明之前parent一边高、一边低；这次插入之后填入矮的那边，parent所在的子树高度不变，不需要继续往上更新。如图：
（2）如果 parent 的平衡因子为正负 1
如果parent的平衡因子是1或者-1：说明之前parent的平衡因子是0，两边一样高，插入之后一边更高，parent所在的子树高度发生变化，继续往上更新。
①parent为1
②parent为 -1
（3）如果 parent 的平衡因子为正负 2
平衡因子是2或-2，说明之前parent的平衡因子是1或-1，现在插入严重不平衡，违反规则，需要进行旋转处理
- 如果parent的平衡因子是2，cur的平衡因子是1时，说明右边的右边比较高，我们需要进行左单旋
- 如果parent的平衡因子是-2，cur的平衡因子是-1时，说明左边的左边比较高，我们需要进行右单旋
- 如果parent的平衡因子是-2，cur的平衡因子是1时，我们需要进行左右双旋
- 如果parent的平衡因子是2，cur的平衡因子是-1时，我们需要进行右左双旋
这里我们就举一个栗子：
代码实现：
public: // 插入函数 bool Insert(const pair<K, V>& kv) { // 如果AVL树是空树，把插入节点直接作为根节点 if (_root == nullptr) { _root = new Node(kv); _root->_bf = 0; return true; } // 1.按照二叉搜索树的规则插入 Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) // 待插入节点的key值大于当前节点的key值 { // 往右子树走 parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) // 待插入节点的key值小于当前节点的key值 { // 往左子树走 parent = cur; cur = cur->_left; } else // 待插入节点的key值等于当前节点的key值 { return false; // 插入失败，返回false } } // 2.当循环结束，说明cur找到了空的位置，那么就插入 cur = new Node(kv); // 构造一个新节点 if (parent->_kv.first < kv.first) // 如果新节点的key值大于当前parent节点的key值 { // 就把新节点链接到parent的右边 parent->_right = cur; } else // 如果新节点的key值小于当前parent节点的key值 { // 就把新节点链接到parent的左边 parent->_left = cur; } cur->_parent = parent; // 别忘了把新节点里面的_parent指向parent(因为我们定义的是一个三叉链) // 3.更新平衡因子,如果出现不平衡,则需要进行旋转 while (parent) // 最远要更新到根节点去 { if (cur == parent->_right) // 如果cur插在parent的右边，说明parent的右子树增高 { parent->_bf++; // 那么parent的平衡因子要++ } else // 如果cur插在parent的左边，说明parent的左子树增高 { parent->_bf--; // 那么parent的平衡因子要-- } // 判断是否更新结束，或者是否需要进行旋转 if (parent->_bf == 0) // 如果parent的bf等于0，说明左右子树高度一致，就更新结束(原因是新插入的节点把parent左右子树中矮的那一边给填补了） { // 高度不变,更新结束 break; } else if (parent->_bf == 1 || parent->_bf == -1) // 继续往上更新平衡因子(插入节点导致某一边变高了，说明parent所在的子树高度改变了) { // 子树的高度变了，就要继续往上更新祖先 cur = cur->_parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) // 说明插入节点导致本来高的一边又变高了，子树不平衡了，那么此时需要做旋转处理 { // 旋转的四种处理方式 // 1.左单旋 // 2.右单旋 // 3.左右双旋 // 4.右左双旋 // 旋转完成，跳出 break; } else { // 如果程序走到了这里，说明在插入节点之前AVL树就存在不平衡的子树，也就是存在平衡因子 >= 2的节点 // 所以这里加一个断言进行处理 assert(false); } } // 插入成功，返回true return true; }
【C++】手撕AVL树（下） https://developer.aliyun.com/article/1565632
