AVL树：高效平衡的二叉搜索树

🌟 快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。🌟

在这里插入图片描述

引言🤔

在数据结构的奇妙世界里，二叉搜索树（BST）原本是查找数据的好帮手。想象一下，它就像一本有序的字典，能快速帮我们找到想要的信息。可要是数据排得太整齐，像排队一样有序，二叉搜索树就会“变形”成单支树，这时候查找数据就像在长长的队伍里一个个找，效率低得让人抓狂😫。别担心，1962年，两位聪明的俄罗斯数学家G.M.Adelson - Velskii和E.M.Landis发明了AVL树，给这个问题找到了完美的解决方案👏。

AVL树的概念🧐

1.1 平衡的定义

AVL树就像是一个超级严格的“平衡大师”😏，它不仅是二叉搜索树，还得满足每个节点的左右子树高度差（也就是平衡因子）的绝对值不能超过1。这就好比走钢丝的杂技演员，两边的平衡杆长度差得控制在一定范围内，才能稳稳地走在钢丝上。
在这里插入图片描述

1.2 高度与复杂度

因为AVL树这么会“平衡”，所以哪怕它有好多好多节点（(n)个节点），它的高度也能保持在(O(log_2 n))这个不错的水平。这就意味着，我们查找数据的时候，时间复杂度也是(O(log_2 n))，快得飞起🛫！

AVL树节点的定义📋

要实现AVL树，先得把它的“小砖头”——节点定义好。每个节点都像一个小盒子，装着数据，还有指向左右“小伙伴”（子节点）和“家长”（父节点）的指针，另外还有个记录平衡因子的小标签。下面是用C++ 写的节点定义模板哦👇：

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;   // 该节点的左孩子AVLTreeNode<T>* _pRight;  // 该节点的右孩子AVLTreeNode<T>* _pParent; // 该节点的双亲T _data;int _bf;         // 该节点的平衡因子
};

AVL树的插入🎯

AVL树插入新数据就像往一个有序的书架上放新书，分两步走：

3.1 二叉搜索树插入

先按照二叉搜索树的规矩，从根节点开始，把新书（新数据）和每个节点的数据比较。要是新书比当前节点的数据小，就往左走；要是大，就往右走，直到找到合适的空位，把新书放进去📚。

3.2 平衡因子调整

新书放进去后，可能会把书架弄“歪”，也就是破坏了AVL树的平衡。这时候就得从新书的“家长”开始，沿着书架往上检查，调整每个节点的平衡因子。在调整过程中，“家长”节点的平衡因子会根据新书插在左边还是右边做相应变化（左边就减1，右边就加1）。这时候“家长”的平衡因子可能出现三种情况：

平衡因子为0：这说明放新书之前，“家长”的平衡因子是正负1，放进去后刚刚好变成0，书架又稳了，插入成功🎉。
平衡因子为正负1：意味着放新书前“家长”的平衡因子是0，放进去后变成正负1，以“家长”为根的这部分书架变高了，还得继续往上检查调整🧐。
平衡因子为正负2：糟糕，这说明“家长”的平衡因子违反规定啦，得赶紧用旋转操作来把书架扶正😰。

AVL树的旋转🔄

当AVL树因为插入新书变得不平衡时，根据新书插的位置不同，有四种旋转“魔法”来恢复平衡：

4.1 左左（LL）：右单旋

要是新书插在较高左子树的左侧，就来个右单旋。想象一下，失衡的节点（叫它(pParent)）像个小塔，它的左子节点（(pSubL)）来帮忙把塔扶正。具体做法就是：

把(pSubL)的右子节点（(pSubLR)）放到(pParent)的左边当左子节点。
如果(pSubLR)存在，记得告诉它新“家长”是(pParent)。
再把(pParent)放到(pSubL)的右边当右子节点。
接着更新(pParent)和(pSubL)的“家长”指针，要是原来的塔尖（根节点）变了，也要更新根节点指针。
最后，把(pParent)和(pSubL)的平衡因子都设为0，塔就稳稳当当啦🧱。

4.2 右右（RR）：左单旋

和左左情况相反，新书插在较高右子树的右侧时，就来个左单旋，跟右单旋类似，只是方向反过来。
在这里插入图片描述

4.3 左右（LR）：先左单旋再右单旋

新书插在较高左子树的右侧时，先对失衡节点的左子节点来个左单旋，再对失衡节点来个右单旋。这个过程中，要小心保存和更新每个节点的平衡因子，保证书架重新平衡。
在这里插入图片描述

4.4 右左（RL）：先右单旋再左单旋

新书插在较高右子树的左侧时，先对失衡节点的右子节点来个右单旋，再对失衡节点来个左单旋。同样，别忘了平衡因子的更新。
在这里插入图片描述

AVL树的验证✅

要看看AVL树是不是真的“合格”，可以从两方面检查：

5.1 验证为二叉搜索树

