C++ AVL树 详细讲解

2024-06-07 19:36
文章标签 c++ 讲解 详细 avl

本文主要是介绍C++ AVL树 详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、AVL树的概念

二、AVL树的实现

1.AVL树节点的定义

2.AVL树的插入

3.AVL树的旋转

4.AVL树的验证

三、AVL树的性能

四、完结撒❀


一、AVL树的概念

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

如果一棵二叉搜索树是高度平衡的,它就是 AVL 树。如果它有 n 个结点,其高度可保持在
O(log2 n) ,搜索时间复杂度 O(log2 n)

二、AVL树的实现

1.AVL树节点的定义

AVL树节点的定义:

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;                  // 该节点的平衡因子
};

2.AVL树的插入

AVL 树就是在二叉搜索树的基础上引入了平衡因子,因此 AVL 树也可以看成是二叉搜索树。那么
AVL 树的插入过程可以分为两步:
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子
bool Insert(const pair<K, V>& kv)
{// 1. 先按照二叉搜索树的规则将节点插入到AVL树中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->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{//插入相同值return false;}}//找到cur所在位置cur = new Node(kv);if (parent->_kv.first > cur->_kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}// 2. 新节点插入后,AVL树的平衡性可能会遭到破坏,此时就需要更新平衡因子,并检测是否//破坏了AVL树的平衡性/*pCur插入后,pParent的平衡因子一定需要调整,在插入之前,pParent的平衡因子分为三种情况:-1,0, 1, 分以下两种情况:1. 如果pCur插入到pParent的左侧,只需给pParent的平衡因子-1即可2. 如果pCur插入到pParent的右侧,只需给pParent的平衡因子+1即可此时:pParent的平衡因子可能有三种情况:0,正负1, 正负21. 如果pParent的平衡因子为0,说明插入之前pParent的平衡因子为正负1,插入后被调整成0,此时满足
AVL树的性质,插入成功2. 如果pParent的平衡因子为正负1,说明插入前pParent的平衡因子一定为0,插入后被更新成正负1,此
时以pParent为根的树的高度增加,需要继续向上更新3. 如果pParent的平衡因子为正负2,则pParent的平衡因子违反平衡树的性质,需要对其进行旋转处理*///更新平衡因子while (parent){if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){//二叉树高度没问题,更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1){// 插入前双亲的平衡因子是0,插入后双亲的平衡因子为1 或者 -1 ,说明以双亲为根的二叉树// 的高度增加了一层,因此需要继续向上调整cur = parent;parent = parent->_parent;}else if (parent->_bf == -2 || parent->_bf == 2){//双亲的平衡因子为正负2,违反了AVL树的平衡性//二叉树平衡被破坏,需要旋转完成平衡//判断是右单旋还是左单旋还是双旋//右单旋if (parent->_bf == -2 && cur->_bf == -1){//...}//左单旋else if (parent->_bf == 2 && cur->_bf == 1){//...}//左右双旋else if (parent->_bf == -2 && cur->_bf == 1){//...}//右左双旋else if (parent->_bf == 2 && cur->_bf == -1){//...}}else{//理论上不会出现这种状况assert(false);}}return true;
}

3.AVL树的旋转

如果在一棵原本是平衡的 AVL 树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,
使之平衡化。根据节点插入位置的不同, AVL 树的旋转分为四种:
1) 新节点插入较高左子树的左侧---左左:右单旋

/*上图在插入前,AVL树是平衡的,新节点插入到30的左子树(注意:此处不是左孩子)中,30左
子树增加了一层,导致以60为根的二叉树不平衡,要让60平衡,只能将60左子树的高度减少一层,右子
树增加一层,即将左子树往上提,这样60转下来,因为60比30大,只能将其放在30的右子树,而如果30有
右子树,右子树根的值一定大于30,小于60,只能将其放在60的左子树,旋转完成后,更新节点
的平衡因子即可。在旋转过程中,有以下几种情况需要考虑:1. 30节点的右孩子可能存在,也可能不存在2. 60可能是根节点,也可能是子树如果是根节点,旋转完成后,要更新根节点如果是子树,可能是某个节点的左子树,也可能是右子树此处可举一些详细的例子进行画图,考虑各种情况,加深旋转的理解
*/
void _RotateR(Node Parent)
{// SubL: Parent的左孩子// SubLR: Parent左孩子的右孩子,注意:该Node SubL = Parent->_Left;Node SubLR = SubL->_Right;// 旋转完成之后,30的右孩子作为双亲的左孩子Parent->_Left = SubLR;// 如果30的左孩子的右孩子存在,更新亲双亲if (SubLR)SubLR->_Parent = Parent;// 60 作为 30的右孩子SubL->_Right = Parent;// 因为60可能是棵子树,因此在更新其双亲前必须先保存60的双亲Node Parent = Parent->_Parent;// 更新60的双亲Parent->_Parent = SubL;// 更新30的双亲SubL->_Parent = Parent;// 如果60是根节点,根新指向根节点的指针if (NULL == Parent){_root = SubL;SubL->_Parent = NULL;}else{// 如果60是子树,可能是其双亲的左子树,也可能是右子树if (Parent->_Left == Parent)Parent->_Left = SubL;elseParent->_Right = SubL;}// 根据调整后的结构更新部分节点的平衡因子Parent->_bf = SubL->_bf = 0;
}

