永康市建设银行网站查询,异地网站建设公司,wordpress 改cms,馨端网站建设文章目录前言一、概念二、AVL树结点的定义三、AVL树的插入四、AVL树的旋转1.右单旋的情况以及具体操作抽象图h 0h 1h 2代码实现2.左单旋的情况以及具体操作抽象图代码实现3.右左双旋的情况以及具体操作抽象图h 0h 1h 23.左右双旋的情况以及具体操作抽象图5.总结6.完整实现…
文章目录前言一、概念二、AVL树结点的定义三、AVL树的插入四、AVL树的旋转1.右单旋的情况以及具体操作抽象图h 0h 1h 2代码实现2.左单旋的情况以及具体操作抽象图代码实现3.右左双旋的情况以及具体操作抽象图h 0h 1h 23.左右双旋的情况以及具体操作抽象图5.总结6.完整实现代码7.验证概念主程序代码8.性能总结前言
前面我们介绍了STL中的关联式容器map/set/multimap/mutiset等我们可以发现它们的底层都是按照二叉搜索树来实现的但是二叉搜索树自身有一些缺陷当往二叉搜索树中插入的元素有序或者接近有序二叉搜索树就会退化为单支其检索的时间复杂度就会退化为O(n)。因此map、set等关联式容器的底层结构是对搜索二叉树进行平衡处理的平衡二叉搜索树。 本节我们就来了解平衡搜索二叉树AVL树的相关概念。 一、概念
普通的搜索二叉树一旦数据有序或者接近有序就会造成二叉搜索树退化为单支两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法 **当向二叉搜索树中插入新结点后如果能保证每个节点的左右子树高度之差不超过1需要对树中结点进行调整**即可降低树的高度从而减少平均搜索长度。 一棵AVL树要具有以下性质
该树如果是空树那么它是AVL树它的左右子树是AVL树左右子树的高度差命名为平衡因子的绝对值不超过1可以是1/0/-1 上图的红色标识的是该结点的平衡因子这里的平衡因子使用右子树的高度减左子树的高度计算的。 如果一棵二叉搜索树是高度平衡的那么他就是AVL树。 假设该树有n个结点其高度应保持在O(log2n)O(log_2 n)O(log2n)搜索时间复杂度为O(log2nlog_2 nlog2n。
二、AVL树结点的定义 templateclass K,class Vstruct AVLnode//三叉链{pairK, V _kv;AVLnode(const pairK,V kv):_kv(kv), _bf(0), _pleft(nullptr), _pright(nullptr), _pparent(nullptr){}AVLnodeK, V* _pleft;//左孩子AVLnodeK, V* _pright;//右孩子AVLnodeK, V* _pparent;//双亲结点int _bf;//平衡因子};三、AVL树的插入
实际上AVL树就是在二叉搜索树的基础上增加了平衡因子因此AVL树的插入可以分为两步
按照二叉搜索树的插入方式插入新结点调整结点的平衡因子 bool insert(const pairK,V kv){//1.按照二叉搜索树的规则将节点插入到AVL树中node* newnode new node(kv);node* cur _root;if (_root nullptr)//如果该树为空树直接插入新节点此时新节点是该树的根节点{_root newnode;return true;}node* prev nullptr;while (cur){prev cur;if (cur-_kv.first data){cur cur-_pleft;}else if (cur-_kv.first data){cur cur-_pright;}else return false;//树中已经存在该元素插入失败}if (prev-_kv.first data){prev-_pleft newnode;newnode-_pparent prev;}else{prev-_pright newnode;newnode-_pparent prev;}node* pParent prev;cur newnode;//2.对结点的平衡因子进行更新并检测新插入的结点是否破坏了AVL树的平衡性//调节平衡因子在插入新结点前pparent的平衡因子有以下三种情况-1, 0, 1//如果cur插在pparent的左边给pparent的结点的平衡因子-1//如果cur插在pparent的右边给pparent的结点的平衡因子1//此时pparent的平衡因子有以下三种情况0±1±2//pparent平衡因子为0说明新插入结点不影响该子树的高度满足AVL树的性质不再进行调整//pparent平衡因子为±1说明插入前pparent的平衡因子为0此时以pparent为根的子树的高度加1需要继续向上更新平衡因子//pparent平衡因子为±2说明插入前pparent的平衡因子为±1此时pparent的平衡因子违反了AVL树的性质需要进行旋转操作while (pParent)//当pParent为空时pParent就是根节点的父节点就不需要再进行调整了{//更新父节点的平衡因子if (cur pParent-_pleft){pParent-_bf--;}else if (cur pParent-_pright){pParent-_bf;}//检测更新后的平衡因子if (0 pParent-_bf)//该子树的高度没变化不用调整{break;}else if (1 pParent-_bf || -1 pParent-_bf)//该子树的高度增加了1因此要继续向上调整平衡因子{cur pParent;pParent pParent-_pparent;}//3.破坏了AVL树的平衡性我们就要对以pparent为根的子树就地旋转处理//旋转的目的//1)让这棵子树的左右高度差不超过1//2旋转过程中保持它是搜索树//3更新旋转后的平衡因子//4让这棵树的高度与插入前保持一致不会继续影响上层不用继续向上调整else if (2 pParent-_bf || -2 pParent-_bf){//右单旋//我的平衡因子为-1父节点的平衡因子为-2.if (-2 pParent-_bf -1 cur-_bf){RotateR(pParent);//更新平衡因子cur-_bf 0;pParent-_bf 0;}//左单旋else if (2 pParent-_bf 1 cur-_bf){RotateL(pParent);//更新平衡因子cur-_bf 0;pParent-_bf 0;}//左右双旋else if (-2 pParent-_bf 1 cur-_bf){node* SubR cur-_pright;RotateL(cur);RotateR(pParent);//更新平衡因子//新增结点就是SubRif (SubR -_bf 0){cur-_bf 0;pParent-_bf 0;}//新增结点在SubR结点的左子树else if (SubR-_bf -1){SubR-_bf cur-_bf 0;pParent-_bf 1;}//新增结点在SubR结点的右子树else if (SubR-_bf 1){SubR-_bf pParent-_bf 0;cur-_bf -1;}else{assert(false);}}//右左双旋else if (2 pParent-_bf -1 cur-_bf){node* SubL cur-_pleft;RotateR(cur);RotateL(pParent);//更新平衡因子//新增结点就是SubLif (SubL-_bf 0){cur-_bf 0;pParent-_bf 0;}//新增结点在SubL结点的左子树else if (SubL -_bf -1){SubL-_bf pParent-_bf 0;cur-_bf 1;}//新增结点在SubL结点的右子树else if (SubL-_bf 1){SubL-_bf cur-_bf 0;pParent-_bf -1;}else{assert(false);}}return true;}else//如果以上的程序哪里出现问题就会直接报错{assert(false);}}return true;}private:AVLnodeT* _root;};四、AVL树的旋转
1.右单旋的情况以及具体操作
抽象图
先看如下的抽象图 图中a,b,c是高度为h的子树红色数字是插入前该节点的平衡因子。 新增结点导致要向上更新平衡因子如果父节点的平衡因子为-2且当前结点的平衡因子为-1时我们就要进行右单旋。 那么如何进行右单旋呢旋转处理之后平衡因子又是如何更新的呢 要由具体的解决方法推出抽象的解决方法因此下面我们具体分析当h分别为0/1/2时我们的解决方法
h 0 如图当h 0时在a处新增节点按照图中步骤使用右单旋对该子树进行调整最后更新平衡因子即可。
h 1 如图当h 1时在a结点的左右子结点任意一个位置新增节点按照图中步骤使用右单旋对该子树进行调整最后更新平衡因子即可。
h 2 如图当h 2时在a子树的i/j/m/n等四个位置的任意一个位置新增节点按照图中步骤使用右单旋对该子树进行调整最后更新平衡因子即可。 总结根据以上三种情况我们可以得出新增节点向上调整平衡因子的过程中如果出现父节点的平衡因子为-2当前结点的平衡因子为-1的情况就以父节点为轴进行右单旋之后更新父节点和当前结点的平衡因子为0即可。
代码实现 //左单旋(父节点平衡因子为2右孩子平衡因子为1void RotateL(node* parent){node* SubR parent-_pright;node* SubRL SubR-_pleft;node* Grandpa parent-_pparent;//祖父parent-_pright SubRL;if (SubRL){SubRL-_pparent parent;}SubR-_pleft parent;parent-_pparent SubR;SubR-_pparent Grandpa;//更新祖父的孩子结点if (Grandpa nullptr)//pParent此时是根节点{_root SubR;//更新cur为根节点_root -_pparent nullptr;}else{if (parent Grandpa-_pleft){Grandpa-_pleft SubR;}else{Grandpa-_pright SubR;}}}2.左单旋的情况以及具体操作
抽象图 图中a,b,c是高度为h的子树红色数字是插入前该节点的平衡因子。 新增结点导致要向上更新平衡因子如果父节点的平衡因子为2且当前结点的平衡因子为1时我们就要进行左单旋。 左单旋与右单旋的方法类似没有特殊情况因此这里只介绍当h 0时的情况 当h 0时在c位置新增结点 可以看出当父节点为2且当前结点为1时需要以父节点为轴进行左单旋最后更新平衡因子。
代码实现 //右单旋(父节点平衡因子为-2左孩子平衡因子为-1void RotateR(node* parent){node* SubL parent-_pleft;node* SubLR SubL-_pright;node* Grandpa parent-_pparent;//祖父parent-_pparent SubL;SubL-_pright parent;parent-_pleft SubLR;if (SubLR)SubLR-_pparent parent;SubL-_pparent Grandpa;//更新祖父的孩子结点if (Grandpa nullptr)//pParent此时是根节点{_root SubL;SubL-_pparent nullptr;}else{if (parent Grandpa-_pleft){Grandpa-_pleft SubL;}else{Grandpa-_pright SubL;}}}3.右左双旋的情况以及具体操作
我们设定结点值为30的结点是parent结点值为90的结点是pR,结点值为60的结点是pRL起名字后方便操作
抽象图
右左双旋的抽象图其中a/d是高度为h的子树b/c是高度为h-1的子树 先以pR结点为轴进行右单旋再以parent结点为轴进行左单旋最后更新平衡因子即可。
h 0 h 1
如果在b处新增结点在60的左子树新增结点
旋转后平衡因子的更新如下 30结点的平衡因子为0 60结点的平衡因子为0 90结点的平衡因子为-1.
如果在c处新增结点在60的右子树新增结点
旋转后平衡因子的更新如下 30结点的平衡因子为0 60结点的平衡因子为0 90结点的平衡因子为-1.
h 2
在60的左右子树新增节点导致的旋转后的平衡因子的更新情况与h 1时是一致的因此只简单介绍在e处新增的情况。
3.左右双旋的情况以及具体操作
我们设定结点值为90的结点是parent结点值为30的结点是pL,结点值为60的结点是pLR起名字后方便操作
抽象图 先以pL结点为轴进行左单旋再以parent结点为轴进行右单旋最后更新平衡因子即可。 如果新增的节点就是60那么旋转后的平衡因子更新如下 30结点/60结点/90结点的平衡因子都为0 如果新增的节点在60结点的左子树那么旋转后的平衡因子更新如下 30结点的平衡因子为1 60结点的平衡因子为0 90结点的平衡因子为0。 如果新增的节点在60结点的右子树那么旋转后的平衡因子更新如下 30结点的平衡因子为0 60结点的平衡因子为0 90结点的平衡因子为-1。 左右双旋与右左双旋类似可以参考理解这里就不多赘述了。
5.总结
假如以parent为根的子树不平衡即parent的平衡因子为2/-2有以下几种情况
parent的平衡因子为2说明parent的右子树高设parent的右子树的根节点为pR
当pR的平衡因子为1时执行左单旋当pR的平衡因子为-1时执行右左双旋。
parent的平衡因子为-2说明parent的左子树高设parent的左子树的根节点为pL
当pL的平衡因子为-1执行右单旋当pL的平衡因子为1执行左右双旋。
旋转结束后原parent为根的子树高度已平衡不需要再向上更新。
6.完整实现代码
namespace Jinger
{templateclass K,class Vstruct AVLnode//三叉链{pairK, V _kv;AVLnode(const pairK,V kv):_kv(kv), _bf(0), _pleft(nullptr), _pright(nullptr), _pparent(nullptr){}AVLnodeK, V* _pleft;//左孩子AVLnodeK, V* _pright;//右孩子AVLnodeK, V* _pparent;//双亲结点int _bf;//平衡因子};templateclass K, class Vstruct AVLTree{typedef AVLnodeK, V node;AVLTree():_root(nullptr){}//左单旋(父节点平衡因子为2右孩子平衡因子为1void RotateL(node* parent){node* SubR parent-_pright;node* SubRL SubR-_pleft;node* Grandpa parent-_pparent;//祖父parent-_pright SubRL;if (SubRL){SubRL-_pparent parent;}SubR-_pleft parent;parent-_pparent SubR;SubR-_pparent Grandpa;//更新祖父的孩子结点if (Grandpa nullptr)//pParent此时是根节点{_root SubR;//更新cur为根节点_root -_pparent nullptr;}else{if (parent Grandpa-_pleft){Grandpa-_pleft SubR;}else{Grandpa-_pright SubR;}}}//右单旋(父节点平衡因子为-2左孩子平衡因子为-1void RotateR(node* parent){node* SubL parent-_pleft;node* SubLR SubL-_pright;node* Grandpa parent-_pparent;//祖父parent-_pparent SubL;SubL-_pright parent;parent-_pleft SubLR;if (SubLR)SubLR-_pparent parent;SubL-_pparent Grandpa;//更新祖父的孩子结点if (Grandpa nullptr)//pParent此时是根节点{_root SubL;SubL-_pparent nullptr;}else{if (parent Grandpa-_pleft){Grandpa-_pleft SubL;}else{Grandpa-_pright SubL;}}}bool insert(const pairK,V kv){//1.按照二叉搜索树的规则将节点插入到AVL树中node* newnode new node(kv);node* cur _root;if (_root nullptr)//如果该树为空树直接插入新节点此时新节点是该树的根节点{_root newnode;return true;}node* prev nullptr;while (cur){prev cur;if (cur-_kv.first kv.first){cur cur-_pleft;}else if (cur-_kv.first kv.first){cur cur-_pright;}else return false;//树中已经存在该元素插入失败}if (prev-_kv.first kv.first){prev-_pleft newnode;newnode-_pparent prev;}else{prev-_pright newnode;newnode-_pparent prev;}node* pParent prev;cur newnode;//2.对结点的平衡因子进行更新并检测新插入的结点是否破坏了AVL树的平衡性//调节平衡因子在插入新结点前pparent的平衡因子有以下三种情况-1, 0, 1//如果cur插在pparent的左边给pparent的结点的平衡因子-1//如果cur插在pparent的右边给pparent的结点的平衡因子1//此时pparent的平衡因子有以下三种情况0±1±2//pparent平衡因子为0说明新插入结点不影响该子树的高度满足AVL树的性质不再进行调整//pparent平衡因子为±1说明插入前pparent的平衡因子为0此时以pparent为根的子树的高度加1需要继续向上更新平衡因子//pparent平衡因子为±2说明插入前pparent的平衡因子为±1此时pparent的平衡因子违反了AVL树的性质需要进行旋转操作while (pParent)//当pParent为空时pParent就是根节点的父节点就不需要再进行调整了{//更新父节点的平衡因子if (cur pParent-_pleft){pParent-_bf--;}else if (cur pParent-_pright){pParent-_bf;}//检测更新后的平衡因子if (0 pParent-_bf)//该子树的高度没变化不用调整{break;}else if (1 pParent-_bf || -1 pParent-_bf)//该子树的高度增加了1因此要继续向上调整平衡因子{cur pParent;pParent pParent-_pparent;}//3.破坏了AVL树的平衡性我们就要对以pparent为根的子树就地旋转处理//旋转的目的//1)让这棵子树的左右高度差不超过1//2旋转过程中保持它是搜索树//3更新旋转后的平衡因子//4让这棵树的高度与插入前保持一致不会继续影响上层不用继续向上调整else if (2 pParent-_bf || -2 pParent-_bf){//右单旋//我的平衡因子为-1父节点的平衡因子为-2.if (-2 pParent-_bf -1 cur-_bf){RotateR(pParent);//更新平衡因子cur-_bf 0;pParent-_bf 0;}//左单旋else if (2 pParent-_bf 1 cur-_bf){RotateL(pParent);//更新平衡因子cur-_bf 0;pParent-_bf 0;}//左右双旋else if (-2 pParent-_bf 1 cur-_bf){node* SubR cur-_pright;RotateL(cur);RotateR(pParent);//更新平衡因子//新增结点就是SubRif (SubR -_bf 0){cur-_bf 0;pParent-_bf 0;}//新增结点在SubR结点的左子树else if (SubR-_bf -1){SubR-_bf cur-_bf 0;pParent-_bf 1;}//新增结点在SubR结点的右子树else if (SubR-_bf 1){SubR-_bf pParent-_bf 0;cur-_bf -1;}else{assert(false);}}//右左双旋else if (2 pParent-_bf -1 cur-_bf){node* SubL cur-_pleft;RotateR(cur);RotateL(pParent);//更新平衡因子//新增结点就是SubLif (SubL-_bf 0){cur-_bf 0;pParent-_bf 0;}//新增结点在SubL结点的左子树else if (SubL -_bf -1){SubL-_bf pParent-_bf 0;cur-_bf 1;}//新增结点在SubL结点的右子树else if (SubL-_bf 1){SubL-_bf cur-_bf 0;pParent-_bf -1;}else{assert(false);}}return true;}else//如果以上的程序哪里出现问题就会直接报错{assert(false);}}return true;}//获取根节点node* Getroot(){return _root;}private:node* _root;};
}7.验证
概念
AVL树是在搜索二叉树的基础上加入了平衡因子的限制因此要验证AVL树可以分为以下两个步骤
验证其是否为搜索二叉树验证其是否为平衡树平衡因子
每个结点子树高度差的绝对值不超过1判断结点中的平衡因子计算是否正确
验证用例 一般情况仅进行单旋
{16, 3, 7, 11, 9, 26, 18, 14, 15}特殊情况进行双旋
{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}主程序代码
下面是测试用的主程序代码大家可以用它来检验AVL树实现代码的正确性
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
using namespace std;
#includevector
#includealgorithm
#includeassert.h
#includeAVL.h
int _Height(Jinger::AVLnodeint,int* pRoot)//计算树的最大高度
{if (pRoot nullptr) return 0;return 1 max(_Height(pRoot-_pleft), _Height(pRoot-_pright));
}
bool _IsBalanceTree(Jinger::AVLnodeint,int* pRoot)
{// 空树也是AVL树if (nullptr pRoot) return true;// 计算pRoot节点的平衡因子即pRoot左右子树的高度差int leftHeight _Height(pRoot-_pleft);int rightHeight _Height(pRoot-_pright);int diff rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等或者pRoot平衡因子的绝对值超过1则一定不是AVL树if (diff ! pRoot-_bf || (diff 1 || diff -1))return false;// pRoot的左和右如果都是AVL树则该树一定是AVL树return _IsBalanceTree(pRoot-_pleft) _IsBalanceTree(pRoot -_pright);
}
int main()
{Jinger::AVLTreeint,int tree;vectorint v{ 16, 3, 7, 11, 9, 26, 18, 14, 15};//vectorint v{ 4, 2, 6, 1, 3, 5, 15, 7, 16, 14};for (auto it : v){cout it ;tree.insert(make_pair(it,it));}int a 0;bool ret _IsBalanceTree(tree.Getroot());if (ret 0) cout 该树不是AVL树 endl;else cout 该树是AVL树 endl;return 0;
}8.性能
AVL树是一棵绝对平衡的搜索二叉树它要求每个结点的左右子树的高度差的绝对值不超过1这样可以保证查询时的时间复杂度log2(N)log_2(N)log2(N))。但是如果对AVL树做一些结构修改的操作它的性能就会比较低下例如插入元素时要维护其绝对平衡的性质旋转的次数会比较多。其中删除的效果最差有可能让旋转一直持续到根节点。 因此如果需要一种查询高效且有序的数据结构并且数据结构的个数为静态的不会发生改变可以考虑使用AVL树但是如果该结构需要经常被修改AVL树就不太适合了。 总结
以上就是今天要讲的内容本文介绍了C中的AVL树的相关概念。本文作者目前也是正在学习C相关的知识如果文章中的内容有错误或者不严谨的部分欢迎大家在评论区指出也欢迎大家在评论区提问、交流。 最后如果本篇文章对你有所启发的话希望可以多多支持作者谢谢大家
