C++：平衡搜索二叉树（AVL）
Sherry_iyao 2024-08-16 09:35:01 阅读 53
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
(
l
o
g
2
n
)
O(log_2 n)
O(log2n)，搜索时间复杂度O(
l
o
g
2
n
log_2 n
log2n)。
🍁AVL树节点的定义
先看代码：
<code>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 factor
AVLTreeNode(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;
}
else
return false;
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
parent->_right = cur;
else
parent->_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，则无需继续向上调整，直接break
break;
}
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树的旋转分四种情况：
新节点插入较高左子树的左侧：右单旋
右旋实现代码：
<code>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;// 调整平衡因子
}
新节点插入较高左子树的右侧—左右：先左单旋再右单旋
实现代码：
<code>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;
}
else
return cur;
}
return nullptr;
}
Erase就有点麻烦了，删除后要保证平衡
举个例子：
要比25小，而且要比10大，很显然只需要寻找<code>?节点左子树最大节点和右子树最小节点即可，那么我们选择左子树最大节点15
实现代码：
注意：下列代码并没有实现删除后平衡因子的调整！！！
<code>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;
else
parent->_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;
else
parent->_right = cur->_left;
delete cur;
return true;
}
// 2个孩子
else
{ // 找右边最小的rightmin
Node* 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，这样可以保证查询时高效的时间复杂度，即
l
o
g
2
(
N
)
log_2 (N)
log2(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 factor
AVLTreeNode(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;
}
else
return false;
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
parent->_right = cur;
else
parent->_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;
}
else
return 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;
else
parent->_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;
else
parent->_right = cur->_left;
delete cur;
return true;
}
// 2个孩子
else
{ // 找右边最小的rightmin
Node* 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;
}
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;
};
你学会了吗？
好啦，本章对于《C++：平衡搜索二叉树（AVL）》的学习就先到这里，如果有什么问题，还请指教指教，希望本篇文章能够对你有所帮助，我们下一篇见！！！
如你喜欢，点点赞就是对我的支持，感谢感谢！！！
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。