C++：平衡搜索二叉树（AVL）

hello，各位小伙伴，本篇文章跟大家一起学习《C++：平衡搜索二叉树（AVL）》，感谢大家对我上一篇的支持，如有什么问题，还请多多指教！

文章目录

- :maple_leaf:AVL树
- :maple_leaf:AVL树节点的定义
- - :leaves:关于pair
- :maple_leaf:AVL树的插入
- :maple_leaf:AVL树的旋转
- :maple_leaf:验证AVL是否平衡
- :maple_leaf:AVL树的Find和Erase
- :maple_leaf:AVL树的性能
- :maple_leaf:AVL树实现的总代码

🍁AVL树

上篇我们讲到了二叉搜索树，二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

AVL树是具有以下性质的搜索二叉树：

它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

那么可以得出：假设一颗AVL树有n个节点，那么其高度可保持在 $O(log_2 n)$ ，搜索时间复杂度O( $log_2 n$ )。

🍁AVL树节点的定义

先看代码：

template<class K,class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

由于要保证左右子树高度之差的绝对值不超过1(-1/0/1)，所以引用了平衡因子_bf来维护，平衡因子的计算为右子树高度减去左子树高度
因为AVL树会对节点进行旋转，所以引入了父节点指针_parent来维护

🍃关于pair

在C++中，pair是一个模板类，用于将两个值（通常是不同类型的值）组合成一个单元，称为键-值对。pair允许我们将两个值一起存储、传递和操作，非常适合需要成对操作的场景。

基本用法：
要使用pair，首先需要包含 <utility> 头文件，因为pair定义在这个头文件中。

但是在某些编译环境中，尤其是较新版本的C++标准中，pair可能会隐式地包含在一些其他标准头文件中，例如 <iostream>或 <map>。这种情况下，您可能会发现在不包含 <utility> 头文件的情况下也能使用pair。

#include <utility>
#include <iostream>int main() {// 创建一个键-值对std::pair<int, std::string> student(1, "Alice");// 访问键和值std::cout << "ID: " << student.first << ", Name: " << student.second << std::endl;// 修改键和值student.first = 2;student.second = "Bob";std::cout << "ID: " << student.first << ", Name: " << student.second << std::endl;return 0;
}

pair还提供了成员函数用于访问其成员：

first：访问第一个元素（键）
second：访问第二个元素（值）

使用示例：
pair在STL中广泛使用，特别是在关联容器中（如map和multimap）存储键值对。例如，使用pair可以方便地在map中插入元素：

#include <iostream>
#include <map>int main() {std::map<int, std::string> studentMap;// 插入键-值对studentMap.insert(std::make_pair(1, "Alice"));studentMap.insert(std::make_pair(2, "Bob"));studentMap.insert(std::make_pair(3, "Charlie"));// 遍历并打印所有键-值对for (const auto& pair : studentMap) {std::cout << "ID: " << pair.first << ", Name: " << pair.second << std::endl;}return 0;
}

🍁AVL树的插入

AVL树本质上就是搜索二叉树，所以插入的规则和搜索二叉树是一样的，只不过多了一个步骤：调整平衡因子

先看代码：

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;}elsereturn false;}cur = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;

// 上述操作都与搜索二叉树基本一致// 调整平衡因子while (parent){if (cur == parent->_left){// 如果插入的位置为父节点的左边，则parent->_bf--parent->_bf--;}else{// 如果插入的位置为父节点的右边，则parent->_bf++parent->_bf++;}if (parent->_bf == 0){// 如果该结点_bf的值为0，则无需继续向上调整，直接breakbreak;}else if (parent->_bf == 1 || parent->_bf == -1){// 如果该结点_bf的值为1或者-1，则继续向上调整cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 如果该结点_bf的值为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){// 双旋操作RotateRL(parent);}else{// 双旋操作RotateLR(parent);}break;}else{assert(0);}}return true;
}

🍁AVL树的旋转

当插入新节点后，AVL树不再平衡，就要进行旋转操作，AVL树的旋转分四种情况：

新节点插入较高左子树的左侧：右单旋

右旋实现代码：

void  RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;// 关键点：当parentParent == nullptr，就要注意根节点的改变if (parentParent == nullptr)// 更改根节点{_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_bf = subL->_bf = 0;// 调整平衡因子
}

新节点插入较高右子树的右侧：左单旋
那么左旋道理也是一样，直接看代码：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr)// 更改根节点{_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;// 调整平衡因子
}

新节点插入较高左子树的右侧—左右：先左单旋再右单旋

实现代码：

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;// 记录旋转前的平衡因子RotateL(parent->_left);RotateR(parent);// 但是调整平衡因子就有点麻烦了// 3种情况if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == -1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

新节点插入较高右子树的左侧—右左：先右单旋再左单旋
实现代码：

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

总结：
假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑

parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR

当subR的平衡因子为1时，执行左单旋
当subR的平衡因子为-1时，执行右左双旋

parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL

当subL的平衡因子为-1是，执行右单旋
当subL的平衡因子为1时，执行左右双旋
旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。

🍁验证AVL是否平衡

int _Height(Node* pRoot)
{if (pRoot == nullptr){return 0;}return _Height(pRoot->_left) > _Height(pRoot->_right) ? _Height(pRoot->_left) + 1 : _Height(pRoot->_right) + 1;
}bool _IsBalanceTree(Node* pRoot)
{// 空树也是AVL树if (nullptr == pRoot) return true;// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(pRoot->_left);int rightHeight = _Height(pRoot->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (diff != pRoot->_bf || (diff > 1 || diff < -1))return false;// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(pRoot->_left) && _IsBalanceTree(pRoot ->_right);void test()
{cout<< _IsBalanceTree(_root) << endl;
}
}

创建好AVL树后，直接在主函数调用test()就可以了

🍁AVL树的Find和Erase

Find和搜索二叉树没什么区别：

Node* Find(const pair<K,V> kv)
{Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){cur = cur->_right;}else if (cur->_kv.first > kv.first){cur = cur->_left;}elsereturn cur;}return nullptr;
}

Erase就有点麻烦了，删除后要保证平衡
举个例子：
在这里插入图片描述
要比25小，而且要比10大，很显然只需要寻找?节点左子树最大节点和右子树最小节点即可，那么我们选择左子树最大节点15

实现代码：
注意：下列代码并没有实现删除后平衡因子的调整！！！

bool Erase(const pair<K, V>kv)
{Node* cur = _root;Node* parent = nullptr;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// 找到后进行删除操作{	// 1、0个孩子if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;return true;}if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;return true;}if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;delete cur;return true;}// 2个孩子else{	// 找右边最小的rightminNode* rightminP = cur;Node* rightmin = cur->_right;while (rightmin->_left){rightminP = rightmin;rightmin = rightmin->_left;}cur->_kv.first = rightmin->_kv.first;if (rightminP->_left == rightmin){rightminP->_left = rightmin->_right;}else{	rightminP->_right = rightmin->_right;}delete rightmin;return true;}}}return false;
}

对于删除具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

🍁AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 $log_2 (N)$ 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

🍁AVL树实现的总代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;template<class K,class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template<class K, class V>
class AVLT
{typedef AVLTreeNode<K, V> Node;
public:AVLT() = default;/*AVLT(const AVLT<K, V> t){_root = Copy(t._root);}*/AVLT& operator=(AVLT<K, V> t){swap(_root, t._root);return *this;}~AVLT(){Destroy(_root);_root = nullptr;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr)// 更改根节点{_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;}void  RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr)// 更改根节点{_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_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){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_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 == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == -1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}}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;}elsereturn false;}cur = new Node(kv);if (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_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){// 不平衡了，旋转处理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{RotateLR(parent);}break;}else{assert(0);}}return true;}Node* Find(const pair<K,V> kv){Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){cur = cur->_right;}else if (cur->_kv.first > kv.first){cur = cur->_left;}elsereturn cur;}return nullptr;}bool Erase(const pair<K, V>kv){Node* cur = _root;Node* parent = nullptr;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{	// 1、0个孩子if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;return true;}if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;return true;}if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;delete cur;return true;}// 2个孩子else{	// 找右边最小的rightminNode* rightminP = cur;Node* rightmin = cur->_right;while (rightmin->_left){rightminP = rightmin;rightmin = rightmin->_left;}cur->_kv.first = rightmin->_kv.first;if (rightminP->_left == rightmin)rightminP->_left = rightmin->_right;elserightminP->_right = rightmin->_right;delete rightmin;return true;}}}return false;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void InOrder(){_InOrder(_root);cout << endl;}int _Height(Node* pRoot){if (pRoot == nullptr){return 0;}return _Height(pRoot->_left) > _Height(pRoot->_right) ? _Height(pRoot->_left) + 1 : _Height(pRoot->_right) + 1;}bool _IsBalanceTree(Node* pRoot){// 空树也是AVL树if (nullptr == pRoot) return true;// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(pRoot->_left);int rightHeight = _Height(pRoot->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (diff != pRoot->_bf || (diff > 1 || diff < -1))return false;// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(pRoot->_left) && _IsBalanceTree(pRoot ->_right);}void test(){cout<< _IsBalanceTree(_root) << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* _root = nullptr;
};