前言
本篇文章主要内容：AVL树底层结构解析、c++代码实现以及key/key_value场景分析。
之前，我们学习了一种特殊的二叉树结构——二叉搜索树。它最大的好处在于，能够在平均情况下提供O(log n)时间复杂度的查找、插入和删除操作。然而，当数据的插入顺序与理想情况大相径庭时，传统的二叉搜索树可能会退化成接近单支树的形态，导致其查找效率骤降至O(n)。为了弥补这一缺陷，计算机科学界孕育出了一种更加精巧的数据结构——AVL树。AVL树通过引入平衡因子的概念，确保在每次插入或删除操作后，左右子树的高度差达到最小，从而保证了最优的O(log n)查找效率。本文将带你深入探索AVL树的奥秘，见证它是如何在维护平衡的同时，优雅地解决了传统二叉搜索树的缺陷。
实现二叉搜索树时，我们将键（key）作为节点的数据部分。而在本次实现AVL树的过程中，我们将进行 “改进” ，使用键值对（key_value）作为节点数据域。
一、AVL树的概念
AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis，是一种自平衡二叉搜索树，能够在进行插入或删除操作后，保持平衡状态，维持较高的查找效率。
它或者是一棵空树，或者具有以下特点：
1. 它是一棵二叉搜索树。
2. 它左右子树的高度差不超过1。（无法保证做到高度一致）
3. 它的每一棵子树也符合前两点特性（每一棵子树都是AVL树）。
一般情况下，AVL树通过平衡因子来检查左右子树是否达到平衡。每一个节点都带有一个平衡因子，平衡因子的值等于该节点右子树的高度减去左子树的高度。当平衡因子的值为-1/0/1时，表明以该节点为根的树达到平衡。
由于AVL树能够持续保持平衡（所有平衡因子的值都在合法范围内），所以其高度可以控制在log n级别，保证了最优的查找效率。
二、AVL树底层解析及实现
1. 节点的定义
//节点 template<class K, class V> struct AVLTNode { pair<K, V> _kv;//键值对--数据域 AVLTNode<K, V>* _left;//指向左孩子的指针 AVLTNode<K, V>* _right;//指向右孩子的指针 AVLTNode<K, V>* _parent;//指向父亲的指针 int _bf;//平衡因子 //节点构造 AVLTNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} };
AVL树的节点包含五个成员变量：pair（键值对，存储key值和value值）、指向左孩子的指针、指向右孩子的指针、指向父亲节点的指针以及平衡因子bf。不难看出，AVL树的节点是一种三叉链结构，更有利于节点之间的控制访问。
这里我们简单介绍一下pair：
pair是c++标准库自带的一种类型，定义在<utility>头文件中，用于表示二元组，该类将一对不同类型的值（T1和T2）耦合在一起。单个值可以通过它的公有成员first和second来访问。
代码示例：
using namespace std; int main() { pair<int, char> pr1;//无参构造 pair<int, char> pr2 = { 1,'w' };//初始化器构造 pair<int, char> pr3(pr2);//拷贝构造 pr1 = pr2;//支持赋值重载 pr1.swap(pr2);//支持交换 pr1 == pr2;//支持大小比较，比较规则是 先比第一个成员，再比第二个成员 cout << pr1.first;//访问第一个成员 cout << pr1.second;//访问第二个成员 return 0; }
2. 接口声明
需要实现的接口如下：
//AVL树 template<class K, class V> class AVLTree { typedef AVLTNode<K, V> Node;//重命名简化代码 public: //强制生成无参构造 AVLTree() = default; //拷贝构造 AVLTree(const AVLTree<K, V>& t); //析构 ~AVLTree(); //中序遍历 void Inorder(); //插入 bool Insert(const pair<K, V>& kv); //查找 Node* Find(const K& key); //获取节点个数 size_t Size() const; private: Node* _root = nullptr;//根节点指针 size_t _size = 0;//节点个数 };
3. AVL树的插入
AVL树插入的总体过程是：首先按照二叉搜索树的规则进行插入，然后根据插入的位置更新父亲以及祖先的平衡因子。更新过程中，判断平衡因子是否合法，若不合法，则需要通过旋转来调整树的结构，使之维持平衡。
3.1 更新平衡因子
首先探讨平衡因子的更新方法（设cur是新节点，parent是新节点的父亲）：
1. 由于平衡因子的值为右子树的高度减去左子树的高度，所以：
当cur是parent的左孩子，则parent的平衡因子 - 1；
当cur是parent的右孩子，则parent的平衡因子 + 1。
2. parent的平衡因子更新之后，以parent为根节点的树的高度可能发生变化，此时需要根据平衡因子的值来判断是否继续向祖先方向更新平衡因子。判断规则如下：
• parent的平衡因子为0（则更新之前平衡因子为-1/1），以parent为根的树的高度不变，无需向上更新。
• parent的平衡因子为1/-1（则更新之前平衡因子为0），以parent为根的树的高度 + 1，需要向上更新，直到某个节点平衡因子为0为止。
• parent的平衡因子为2/-2（则更新之前平衡因子为1/-1），此时以parent为根的树已经不平衡，需要进行旋转。
总结：
1. 不难发现，向上更新是一个循环的过程。停止更新的条件是：更新完根节点或某个节点平衡因子更新后的值为0。
2. 向上更新时，我们需要让cur指向当前parent节点，而让parent指向其父亲节点，此时三叉链结构的便利性得到体现。
3. 更新过程当中，一旦发现某平衡因子的值为2/-2，就需要旋转。
节点插入和更新平衡因子代码实现：
//插入 bool Insert(const pair<K, V>& kv) { //根节点为空，直接插入 if (_root == nullptr) { _root = new Node(kv); _size++; return true; } Node* parent = nullptr; Node* cur = _root; //寻找合适位置 while (cur) { if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } //让cur的parent指针指向父亲 cur->_parent = parent; //更新平衡因子 while (parent) { //根据插入节点的位置更新父亲的平衡因子 if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } //判断平衡因子的值 if (parent->_bf == 0)//等于0，停止更新 { break; } else if (parent->_bf == 1 || parent->_bf == -1)//等于1，继续向上更新 { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -1)//等于2，需要旋转 { //旋转 break; } else //不可能有其他情况，走到这里直接断言报错 { assert(false); } } _size++; return true; }
这里需要注意两点：
1. 由于数据类型是键值对，所以需要进行比较的是键的大小，跟值无关。
2. 与之前实现二叉搜索树相同，我们默认不支持插入重复键。
3.2 旋转（重点）
接下来主要介绍AVL树的旋转。
当某平衡因子的值为2/-2时，需要旋转。
旋转原则：在保持二叉搜索树特性的基础上，尽量降低树的高度，使树保持平衡。
旋转主要分为四种，分别是：右单旋、左单旋、左右双旋、右左双旋。
右单旋
当新节点位于较高左子树的左侧时，进行右单旋。
如图，这里的a、b、c都是抽象形式，表示的是高度为h的子树（h>=0）。
由于节点2的存在，左子树比右子树高1，所以节点6的平衡因子为-1。
当插入一个新节点，使得 a 的高度由h变为h+1时，节点2的平衡因子就变为-1，节点6的平衡因子变为-2。
新节点使得 a 的高度增1，其位于较高左子树的左侧，将节点6作为旋转点，进行右单旋。
右单旋的过程：如图所示，将节点6标记为parent，节点2标记为subL，b标记为subLR。然后将parent的左指针指向subLR，subL的右指针指向parent，subL成为该部分的新根。
（这里的subL含义为左孩子，subLR为左孩子的右孩子）
旋转完成之后，整个体系达到平衡，将subL和parent的平衡因子设置为0。
AVL树是三叉链结构，实际代码编写过程远比描述复杂，有许多细节需要处理。
代码实现：
//右单旋 void RotateR(Node* parent) { //先标记subL和subLR Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;//让parent的左指针指向subLR if (subLR) subLR->_parent = parent;//让subLR的父指针指向parent。注意subLR可能为空，需要判断 //标记parent的父亲 Node* ppNode = parent->_parent; subL->_right = parent;//让subL的右指针指向parent parent->_parent = subL;//parent的父指针指向subL //处理ppNode和subL的关系 if (ppNode == nullptr)//ppNode为空说明parent之前是根节点 { _root = subL;//subL成为新根 subL->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } //调整平衡因子 parent->_bf = 0; subL->_bf = 0; }
左单旋
当新节点位于较高右子树的右侧时，进行左单旋。
由于节点8的存在，右子树比左子树高1，所以节点3的平衡因子为1。
当插入一个新节点，使得 c 的高度由h变为h+1时，节点8的平衡因子就变为1，节点3的平衡因子变为2。
新节点使得 c 的高度增1，其位于较高右子树的右侧，将节点3作为旋转点，进行左单旋。
左单旋的过程：如图所示，将节点3标记为parent，节点8标记为subR，b标记为subRL。然后将parent的右指针指向subRL，subR的左指针指向parent，subR成为该部分的新根。
（这里的subR含义为右孩子，subRL为右孩子的左孩子）
旋转完成之后，整个体系达到平衡，将subR和parent的平衡因子设置为0。
代码实现：
//左单旋 void RotateL(Node* parent) { //先标记subR和subRL Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;//让parent的右指针指向subRL if (subRL) subRL->_parent = parent;//让subRL的父指针指向parent。注意subRL可能为空，需要判断 //标记parent的父亲 Node* ppNode = parent->_parent; subR->_left = parent;//让subR的左指针指向parent parent->_parent = subR;//parent的父指针指向subR //处理ppNode和subR的关系 if (ppNode == nullptr)//ppNode为空说明parent之前是根节点 { _root = subR;//subR成为新根 subR->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } //调整平衡因子 parent->_bf = 0; subR->_bf = 0; }
左右双旋
当新节点位于较高左子树的右侧时，进行左右双旋。
如图，新节点使得 b 的高度增1，其位于较高左子树的右侧，进行一次右单旋显然不能达到平衡。所以插入之后需要将subL作为旋转点，进行一次左单旋；然后将parent作为旋转点，进行一次右单旋。
双旋转操作可以直接调用单旋转实现，但平衡因子的调节是最棘手的问题。
我们对 b 进行细化。
场景1：b（subLR）的平衡因子为0（b为插入的新节点）。
两次旋转之后，subL和parent的左右子树高度差相同，平衡因子均调整为0。
场景2：b（subLR）的平衡因子为-1。
两次旋转之后，subLR的左右子树高度一致，平衡因子调整为0；parent的右子树比左子树高1，平衡因子调整为1。
场景3：b（subLR）的平衡因子为1。
两次旋转之后，subLR的左子树比右子树高1，平衡因子调整为-1；parent的左右子树高度一致，平衡因子调整为0。
左右双旋代码实现：
//左右双旋 void RotateLR(Node* parent) { //先标记subL和subLR Node* subL = parent->_left; Node* subLR = subL->_right; //记录subLR的平衡因子 int bf = subLR->_bf; RotateL(subL);//将subL作为旋转点，进行一次左单旋 RotateR(parent);//将parent作为旋转点，进行一次右单旋 //调整平衡因子 if (bf == 0)//场景1 { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0; } else if (bf == -1)//场景2 { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 1; } else if (bf == 1)//场景3 { subL->_bf = -1; subLR->_bf = 0; parent->_bf = 0; } else //不可能有其他情况，走到这里直接断言报错 { assert(false); } }
右左双旋
当新节点位于较高右子树的左侧时，进行右左双旋。
如图，新节点位于较高右子树的左侧时，一次左单旋显然无法达到平衡。需要将subR作为旋转点，进行一次右单旋；然后将parent作为旋转点，进行一次左单旋。
与左右双旋相同，右左双旋也需考虑平衡因子调节的问题。这里的情况与左右双旋相似，不再进行详细讲解。
场景1：b（subRL）的平衡因子为0（b为插入的新节点）。
场景2： b（subRL）的平衡因子为-1。
场景3：b（subRL）的平衡因子为1。
右左双旋代码实现：
//右左双旋 void RotateRL(Node* parent) { //先标记subR和subRL Node* subR = parent->_right; Node* subRL = subR->_left; //记录subRL的平衡因子 int bf = subRL->_bf; RotateR(subR);//将subR作为旋转点，进行一次右单旋 RotateL(parent);//将parent作为旋转点，进行一次左单旋 //调整平衡因子 if (bf == 0)//场景1 { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 0; } else if (bf == -1)//场景2 { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } else if (bf == 1)//场景3 { parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else { assert(false); } }
旋转种类的选取判定
在代码中，需要根据特定条件来判断何时使用右单旋、何时使用左右双旋等操作。从四种旋转的图示可以看出，我们可以使用插入新节点之后parent节点和subL/subR节点的平衡因子作为判定原则。
右单旋：parent平衡因子为-2；subL平衡因子为-1。
左单旋：parent平衡因子为2；subR平衡因子为1。
左右双旋：parent平衡因子为-2；subL平衡因子为1。
右左双旋：parent平衡因子为2；subR平衡因子为-1。
注：这里的subL、subR在Insert函数中都可以用cur来表示。
3.3 总代码
AVL树插入操作的全部代码如下：
//插入 bool Insert(const pair<K, V>& kv) { //根节点为空，直接插入 if (_root == nullptr) { _root = new Node(kv); _size++; return true; } Node* parent = nullptr; Node* cur = _root; //寻找合适位置 while (cur) { if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } //让cur的parent指针指向父亲 cur->_parent = parent; //更新平衡因子 while (parent) { //根据插入节点的位置更新父亲的平衡因子 if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } //判断平衡因子的值 if (parent->_bf == 0)//等于0，停止更新 { break; } else if (parent->_bf == 1 || parent->_bf == -1)//等于1，继续向上更新 { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -1)//等于2，需要旋转 { //右单旋 if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } //左单旋 else if (parent->_bf == 2 && cur->_bf == 1) { RotateL(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 //不可能有其他情况，走到这里直接断言报错 { assert(false); } } _size++; return true; } //右单旋 void RotateR(Node* parent) { //先标记subL和subLR Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;//让parent的左指针指向subLR if (subLR) subLR->_parent = parent;//让subLR的父指针指向parent。注意subLR可能为空，需要判断 //标记parent的父亲 Node* ppNode = parent->_parent; subL->_right = parent;//让subL的右指针指向parent parent->_parent = subL;//parent的父指针指向subL //处理ppNode和subL的关系 if (ppNode == nullptr)//ppNode为空说明parent之前是根节点 { _root = subL;//subL成为新根 subL->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } //调整平衡因子 parent->_bf = 0; subL->_bf = 0; } //左单旋 void RotateL(Node* parent) { //先标记subR和subRL Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;//让parent的右指针指向subRL if (subRL) subRL->_parent = parent;//让subRL的父指针指向parent。注意subRL可能为空，需要判断 //标记parent的父亲 Node* ppNode = parent->_parent; subR->_left = parent;//让subR的左指针指向parent parent->_parent = subR;//parent的父指针指向subR //处理ppNode和subR的关系 if (ppNode == nullptr)//ppNode为空说明parent之前是根节点 { _root = subR;//subR成为新根 subR->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } //调整平衡因子 parent->_bf = 0; subR->_bf = 0; } //左右双旋 void RotateLR(Node* parent) { //先标记subL和subLR Node* subL = parent->_left; Node* subLR = subL->_right; //记录subLR的平衡因子 int bf = subLR->_bf; RotateL(subL);//将subL作为旋转点，进行一次左单旋 RotateR(parent);//将parent作为旋转点，进行一次右单旋 //调整平衡因子 if (bf == 0)//场景1 { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0; } else if (bf == -1)//场景2 { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 1; } else if (bf == 1)//场景3 { subL->_bf = -1; subLR->_bf = 0; parent->_bf = 0; } else //不可能有其他情况，走到这里直接断言报错 { assert(false); } } //右左双旋 void RotateRL(Node* parent) { //先标记subR和subRL Node* subR = parent->_right; Node* subRL = subR->_left; //记录subRL的平衡因子 int bf = subRL->_bf; RotateR(subR);//将subR作为旋转点，进行一次右单旋 RotateL(parent);//将parent作为旋转点，进行一次左单旋 //调整平衡因子 if (bf == 0)//场景1 { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 0; } else if (bf == -1)//场景2 { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } else if (bf == 1)//场景3 { parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else { assert(false); } }
4. AVL树的查找
AVL树的查找逻辑与传统二叉搜索树完全相同。需要注意：该函数通过key值查找。
//查找 Node* Insert(const K& key) { Node* cur = _root; while (cur) { //比较key值 if (key < cur->_kv.first) { cur = cur->_left; } else if (key > cur->_kv.first) { cur = cur->_right; } else { return cur; } } return nullptr; }
5. 获取节点个数
直接返回成员_size的值。
//获取节点个数 size_t Size() const { return _size; }
6. 中序遍历、拷贝构造和析构
三个函数的实现逻辑与传统二叉搜索树基本相同。注意中序遍历需要打印key值和value值；拷贝构造时要注意拷贝平衡因子和指向父亲的指针。
//中序遍历 void Inorder() { _Inorder(_root); } void _Inorder(Node* root) { if (root == nullptr) return; _Inorder(root->_left); cout << root->_kv.first << ' ' << root->_kv.second << endl; _Inorder(root->_right); }
//拷贝构造 AVLTree(const AVLTree<K, V>& t) { _root = _Copy(t._root); _size = t._size; } Node* _Copy(Node* root, Node* parent = nullptr) { if (root == nullptr) return nullptr; Node* NewRoot = new Node(root->_kv); NewRoot->_bf = root->_bf;//复制平衡因子 NewRoot->_parent = parent;//设置父指针 //递归拷贝左子树和右子树 NewRoot->_left = _Copy(root->_left, NewRoot); NewRoot->_right = _Copy(root->_right, NewRoot); return NewRoot; }
//析构 ~AVLTree() { _Destroy(_root); } void _Destroy(Node* root) { if (root == nullptr) return; _Destroy(root->_left); _Destroy(root->_right); delete root; }
7. AVL树的验证
写一段代码验证我们实现的AVL树是否正确：
//计算高度 int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); } //验证AVL树 bool IsAVLTree() { return _IsAVLTree(_root); } bool _IsAVLTree(Node* root) { if (root == nullptr) return true; int left_bf = _Height(root->_left); int right_bf = _Height(root->_right); //验证高度差 if (abs(left_bf - right_bf) >= 2) { cout << "高度差异常" << endl; return false; } //验证平衡因子 if (right_bf - left_bf != root->_bf) { cout << "平衡因子异常" << endl; return false; } //递归验证左子树和右子树 return _IsAVLTree(root->_left) && _IsAVLTree(root->_right); }
//主函数 int main() { AVLTree<int, int> t; int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto& e : a) { t.Insert({ e,e }); } cout << "size:" << t.Size() << endl; t.Inorder(); cout << t.IsAVLTree() << endl; return 0; }
运行结果：
8. 程序全部代码
AVL树实现全部代码：
using namespace std; //节点 template<class K, class V> struct AVLTNode { pair<K, V> _kv;//键值对--数据域 AVLTNode<K, V>* _left;//指向左孩子的指针 AVLTNode<K, V>* _right;//指向右孩子的指针 AVLTNode<K, V>* _parent;//指向父亲的指针 int _bf;//平衡因子 //节点构造 AVLTNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} }; //AVL树 template<class K, class V> class AVLTree { typedef AVLTNode<K, V> Node;//重命名简化代码 public: //强制生成无参构造 AVLTree() = default; //拷贝构造 AVLTree(const AVLTree<K, V>& t) { _root = _Copy(t._root); _size = t._size; } //析构 ~AVLTree() { _Destroy(_root); } //中序遍历 void Inorder() { _Inorder(_root); } //插入 bool Insert(const pair<K, V>& kv) { //根节点为空，直接插入 if (_root == nullptr) { _root = new Node(kv); _size++; return true; } Node* parent = nullptr; Node* cur = _root; //寻找合适位置 while (cur) { if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } //让cur的parent指针指向父亲 cur->_parent = parent; //更新平衡因子 while (parent) { //根据插入节点的位置更新父亲的平衡因子 if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; } //判断平衡因子的值 if (parent->_bf == 0)//等于0，停止更新 { break; } else if (parent->_bf == 1 || parent->_bf == -1)//等于1，继续向上更新 { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -1)//等于2，需要旋转 { //右单旋 if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } //左单旋 else if (parent->_bf == 2 && cur->_bf == 1) { RotateL(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 //不可能有其他情况，走到这里直接断言报错 { assert(false); } } _size++; return true; } //查找 Node* Find(const K& key) { Node* cur = _root; while (cur) { //比较key值 if (key < cur->_kv.first) { cur = cur->_left; } else if (key > cur->_kv.first) { cur = cur->_right; } else { return cur; } } return nullptr; } //获取节点个数 size_t Size() const { return _size; } //验证AVL树 bool IsAVLTree() { return _IsAVLTree(_root); } private: //右单旋 void RotateR(Node* parent) { //先标记subL和subLR Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;//让parent的左指针指向subLR if (subLR) subLR->_parent = parent;//让subLR的父指针指向parent。注意subLR可能为空，需要判断 //标记parent的父亲 Node* ppNode = parent->_parent; subL->_right = parent;//让subL的右指针指向parent parent->_parent = subL;//parent的父指针指向subL //处理ppNode和subL的关系 if (ppNode == nullptr)//ppNode为空说明parent之前是根节点 { _root = subL;//subL成为新根 subL->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; subL->_parent = ppNode; } //调整平衡因子 parent->_bf = 0; subL->_bf = 0; } //左单旋 void RotateL(Node* parent) { //先标记subR和subRL Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;//让parent的右指针指向subRL if (subRL) subRL->_parent = parent;//让subRL的父指针指向parent。注意subRL可能为空，需要判断 //标记parent的父亲 Node* ppNode = parent->_parent; subR->_left = parent;//让subR的左指针指向parent parent->_parent = subR;//parent的父指针指向subR //处理ppNode和subR的关系 if (ppNode == nullptr)//ppNode为空说明parent之前是根节点 { _root = subR;//subR成为新根 subR->_parent = nullptr; } else { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } //调整平衡因子 parent->_bf = 0; subR->_bf = 0; } //左右双旋 void RotateLR(Node* parent) { //先标记subL和subLR Node* subL = parent->_left; Node* subLR = subL->_right; //记录subLR的平衡因子 int bf = subLR->_bf; RotateL(subL);//将subL作为旋转点，进行一次左单旋 RotateR(parent);//将parent作为旋转点，进行一次右单旋 //调整平衡因子 if (bf == 0)//场景1 { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0; } else if (bf == -1)//场景2 { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 1; } else if (bf == 1)//场景3 { subL->_bf = -1; subLR->_bf = 0; parent->_bf = 0; } else //不可能有其他情况，走到这里直接断言报错 { assert(false); } } //右左双旋 void RotateRL(Node* parent) { //先标记subR和subRL Node* subR = parent->_right; Node* subRL = subR->_left; //记录subRL的平衡因子 int bf = subRL->_bf; RotateR(subR);//将subR作为旋转点，进行一次右单旋 RotateL(parent);//将parent作为旋转点，进行一次左单旋 //调整平衡因子 if (bf == 0)//场景1 { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 0; } else if (bf == -1)//场景2 { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } else if (bf == 1)//场景3 { parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else { assert(false); } } //中序遍历 void _Inorder(Node* root) { if (root == nullptr) return; _Inorder(root->_left); cout << root->_kv.first << ' ' << root->_kv.second << endl; _Inorder(root->_right); } //拷贝构造 Node* _Copy(Node* root, Node* parent = nullptr) { if (root == nullptr) return nullptr; Node* NewRoot = new Node(root->_kv); NewRoot->_bf = root->_bf;//复制平衡因子 NewRoot->_parent = parent;//设置父指针 //递归拷贝左子树和右子树 NewRoot->_left = _Copy(root->_left, NewRoot); NewRoot->_right = _Copy(root->_right, NewRoot); return NewRoot; } //析构 void _Destroy(Node* root) { if (root == nullptr) return; _Destroy(root->_left); _Destroy(root->_right); delete root; } //计算高度 int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); } //验证AVL树 bool _IsAVLTree(Node* root) { if (root == nullptr) return true; int left_bf = _Height(root->_left); int right_bf = _Height(root->_right); //验证高度差 if (abs(left_bf - right_bf) >= 2) { cout << "高度差异常" << endl; return false; } //验证平衡因子 if (right_bf - left_bf != root->_bf) { cout << "平衡因子异常" << endl; return false; } //递归验证左子树和右子树 return _IsAVLTree(root->_left) && _IsAVLTree(root->_right); } Node* _root = nullptr;//根节点指针 size_t _size = 0;//节点个数 };
三、key/key_value搜索场景分析
1. key
在编程中，key（键）在数组、平衡二叉树、哈希表或数据库索引结构中扮演重要角色。key的特别之处在于其唯一性，确保了高效的数据检索。
key的搜索场景：即元素的数据域当中只存储key，key即为需要查找的值。搜索过程中，只需要判断key是否存在。在搜索树结构当中，只支持key的增、删、查，但不支持修改（会破坏搜索树结构）。
举例：小区车库只允许购买车位的业主车进入，那么已购买车位的业主车牌号就会被录入后台系统，此时 “车牌号” 即为key。当车辆进入时，如果能检索到key值，则抬杆；否则无法进入车库。
2. key_value
key-value（键值对）是一种基础且广泛使用的数据存储和检索方式。 在key_value模型中，每一个key都有与之对应的值value。
key_value的搜索场景：元素的数据域中存储key及其对应的value。搜索过程中，不仅需要判断key是否存在，还要访问key存在时对应的value值。在搜索树结构当中，增、删、查操作需要以key为基准进行搜索，对于修改操作，只支持修改value值，不支持修改key。
举例：简单的汉化词典，数据元素中存储英文单词和汉语意思，此时 “英文单词” 即为key，“汉语意思” 即为value。当输入英文单词，就能检索到对应的汉语意思；若单词不正确（如拼写错误），则搜索失败，抛出错误提示。
总结
在深入探讨了AVL树的原理和实现后，我们不难发现，这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题，还通过其独特的平衡机制，确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。通过引入键值对作为节点数据域，AVL树进一步丰富了数据操作的可能性，为实际应用提供了更为灵活和强大的支持。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤
