我要评论
✨ 世事漫随流水，算来一梦浮生 🌏
📃个人主页：
🔥个人专栏：c++学习
🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞
avl树目录
🚀前言
前面我们学到了二叉搜索树，【c++高阶】二叉搜索树的全面解析与高效实现
虽然二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家g.m.adelson-velskii和e.m.landis在1962年发明了一种解决上述问题的方法，即avl树，它以其独特的平衡机制和高效的搜索性能，成为了一颗璀璨的明星。它不仅解决了二叉搜索树在数据插入和删除时可能产生的失衡问题，更通过旋转操作，使得树的高度始终保持在一个相对较低的水平，从而保证了搜索的高效性。让我们来详细看看avl树到底是怎么解决上述问题的吧，踏上这学习之旅。
一. avl树的概念
📒二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位俄罗斯的数学家g.m.adelson-velskii和e.m.landis在1962年发明了一种解决上述问题的方法：
📙一棵avl树或者是空树，或者是具有以下性质的二叉搜索树：
🎈注意： 如果一棵二叉搜索树是高度平衡的，它就是avl树。如果它有n个结点，其高度可保持在o（
）搜索时间复杂度o（
）。
二. avl树节点的定义
avl树节点的定义通常包含以下几个关键部分：
🧩1. 基本元素
在调整失衡的avl树时，我们需要频繁的访问父节点，所以在avl树中我们需要使用三叉链，因此avl树的节点除了包含左右子节点的指针，还需要一个指向父节点的指针。
🧩2. 平衡因子（_bf）
🧩3.构造函数
另外需要说明一下，本文中，我们使用key/value模型的avl树
🧩avl节点定义：
template<class k, class v>
struct avltreenode
{
pair<k, v> _kv;//第一个数据存储key，第二个数据存储value
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) //新节点左右都为空，平衡因子为0
{}
};注意：
可能有些同学对pair没有了解，这里简单介绍一下，pair可以将两个数据组成一组元素，因此对于key/value模型这种需要用到两个数据为一组的元素时就可以使用，内部的成员变量为first和second，主要使用方法如下：
pair<t1, t2> p1(v1, v2); //输入两个数据创建pair类型变量
make_pair(v1, v2); //输入两个数据通过函数创建pair类型变量
p1.first //访问p1的第一个数据
p1.second //访问p1的第二个数据三. avl树的插入
🌈avl树就是在二叉搜索树的基础上引入了平衡因子，因此avl树也可以看成是二叉搜索树。那么avl树的插入过程可以分为两步：
在我们进行插入操作之前，我们先定义一个avl树的类
avl树定义：
template<class k,class v>
class avltree
{
typedef avltreenode<k, v> node;
public:
// 其他未实现的成员函数
private:
node* _root = nullptr;
};cur插入后，parent的平衡因子一定需要调整
avl树的插入操作类似于我们之前二叉搜索树的插入，只不过avl树的插入操作涉及到旋转操作，我们先演示一下它的全部代码
bool insert(const pair<k, v>& kv) //和之前的二叉平衡树插入类似
{
if (_root == nullptr)
{
_root = new node(kv);
return true;
}
//第一步先找到cur应该插入的位置
node* parent = nullptr, * cur = _root;
while (cur)
{
parent = cur; //保留其父节点
if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
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) //和书上相反，因为书上是把左侧插入节点平衡因子增大，这里左侧插入减小
{
// 不平衡了，旋转处理，cur为插入节点的父节点，paernt为cur的父节点
if (parent->_bf == 2 && cur->_bf == 1) //rr型，在子树根节点右子树的右子树插入节点
{ //逆时针左旋转
rotatel(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)//ll型，在子树根节点左子树上的左子树插入节点，
{ //顺时针右旋转
rotater(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1) //rl型，在子树根节点右子树上的左子树插入节点
{//先顺时针右旋变成rr型，再逆时针左旋，最后就是原子树根节点右子树上左子树作为子树根节点。
rotaterl(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1) //lr型，在子树根节点左子树上的右子树插入节点
{ //先逆时针左旋变成ll型，再顺时针右旋，最后就是原子树根节点左子树上的右子树作为子树根节点。
rotatelr(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}四. avl树的旋转
如果在一棵原本是平衡的avl树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，
使之平衡化。根据节点插入位置的不同，avl树的旋转分为四种：
🌈右单旋
新节点插入子树根节点左子树的左子树上（ll型）:
此处旋转是将30的右子树变成60的左子树，然后让60成为30的右子树
在旋转中有几点要注意：
如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树
avl树右单旋代码示例：
void rotater(node* parent) //顺时针右单旋，arent为根，subl为根左子树，sublr为根左子树的右子树
{ //sublr变成parene的左边，parent变成subl的右边，subl变成这颗子树的根
node* subl = parent->_left, *sublr = subl->_right;
node* parentparent = parent->_parent;
//改变parent的左子树
parent->_left = sublr;
if (sublr != nullptr) //避免为空
sublr->_parent = parent;
//改变parent的父节点
subl->_right = parent;
parent->_parent = subl;
//改变子树根节点，调整subl为子树根节点
if (parentparent == nullptr){//第一种情况：parent为根节点
_root = subl;
subl->_parent = nullptr;
}
else{//第二种情况：parent不为根节点
if (parentparent->_left == parent) parentparent->_left = subl;
else parentparent->_right = subl;
subl->_parent = parentparent; //记得更新子树根节点的父节点
}
parent->_bf = subl->_bf = 0; //更新平衡因子
}🌈左单旋
新节点插入子树根节点右子树的右子树上（ll型）:
左单旋与上面的右单旋类似，所以我们直接来看代码
avl树左单旋代码示例：
void rotatel(node* parent) //逆时针左单旋，parent为子树根节点，subr为根右子树，subrl为根右子树的左子树
{ //subrl变成parene的右边，parent变成subr的左边，subr变成这颗子树的根
node* subr = parent->_right, *subrl = subr->_left;
node* parentparent = parent->_parent;
//改变parentt的右子树
parent->_right = subrl;
if(subrl != nullptr) //避免为空
subrl->_parent = parent;
//改变parent的父节点
subr->_left = parent;
parent->_parent = subr;
//改变子树根节点，调整subr为子树根节点
if (parentparent == nullptr) { //第一种情况：parent为根节点
_root = subr;
subr->_parent = nullptr;
}
else{ //第二种情况，parent不是根节点
if (parentparent->_left == parent) parentparent->_left = subr;
else parentparent->_right = subr;
subr->_parent = parentparent;//记得更新子树根节点的父节点
}
parent->_bf = subr->_bf = 0;//更新平衡因子
}🌙左右双旋
新节点插入子树根节点左子树的右子树上（lr型）:
这里是将双旋变成单旋后再旋转，先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。
avl树左右双旋代码示例：
void rotatelr(node* parent) //先以根节点的左子树进行右旋，再对根节点进行左旋
{
node* subl = parent->_left, *sublr = subl->_right;
int bf = sublr->_bf;
rotatel(parent->_left);
rotater(parent);
if (bf == 0) { //其本身就是新增节点，h = 0
subl->_bf = 0;
sublr->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1) { //在subl的右子树插入节点
subl->_bf = -1;
sublr->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1){ //在subl的左子树插入节点
subl->_bf = 0;
sublr->_bf = 0;
parent->_bf = 1;
}
else assert(false);
}🌙右左双旋
新节点插入子树根节点右子树的左子树上（rl型）:
操作过程左右双旋类似，我们直接看代码
void rotaterl(node* parent) //先以根节点的右子树进行右旋，再对根节点进行左旋
{
node* subr = parent->_right, *subrl = subr->_left;
int bf = subrl->_bf; //g
rotater(parent->_right);
rotatel(parent);
//更新平衡因子
if (bf == 0) { //其本身就是新增节点, h = 0
subr->_bf = 0;
subrl->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1) { //在subrl上的右子树插入节点
subr->_bf = 1;
subrl->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1) { //在subrl的左子树上插入节点
subr->_bf = 0;
subrl->_bf = 0;
parent->_bf = -1;
}
else assert(false);
}总结：
旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新
五. avl树的验证
📝avl树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证avl树，可以分两步：
📝1. 验证其为二叉搜索树
代码示例：
void inorder()
{
_inorder(_root);
cout << endl;
}
void _inorder(node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
cout << root->_kv.first << " ";
_inorder(root->_right);
}
📝2. 验证其为平衡树
代码示例：
bool isbalance()
{
return _isbalance(_root);
}
private:
bool _isbalance(node* root)
{
if (root == nullptr) return true;
int leftheight = _height(root->_left), rightheight = _height(root->_right);
int diff = rightheight - leftheight;
if (abs(diff) >= 2)
{
cout << root->_kv.first << "高度差异常" << endl;
return false;
}
if (diff != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return _isbalance(root->_left) && _isbalance(root->_right);
}
size_t _height(node* root)
{
if (root == nullptr) return 0;
size_t leftheight = _height(root->_left);
size_t rightheight = _height(root->_right);
return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}📝3. 验证用例：
void testavltree()
{
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 << e << "->" << t.isbalance() << endl;
}
t.inorder();
cout << endl;
if (t.isbalance()) printf("avl树建立成功\n");
else printf("avl树建立失败\n");
}
六.avl树的性能和完整代码
avl树追求的是严格平衡，因此可以保证查找时高效的时间复杂度o(logn)，但是如果我们需要频繁的对其进行旋转来维护平衡，一定程度上会影响效率，尤其是删除节点时的最差情况下我们可能需要一路旋转到根的位置。
相对于avl树的严格平衡，红黑树则追求一种相对平衡，因此会略胜一筹，后面的文章中会对红黑树进行讲解。
| 缺陷 | 原因 |
| 插入操作复杂 | 为了保持树的平衡，每次插入或删除节点时，avl树可能需要进行多次旋转操作。具体来说，插入一个节点可能需要单旋转或双旋转来重新平衡树结构，而删除节点后可能需要从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级最坏情况下为o(logn)。这增加了操作的复杂性并可能影响性能。 |
| 维护成本高 | 由于avl树要求每个节点的左右子树高度差不超过1，因此需要频繁地检查和调整树的结构。这种严格的平衡要求导致了相对较高的维护成本，特别是在频繁进行插入和删除操作的情况下。 |
| 空间开销较大 | 虽然avl树在查找效率上具有优势，但由于其需要频繁地进行旋转操作以维持平衡，这可能导致额外的空间开销。尤其是在处理大量数据时，这种开销可能会更加明显。 |
| 不适用于所有场景 | avl树适用于查找操作远多于插入和删除操作的场景。如果在一个应用中插入和删除操作也非常频繁，那么avl树可能不是最优选择，因为每次插入和删除都需要进行平衡调整，这会影响性能。 |
avl树的完整代码如下：
#pragma once
#include <iostream>
#include <assert.h>
#include <cmath>
using namespace std;
template<class k, class v>
struct avltreenode
{
pair<k, v> _kv;//第一个数据存储key，第二个数据存储value
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) //新节点左右都为空，平衡因子为0
{}
};
template<class k, class v>
class avltree
{
typedef avltreenode<k, v> node;
public:
//默认成员函数
avltree() = default; //构造
avltree(const avltree<k, v>& t) //拷贝构造
{
_root = copy(t._root);
}
avltree<k, v>& operator=(avltree<k, v> t) //赋值构造
{
swap(_root, t._root);
return *this;
}
~avltree() //析构
{
destroy(_root);
_root = nullptr;
}
bool insert(const pair<k, v>& kv) //和之前的二叉平衡树插入类似
{
if (_root == nullptr)
{
_root = new node(kv);
return true;
}
//第一步先找到cur应该插入的位置
node* parent = nullptr, * cur = _root;
while (cur)
{
parent = cur; //保留其父节点
if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
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) //和书上相反，因为书上是把左侧插入节点平衡因子增大，这里左侧插入减小
{
// 不平衡了，旋转处理，cur为插入节点的父节点，paernt为cur的父节点
if (parent->_bf == 2 && cur->_bf == 1) //rr型，在子树根节点右子树的右子树插入节点
{ //逆时针左旋转
rotatel(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)//ll型，在子树根节点左子树上的左子树插入节点，
{ //顺时针右旋转
rotater(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1) //rl型，在子树根节点右子树上的左子树插入节点
{//先顺时针右旋变成rr型，再逆时针左旋，最后就是原子树根节点右子树上左子树作为子树根节点。
rotaterl(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1) //lr型，在子树根节点左子树上的右子树插入节点
{ //先逆时针左旋变成ll型，再顺时针右旋，最后就是原子树根节点左子树上的右子树作为子树根节点。
rotatelr(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}
node* find(const k& key)
{
node* cur = _root;
while (cur)
{
if (cur->_key < key){
cur = cur->_right;
}
else if (cur->_key > key){
cur = cur->_left;
}
else{
return cur;
}
}
return nullptr;
}
node* leftmost()
{
if (_root == nullptr) return nullptr;
node* cur = _root;
while (cur->_left) cur = cur->_left;
return cur;
}
node* rightmost()
{
if (_root == nullptr) return nullptr;
node* cur = _root;
while (cur->_right) cur = cur->_right;
return cur;
}
void inorder()
{
_inorder(_root);
cout << endl;
}
bool isbalance()
{
return _isbalance(_root);
}
private:
bool _isbalance(node* root)
{
if (root == nullptr) return true;
int leftheight = _height(root->_left), rightheight = _height(root->_right);
int diff = rightheight - leftheight;
if (abs(diff) >= 2)
{
cout << root->_kv.first << "高度差异常" << endl;
return false;
}
if (diff != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return _isbalance(root->_left) && _isbalance(root->_right);
}
size_t _height(node* root)
{
if (root == nullptr) return 0;
size_t leftheight = _height(root->_left);
size_t rightheight = _height(root->_right);
return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}
void _inorder(node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_inorder(root->_right);
}
void rotatel(node* parent) //逆时针左单旋，parent为子树根节点，subr为根右子树，subrl为根右子树的左子树
{ //subrl变成parene的右边，parent变成subr的左边，subr变成这颗子树的根
node* subr = parent->_right, *subrl = subr->_left;
node* parentparent = parent->_parent;
//改变parentt的右子树
parent->_right = subrl;
if(subrl != nullptr) //避免为空
subrl->_parent = parent;
//改变parent的父节点
subr->_left = parent;
parent->_parent = subr;
//改变子树根节点，调整subr为子树根节点
if (parentparent == nullptr) { //第一种情况：parent为根节点
_root = subr;
subr->_parent = nullptr;
}
else{ //第二种情况，parent不是根节点
if (parentparent->_left == parent) parentparent->_left = subr;
else parentparent->_right = subr;
subr->_parent = parentparent;//记得更新子树根节点的父节点
}
parent->_bf = subr->_bf = 0;//更新平衡因子
}
void rotater(node* parent) //顺时针右单旋，arent为根，subl为根左子树，sublr为根左子树的右子树
{ //sublr变成parene的左边，parent变成subl的右边，subl变成这颗子树的根
node* subl = parent->_left, *sublr = subl->_right;
node* parentparent = parent->_parent;
//改变parent的左子树
parent->_left = sublr;
if (sublr != nullptr) //避免为空
sublr->_parent = parent;
//改变parent的父节点
subl->_right = parent;
parent->_parent = subl;
//改变子树根节点，调整subl为子树根节点
if (parentparent == nullptr){//第一种情况：parent为根节点
_root = subl;
subl->_parent = nullptr;
}
else{//第二种情况：parent不为根节点
if (parentparent->_left == parent) parentparent->_left = subl;
else parentparent->_right = subl;
subl->_parent = parentparent; //记得更新子树根节点的父节点
}
parent->_bf = subl->_bf = 0; //更新平衡因子
}
void rotaterl(node* parent) //先以根节点的右子树进行右旋，再对根节点进行左旋
{
node* subr = parent->_right, *subrl = subr->_left;
int bf = subrl->_bf; //g
rotater(parent->_right);
rotatel(parent);
//更新平衡因子
if (bf == 0) { //其本身就是新增节点, h = 0
subr->_bf = 0;
subrl->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1) { //在subrl上的右子树插入节点
subr->_bf = 1;
subrl->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1) { //在subrl的左子树上插入节点
subr->_bf = 0;
subrl->_bf = 0;
parent->_bf = -1;
}
else assert(false);
}
void rotatelr(node* parent) //先以根节点的左子树进行右旋，再对根节点进行左旋
{
node* subl = parent->_left, *sublr = subl->_right;
int bf = sublr->_bf;
rotatel(parent->_left);
rotater(parent);
if (bf == 0) { //其本身就是新增节点，h = 0
subl->_bf = 0;
sublr->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1) { //在subl的右子树插入节点
subl->_bf = -1;
sublr->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1){ //在subl的左子树插入节点
subl->_bf = 0;
sublr->_bf = 0;
parent->_bf = 1;
}
else assert(false);
}
void destroy(node* root)
{
if (root == nullptr)return;
destroy(root->_left);
destroy(root->_right);
delete root;
}
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;
}
private:
node* _root = nullptr;
};
void testavltree()
{
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 << e << "->" << t.isbalance() << endl;
}
t.inorder();
cout << endl;
printf("最左边节点为：%d，最右边节点为：%d\n", t.leftmost()->_kv.first, t.rightmost()->_kv.first);
if (t.isbalance()) printf("avl树建立成功\n");
else printf("avl树建立失败\n");
}
发表评论