像给书架上的书排序一样，对AVL树进行中序遍历。要是遍历出来的顺序是有序的，那就说明它是个合格的二叉搜索树📖。

5.2 验证为平衡树

一个个检查每个节点的平衡因子，看看它们左右子树高度差的绝对值是不是都没超过1。同时，还要检查平衡因子算得对不对🧮。
在这里插入图片描述

AVL树的删除🗑️

AVL树删除节点就像从书架上拿走一本书，和二叉搜索树的删除方法差不多。但拿走书后，书架可能又歪了，得重新调整平衡。有时候运气不好，可能得一直调整到最上面的根节点。具体怎么做，可以参考《算法导论》或者《数据结构 - 用面向对象方法与C++描述》殷人昆版📚。

AVL树的性能📈

AVL树在查找数据方面就像个超级跑车，时间复杂度是(O(log_2 n))，快得没话说。可要是经常对它进行插入和删除这些“大动作”，就像经常给跑车改装，为了保持平衡，得频繁调整，性能就会受影响，特别是删除的时候，可能要一直调整到根节点，很费时间。所以呢，要是数据基本不怎么变，查询又多，AVL树就是个好选择；要是数据经常变来变去，它可能就不太合适啦😕。

AVL树实现代码示例📄

#pragma once
#include <iostream>
#include <utility>
#include <cassert>template<class K, class V>
class AVLTreeNode
{
public:AVLTreeNode(const std::pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // 平衡因子std::pair<K, V> _kv;
};template<class K, class V>
class AVLTree
{
public:typedef AVLTreeNode<K, V> Node;~AVLTree(){destroy(_root);}void destroy(Node* node){if (node){destroy(node->_left);destroy(node->_right);delete node;}}bool insert(const std::pair<K, V>& key){try{if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if ((cur->_kv).first < key.first){cur = cur->_right;}else if ((cur->_kv).first > key.first){cur = cur->_left;}else{return false;}}cur = new Node(key);cur->_parent = parent;if ((parent->_kv).first < (cur->_kv).first){parent->_right = cur;}else{parent->_left = cur;}// 考虑平衡因子while (cur){if (parent == nullptr){break; // 如果 parent 为 nullptr，说明已经到根节点，跳出循环}if (cur == parent->_right){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){// 旋转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);}}return true;}catch (const std::bad_alloc&){return false;}}void RotateL(Node* parent) // 左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}// 修改_bfparent->_bf = subR->_bf = 0;}void RotateR(Node* parent) // 右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subL->_right;if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* parentParent = parent->_parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}// 修改_bfparent->_bf = subL->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){// 新增的就是subRLparent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1){// subRL的右结点就是新增的parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == -1){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else{subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}}// 中序打印方法void inorderPrint() const{inorderPrintHelper(_root);std::cout << std::endl;}// 判断是否为平衡二叉树bool isBalanced() const{int height = 0;return isBalancedHelper(_root, height);}private:Node* _root = nullptr;// 中序遍历辅助函数void inorderPrintHelper(Node* node) const{if (node){inorderPrintHelper(node->_left);std::cout << "Key: " << node->_kv.first << ", Value: " << node->_kv.second << std::endl;inorderPrintHelper(node->_right);}}// 判断是否为平衡二叉树的辅助函数bool isBalancedHelper(Node* node, int& height) const{if (node == nullptr){height = 0;return true;}int leftHeight = 0;int rightHeight = 0;// 递归判断左子树是否平衡if (!isBalancedHelper(node->_left, leftHeight)){return false;}// 递归判断右子树是否平衡if (!isBalancedHelper(node->_right, rightHeight)){return false;}// 计算当前节点的高度height = std::max(leftHeight, rightHeight) + 1;// 检查当前节点的左右子树高度差是否不超过 1if (std::abs(leftHeight - rightHeight) > 1){return false;}return true;}
};

总结🎉

AVL树就像一个聪明又有点小脾气的数据结构小伙伴😜。它用巧妙的平衡方法，解决了二叉搜索树可能失衡的问题，让查找数据又快又稳。它的插入、旋转和验证等操作一环扣一环，保证了自己时刻保持高效。虽然在结构经常变化的时候有点“小傲娇”，性能不太好，但在适合的场景下，绝对是个得力助手💪。通过深入了解AVL树，希望大家在编程时能更明智地选择数据结构，让程序跑得又快又好🚀。
在这里插入图片描述

投票环节🎊

你觉得AVL树在以下哪种场景最有用呢🧐？

数据基本不变，查询频繁：就像图书馆的藏书目录，很少新增或删除书籍，但经常有人查询。📚
数据频繁插入和删除：比如一个实时更新的新闻网站，不断有新新闻发布，旧新闻过期删除。📰
其他场景（请留言说明）：说不定你有独特的想法哦，快来分享！💡

快来投出你宝贵的一票吧👇，让我们看看大家对AVL树的看法！🎯