史上最详细的AVL树的实现(万字+动图讲解旋转)

       🔥🔥 欢迎来到小林的博客！！       🛰️博客主页：✈️小林爱敲代码       🛰️文章专栏：✈️小林的C++之路       🛰️欢迎关注：👍点赞🙌收藏✍️留言       AVL树是一个平衡二叉搜索，相比于红黑树，它更平衡。但是相比于插入删除的操作，红黑树更优。因为旋转有消耗，而红黑树的旋转明显要比AVL树少的多。所以这篇文章给大家带来了平衡二叉树的插入和查找操作，全程动图讲解！千万不要错过！至于删除操以后有机会为大家更新。          每日一句: 即使道路坎坷不平，车轮也要前进；即使江河波涛汹涌，船只也航行。

目录 AVL树的概念AVL树的节点创建AVL类创建AVL树的插入检查AVL树是否正常查找值总结🥳：

AVL树的概念

AVL是一颗平衡二叉搜索树，相比于二叉搜索树。AVL它能始终保持平衡，因为二叉搜索树的缺陷太大。当有序插入数据时，整颗树就会变成一个单链表。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。

AVL树需要满足以下两点性质: 1.它的左右子树都是AVL树。 2.每颗子树的高度差(平衡因子)不超过1或者小于-1。

那我们来看看一颗典型的AVL树

我们可以发现，左边高，它的高度差就是 -1，右边高，高度差就是1。两边一样高，那么高度差就是 0 。所以我们可以用平衡因子，来确定它的一个高度差。这样可以更好的控制它的高度。

AVL树的节点创建

为了更好的控制，我们决定使用三叉链。也就是新增一个parent节点指向自己的父亲，根节点的父亲为空指针。而我们还要一个平衡因子变量，来记录它子树的高度差。left和right指针指向左右两个孩子。这里我们采取key,value模型，所以用pair结构体，作为节点的值。

节点结构体代码：