2) 新节点插入较高右子树的右侧---右右:左单旋

//左单旋
void LNode(Node* parent)
{/*if (parent == _root){Node* pparent = nullptr;}else{Node* pparent = parent->_parent;}*/Node* pparent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_left = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (pparent){subR->_parent = pparent;if (pparent->_left = parent){pparent->_left = subR;}else{pparent->_right = subR;}}else{_root = subR;subR->_parent = nullptr;}parent->_bf = subR->_bf = 0;
}

3) 新节点插入较高左子树的右侧---左右:先左单旋再右单旋

将双旋变成单旋后再旋转,即: 先对 30 进行左单旋,然后再对 90 进行右单旋 ,旋转完成后再
考虑平衡因子的更新。
// 旋转之前,60的平衡因子可能是-1/0/1,旋转完成之后,根据情况对其他节点的平衡因子进
//行调整
void _RotateLR(Node Parent)
{Node SubL = Parent->_Left;Node SubLR = SubL->_Right;// 旋转之前,保存pSubLR的平衡因子,旋转完成之后,需要根据该平衡因子来调整其他节点的平衡因子int bf = SubLR->_bf;// 先对30进行左单旋_RotateL(Parent->_Left);// 再对90进行右单旋_RotateR(Parent);if (1 == bf)SubL->_bf = -1;else if (-1 == bf)Parent->_bf = 1;
}

4) 新节点插入较高右子树的左侧---右左:先右单旋再左单旋

//右左双旋
void RLNode(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RNode(parent->_right);LNode(parent);if (bf == 1){subRL->_bf = 0;subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subRL->_bf = 0;subR->_bf = 1;parent->_bf = 0;}else if (bf == 0){subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else{//理论没有该状况assert(false);}
}
总结:
假如以 Parent 为根的子树不平衡,即 Parent 的平衡因子为 2 或者 -2 ,分以下情况考虑
1)Parent 的平衡因子为 2 ,说明 Parent 的右子树高,设 Parent 的右子树的根为 SubR
SubR 的平衡因子为 1 时,执行左单旋
SubR 的平衡因子为 -1 时,执行右左双旋
2)Parent 的平衡因子为 -2 ,说明 Parent 的左子树高,设 Parent 的左子树的根为 SubL
SubL 的平衡因子为 -1 是,执行右单旋
SubL 的平衡因子为 1 时,执行左右双旋
旋转完成后,原 Parent 为根的子树个高度降低,已经平衡,不需要再向上更新。

4.AVL树的验证

AVL 树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证 AVL 树,可以分两步:
        1. 验证其为二叉搜索树
            如果中序遍历可得到一个有序的序列,就说明为二叉搜索树
        2. 验证其为平衡树
            ● 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子 )
            ● 节点的平衡因子是否计算正确
int _size(Node* root)
{return root == nullptr ? 0 : _size(root->_left) + _size(root->_right) + 1;
}int _Height(Node* root)
{if (root == nullptr){return 0;}return max(_Height(root->_left), _Height(root->_right)) + 1;
}bool _IsBalance(Node* root)
{if (root == nullptr){return true;}int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);if (abs(LeftHeight - RightHeight) >= 2){return false;}//可以顺便再检查一下平衡因子if (abs(LeftHeight - RightHeight) != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left) && _IsBalance(root->_right);
}

三、AVL树的性能

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

四、完结撒❀

如果以上内容对你有帮助不妨点赞支持一下,以后还会分享更多编程知识,我们一起进步。
最后我想讲的是,据说点赞的都能找到漂亮女朋友❤

这篇关于C++ AVL树 详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1040104

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量,在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员,因为执行构造函数时,类对象已经创建完成,只有类对象创建完成才能调用成员函数,构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化,该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面,主要用于给