template<class K,class V> struct AVLNode { AVLNode<K, V>* _left; AVLNode<K, V>* _right; AVLNode<K, V>* _parent; int _bf; //平衡因子，记录高度差 pair<K, V> _kv; //存储的一对数据 //构造函数 AVLNode(const pair<K,V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) //新增节点肯定是叶子节点，所以高度默认0 ,_kv(kv){} }; AVL类创建

只需要一个成员变量 root 来指向整颗树的根即可。构造函数就把root初始化为空。

template <class K, class V> class AVLTree { typedef AVLNode<K, V> Node; public: AVLTree() :_root(nullptr){} private: Node* _root;//AVL树的根 }; AVL树的插入

AVL树的插入，我们要先找到可以插入的位置，然后插入。插入之后我们树的高度可能会发生变化，因此我们需要向上去更新平衡因子。所以我们插入后分多种情况，那就是插入后平衡因子为 0, 1/-1 ，2/-2的情况

插入后平衡因子为0的情况： 插入后平衡因子为0，那么说明在插入之前，这颗树的平衡因子是 -1 或者1，所以在插入之后这棵树的平衡因子变成了0，那么就意味着这棵树已经平衡了，这种情况就不需要做什么事情了。

插入后平衡因子为1/-1的情况： 如果插入和平衡因子为1或者-1，说明在插入之前这棵树的平衡因子是0。也就是说插入之前这颗树是平衡的，而插入之后，引发了高度变化。所以可能会造成不平衡的情况，这种情况我们需要一种往上更新平衡因子。在更新的过程可能会遇到平衡因子变成 2 或者 -2的情况，这时候就需要发生旋转。

平衡因子为2/-2的情况： 在插入的过程中，平衡因子可能会出现为2/-2的情况。当平衡因子为1/-1的时候，会一直往上更新，而在更新的过程中就会发生平衡因子为 2/-2的情况，这种情况我们就需要发生旋转。

假设我们插入一个10，那么10插入的位置应该在 8的右边。 那么此时 8 的左右子树高度发生了变化，因为插入了一个新节点。如果新增节点在右边，则 平衡因子自减，如果新增节点在右边，则平衡因子自增。所以新增后，平衡因子的变化是。 也就是，7所在的节点的子树不平衡了，因为它的平衡因子 > 1了。所以此时我们要发生旋转。而旋转有四种情况。

第一种情况，右边一边高

就如上图的情况，7所在节点的右子树右边一边高，所以这时候我们需要左旋转。那么我们假设7节点为parent。7的右节点8为subR，8的左节点为subRL，而7的父节点为parentparent

左单旋的步骤: 1.让parent的右节点连接subRL 2.subRL的父节点连接parent，如果为空则不连接 3.subR的左节点连接parent 4.parent的父节点连接subR 5.grandparent与subR连接

旋转流程图 最后，我们会发现parent和subR的平衡因子都变了0。也就意味着这颗子树达到了平衡。 左旋转代码：

// 左单旋 void RotateL(Node* parent) { Node* grandparent = parent->_parent; Node* subR = parent->_right; Node* subRL = subR->_left; //父亲连接subRL parent->_right = subRL; if (subRL) subRL->_parent = parent; //subR的左边连接parent subR->_left = parent; parent->_parent = subR; //grandparent连接subR if (grandparent == nullptr) { //grandparent为空，说明parent一开始是根节点 _root = subR; subR->_parent = nullptr; } else { //如果parent一开是grandparent的左子树，则grandparent的左子树连接subR if (parent == grandparent->_left) grandparent->_left = subR; else grandparent->_right = subR; subR->_parent = grandparent; } //更新平衡因子 parent->_bf = subR->_bf = 0; }

第二种情况：左边一边高 左边一边高和右边一边高的思路完全一样。只不过方向反过来。。下面这棵树就是左边一边高，所以我们用右单旋进行调整。

右单旋的步骤: 1.让parent的左节点连接subLR 2.subLR的父节点连接parent，如果为空则不连接 3.subL的右节点连接parent 4.parent的父节点连接subL 5.grandparent与subL连接

右单旋旋转动图: 右单旋代码：

//右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* grandpraent = parent->_parent; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (grandpraent == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (grandpraent->_left == parent) grandpraent->_left = subL; else grandpraent->_right = subL; subL->_parent = grandpraent; } subL->_bf = parent->_bf = 0; }

第三种情况：新节点插入较高左子树的右侧—左右 一边高是直线，曲线就是整棵树是左边高，但是它的孩子却在和它相反的一边。这就意味着这棵树是曲线的，所以单纯的左右旋转无法使它达到平衡。而旋转完后，我们还需要控制平衡因子，控制平衡因子又有三种情况。

情况1.当subL右节点的平衡因子为0时(也就是新增)

把subL左旋转后

随后这颗树就变成了左边一边高，我们在把parent右旋转。

这种情况下，新增节点，subL，parent的平衡因子都变成了0。

情况2.subL的右节点平衡因子为-1时

和之前一样，先把subL左旋转

再把parent右旋转

旋转后 subL的平衡因子为0 subLR的平衡因子为0 parent的平衡因子为1

情况3.subL的右节点平衡因子为1时

老规矩，把subL进行左单旋

再把parent右单旋

旋转后 subL的平衡因子为-1 subLR的平衡因子为0 parent的平衡因子为0

左右双旋代码:

void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int lrbf = subLR->_bf; //先左旋subL RotateL(subL); //右旋parent RotateR(parent); //保存LR的平衡因子 if (lrbf == 0) { parent->_bf = subL->_bf = subLR->_bf = 0; } else if (lrbf == -1) { subL->_bf = subLR->_bf = 0; parent->_bf = 1; } else if (lrbf == 1) { subL->_bf = -1; subLR->_bf = parent->_bf = 0; } else assert(false); }

第四种情况：新节点插入较高左子树的左侧—右左 这种情况和第三种情况相反，但也另外分了三种情况。

情况1.subRL就是新增节点

先右旋转subR 再左旋转parent 旋转完后，subRL和subR还有parent的平衡因子都为0。

情况2.当在subRL的平衡因子为-1时 先右单旋subR 再左单旋parent

最后的平衡因子分别为: subRL 0 parent 0 subR 1

情况3.当在subRL的平衡因子为1时 老规矩，先右旋 subR

然后左旋转parent 最后的平衡因子分别是： parent -1 subRL 0 subR 0

右左双旋代码：

//右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int rlbf = subRL->_bf; RotateR(subR); RotateL(parent); if (rlbf == 0) { subR->_bf = subRL->_bf = parent->_bf = 0; } else if (rlbf == -1) { subRL->_bf = parent->_bf = 0; subR->_bf = 1; } else if (rlbf == 1) { parent->_bf = -1; subR->_bf = subRL->_bf = 0; } else assert(false); } 检查AVL树是否正常 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 (root->_bf != RightHeight - LeftHeight) { cout << root->_kv._first <<"现在是平衡因子是:" << root->_bf << endl; cout << root->_kv._first <<"平衡因子应该是:" << RightHeight - LeftHeight << endl; } return abs(LeftHeight - RightHeight) < 2; } 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 Find(const K& k) { if (_root == nullptr) return false; Node* cur = _root; while (cur) { if (cur->_kv.first > k) cur = cur->_left; else if (cur->_kv.first < k) cur = cur->_right; else return true; } return false; }

---

全部代码：

template<class K, class V> struct AVLNode { AVLNode<K, V>* _left; AVLNode<K, V>* _right; AVLNode<K, V>* _parent; int _bf; //平衡因子，记录高度差 pair<K, V> _kv; //存储的一对数据 //构造函数 AVLNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) //新增节点肯定是叶子节点，所以高度默认0 , _kv(kv) {} }; template <class K, class V> class AVLTree { typedef AVLNode<K, V> Node; public: 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) { parent = cur; if (cur->_kv.first > kv.first)//新插节点的值比当前节点小，往左子树找 cur = cur->_left; else if (cur->_kv.first < kv.first) cur = cur->_right; else return false; //不允许插入重复值的节点 } cur = new Node(kv); //创建新节点 cur->_parent = parent; //连接父亲 if (cur->_kv.first > parent->_kv.first) parent->_right = cur; else parent->_left = cur; //节点插入成功，控制平衡因子,父亲为空，则说明调整到根节点了 while (parent) { if (cur == parent->_right) //插入节点在父亲节点的右边 parent->_bf++; //在右边++，在左边-- else parent->_bf--; if (parent->_bf == 0) { //平衡因子为0，说明这棵树之前的平衡因子是-1或者1，也就是说插入新节点后变平衡了 break; } else if (parent->_bf == 1 || parent->_bf == -1) { //父亲的平衡因子是1或者-1，说明插入之前是0，也就是说插入之前是平衡的 //插入之后高度发生了变化，所以需要继续往上更新平衡因子 cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //平衡因子为2或者-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) RotateLR(parent); else if (parent->_bf == 2 && cur->_bf == -1) RotateRL (parent); break; } else assert(false); } } // 左单旋 void RotateL(Node* parent) { Node* grandparent = parent->_parent; Node* subR = parent->_right; Node* subRL = subR->_left; //父亲连接subRL parent->_right = subRL; if (subRL) subRL->_parent = parent; //subR的左边连接parent subR->_left = parent; parent->_parent = subR; //grandparent连接subR if (grandparent == nullptr) { //grandparent为空，说明parent一开始是根节点 _root = subR; subR->_parent = nullptr; } else { //如果parent一开是grandparent的左子树，则grandparent的左子树连接subR if (parent == grandparent->_left) grandparent->_left = subR; else grandparent->_right = subR; subR->_parent = grandparent; } //更新平衡因子 parent->_bf = subR->_bf = 0; } //右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* grandpraent = parent->_parent; parent->_left = subLR; if (subLR) subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (grandpraent == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (grandpraent->_left == parent) grandpraent->_left = subL; else grandpraent->_right = subL; subL->_parent = grandpraent; } subL->_bf = parent->_bf = 0; } //左右双旋 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int lrbf = subLR->_bf; //先左旋subL RotateL(subL); //右旋parent RotateR(parent); //保存LR的平衡因子 if (lrbf == 0) { parent->_bf = subL->_bf = subLR->_bf = 0; } else if (lrbf == -1) { subL->_bf = subLR->_bf = 0; parent->_bf = 1; } else if (lrbf == 1) { subL->_bf = -1; subLR->_bf = parent->_bf = 0; } else assert(false); } //右左双旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int rlbf = subRL->_bf; RotateR(subR); RotateL(parent); if (rlbf == 0) { subR->_bf = subRL->_bf = parent->_bf = 0; } else if (rlbf == -1) { subRL->_bf = parent->_bf = 0; subR->_bf = 1; } else if (rlbf == 1) { parent->_bf = -1; subR->_bf = subRL->_bf = 0; } else assert(false); } //查找 bool Find(const K& k) { if (_root == nullptr) return false; Node* cur = _root; while (cur) { if (cur->_kv.first > k) cur = cur->_left; else if (cur->_kv.first < k) cur = cur->_right; else return true; } return false; } 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 (root->_bf != RightHeight - LeftHeight) { cout << root->_kv.first << "现在是平衡因子是:" << root->_bf << endl; cout << root->_kv.first << "平衡因子应该是:" << RightHeight - LeftHeight << endl; } return abs(LeftHeight - RightHeight) < 2; } 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; } private: Node* _root;//AVL树的根 };

---

总结🥳：

💦💦关于AVL的删除，以后有机会会为大家更新。如果有写的不好或者有错误的地方，欢迎大家指出。后序会持续为大家更新红黑树，C/C++，数据结构以及linux操作系统相关的知识，如果不嫌弃可以点个收藏加关注。谢谢大佬们了！ 🔥🔥你们的支持是我最大的动力，希望在往后的日子里，我们大家一起进步！！！🔥🔥