免费做网站的问题,网站导航优化的描述,销售管理系统包括哪几大模块,wordpress被屏蔽了api✅1主页#xff1a;我的代码爱吃辣#x1f4c3;2知识讲解#xff1a;数据结构——AVL树☂️3开发环境#xff1a;Visual Studio 2022#x1f4ac;4前言#xff1a;AVL树是对二叉搜索树的严格高度控制#xff0c;所以AVL树的搜索效率很高… ✅1主页我的代码爱吃辣2知识讲解数据结构——AVL树☂️3开发环境Visual Studio 20224前言AVL树是对二叉搜索树的严格高度控制所以AVL树的搜索效率很高但是这是需要付出很大的代价的要维护父亲指针和平衡因子。 目录
一.AVL的概念
二. AVL树节点及整体结构的定义 三. AVL树的插入
1. 先按照二叉搜索树的规则将节点插入到AVL树中
2.根据插入的位置调整平衡因子
四.AVL树的旋转
1.左单旋
2.右单旋
3.左右双旋
4.右左双旋
5.总结
五.AVL树的删除(了解)
六.AVL树的性能
七.完整代码及测试 一.AVL的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O()搜索时间复杂度O()
二. AVL树节点及整体结构的定义
//AVL树结点
templateclass K, class V
struct AVLTreeNode
{AVLTreeNode(pairK,V kv):_kv(kv),_bf(0),_left(nullptr),_right(nullptr),_parent(nullptr){}pairK, V _kv; //Key/Value数据int _bf; //平衡因子AVLTreeNodeK, V* _left; //结点的左子树AVLTreeNodeK, V* _right; //结点的右子树AVLTreeNodeK, V* _parent; //结点的双亲
};//AVL树定义
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool insert(pairK,V kv){}
private:Node* _root nullptr;
}; 三. AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点调整节点的平衡因子
插入过程
1. 先按照二叉搜索树的规则将节点插入到AVL树中 bool insert(pairK,V kv){if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;//记录当前结点Node* parent nullptr;//记录父亲结点while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return false;}}//找到了合适的位置创建新节点出入位置cur new Node(kv);//修改新节点的指向if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//未完待续....}
2.根据插入的位置调整平衡因子 平衡因子右子树高度减去左子树高度。 cur 插入后parent 的平衡因子一定需要调整在插入之前pParent 的平衡因子分为三种情况-10, 1, 分以下两种情况 如果cur插入到parent的左侧只需给parent的平衡因子-1即可如果cur插入到parent的右侧只需给parent的平衡因子1即可
此时parent的平衡因子可能有三种情况0正负1 正负2
如果parent的平衡因子为0说明插入之前parent的平衡因子为正负1插入后被调整成0此时满足 AVL树的性质插入成功。如果parent的平衡因子为正负1说明插入前parent的平衡因子一定为0插入后被更新成正负1此 时以parent为根的树的高度增加需要继续向上更新。如果parent的平衡因子为正负2则parent的平衡因子违反平衡树的性质需要对其进行旋转处理。
while (parent){//cur插入到parent的左侧if (parent-_left cur){parent-_bf--;}else//cur插入到parent的右侧{parent-_bf;}//需向上调整平衡因子if (parent-_bf 1||parent-_bf-1){cur parent;parent cur-_parent;}//无需向上调整平衡因子else if(parent-_bf0){break;}//无需向上调整平衡因子直接旋转处理else if (parent-_bf 2||parent-_bf-2){//旋转,旋转之后平衡因子已经平衡可以直接推出break;}else//出现的其他的错误情况{assert(0);}}
四.AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构 使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种
1.左单旋
新节点插入较高右子树的右侧 上图在插入前AVL树是平衡的新节点插入到60的右子树中30右子树增加了一层导致以60为根的二叉树不平衡要让30平衡只能将30右子树的高度减少一层左子树增加一层即将右子树往上提这样30转下来因为30比60小只能将其放在60的左子树而如果60有左子树左子树根的值一定大于30小于60只能将其放在30的右子树旋转完成后更新节点的平衡因子即可。在旋转过程中有以下几种情况需要考虑
60节点的左孩子可能存在也可能不存在。30可能是整棵树根节点也可能是子树根节点。 如果是整棵树根节点旋转完成后要更整棵树新根节点如果是子树根节点可能是某个节点的左子树也可能是右子树。 void RotateL(Node* parent){// a// b// c//找到需要旋转的结点Node* curR parent-_right;Node* curRL curR-_left;//调整结点并且修改其父亲结点指针parent-_right curRL;if (curRL)//可能为空{curRL-_parent parent;}//在修改子树根节点之前保存子树根节点的父亲Node* pparent parent-_parent;//修改子树根节点curR-_left parent;parent-_parent curR;//子树根节点有可能是整棵树的根节点if (pparent nullptr){_root curR;_root-_parent nullptr;}else//子树根节点不是整棵树的根节点{//还要看子树是它父亲的左孩子还是右孩子if (pparent-_left parent){pparent-_left curR;}else{pparent-_right curR;}curR-_parent pparent;}//修改平衡因子curR-_bf parent-_bf 0;}2.右单旋
新节点插入较高左子树的左侧 右单旋过程和左单旋转过程一模一样仅仅只是反过来。 void RotateR(Node* parent){Node* curL parent-_left;Node* curLR curL-_right;parent-_left curLR;if (curLR){curLR-_parent parent;}Node* pparent parent-_parent;curL-_right parent;parent-_parent curL;if (parent _root){_root curL;_root-_parent nullptr;}else{if (pparent-_left parent){pparent-_left curL;}else{pparent-_right curL;}curL-_parent pparent;}curL-_bf parent-_bf 0;}3.左右双旋
新节点插入较高左子树的右侧---左右先左单旋再右单旋 将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再 考虑平衡因子的更新。
注意旋转之前60的平衡因子可能是 -1 / 0 / 1旋转完成之后根据情况对其他节点的平衡因子进行调整。 当h0,时60自己就是一个新插入的结点此时他的平衡因子就是。
所以旋转之前需要保存curLR的平衡因子旋转完成之后需要根据该平衡因子来调整其他节 点的平衡因子。 void RotateLR(Node* parent){Node* curL parent-_left;Node* curLR curL-_right;//旋转之前保存curLR的平衡因子旋转完成之后//需要根据该平衡因子来调整其他节点的平衡因子int curLR_bf curLR-_bf;//先左单旋RotateL(curL);//再右单旋RotateR(parent);//保存curLR的平衡因子判断插入结点的位置根据插入结点的位置//判断出其他结点的平衡因子if (curLR_bf -1){parent-_bf 1;curLR-_bf 0;curL-_bf 0;}else if (curLR_bf 1){parent-_bf 0;curL-_bf -1;curLR-_bf 0;}else if (curLR_bf 0){parent-_bf 0;curL-_bf 0;curLR-_bf 0;}else{assert(false);}}4.右左双旋
右左双旋和左右双旋过程一模一样仅仅只是反过来。 void RotateRL(Node* parent){Node* curR parent-_right;Node* curRL curR-_left;int curRL_bf curRL-_bf;RotateR(curR);RotateL(parent);if (curRL_bf -1){parent-_bf 0;curRL-_bf 0;curR-_bf 1;}else if (curRL_bf 1){parent-_bf -1;curRL-_bf 0;curR-_bf 0;}else if (curRL_bf 0){parent-_bf 0;curRL-_bf 0;curR-_bf 0;}else{assert(false);}}
5.总结
假如以parent为根的子树不平衡即parent的平衡因子为2或者-2分以下情况考虑 1. parent的平衡因子为2说明parent的右子树高设parent的右子树的根为curR
当curR的平衡因子为1时执行左单旋当curR的平衡因子为-1时执行右左双旋
2. parent的平衡因子为-2说明parent的左子树高设parent的左子树的根为curL
当curL的平衡因子为-1是执行右单旋当curL的平衡因子为1时执行左右双旋
旋转完成后原parent为根的子树个高度降低已经平衡不需要再向上更新。 //调整平衡因子while (parent){if (parent-_left cur){parent-_bf--;}else{parent-_bf;}if (parent-_bf 1||parent-_bf-1)//需向上调整平衡因子{cur parent;parent cur-_parent;}else if(parent-_bf0)//无需向上调整平衡因子{break;}else if (parent-_bf 2||parent-_bf-2)//无需向上调整平衡因子直接旋转{if (parent-_bf 2 parent-_right-_bf 1){RotateL(parent);//左单旋}else if (parent-_bf -2 parent-_left-_bf -1){RotateR(parent);//右单旋}else if (parent-_bf 2 parent-_left-_bf -1){RotateRL(parent);//右左双旋}else if (parent-_bf -2 parent-_left -_bf 1){RotateLR(parent);//左右双旋}else{assert(false);//其他错误情况}break;}else{assert(0);}
五.AVL树的删除(了解)
因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不 错与删除不同的时删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。 具体实现学生们可参考《算法导论》或《数据结构-用面向对象方法与C描述》殷人昆版。
六.AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这 样可以保证查询时高效的时间复杂度即。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
七.完整代码及测试 AVL.hpp #pragma once
#includeiostream
#includecassert
using namespace std;templateclass K, class V
struct AVLTreeNode
{AVLTreeNode(pairK,V kv):_kv(kv),_bf(0),_left(nullptr),_right(nullptr),_parent(nullptr){}pairK, V _kv; //Key/Value数据int _bf; //平衡因子AVLTreeNodeK, V* _left; //结点的左子树AVLTreeNodeK, V* _right; //结点的右子树AVLTreeNodeK, V* _parent; //结点的双亲
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool insert(pairK,V kv){if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return false;}}//找到了合适的位置cur new Node(kv);//if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//调整平衡因子while (parent){if (parent-_left cur){parent-_bf--;}else{parent-_bf;}if (parent-_bf 1||parent-_bf-1)//需向上调整平衡因子{cur parent;parent cur-_parent;}else if(parent-_bf0)//无需向上调整平衡因子{break;}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 if (parent-_bf -2 cur -_bf 1){RotateLR(parent);//左右双旋}else{//cout parent-_bf : /*parent-_left-_bf : */ parent-_right-_bf endl;assert(false);//其他错误情况}break;}else{assert(false);}}return true;}void Inorder(){_inorder(_root);cout endl;}private:void _inorder(Node* root){if (root nullptr){return;}_inorder(root-_left);cout root-_kv.first ;_inorder(root-_right);}void RotateL(Node* parent){// a// b// c//找到需要旋转的结点Node* curR parent-_right;Node* curRL curR-_left;//调整结点并且修改其父亲结点指针parent-_right curRL;if (curRL)//可能为空{curRL-_parent parent;}//在修改子树根节点之前保存子树根节点的父亲Node* pparent parent-_parent;//修改子树根节点curR-_left parent;parent-_parent curR;//子树根节点有可能是整棵树的根节点if (pparent nullptr){_root curR;_root-_parent nullptr;}else//子树根节点不是整棵树的根节点{//还要看子树是它父亲的左孩子还是右孩子if (pparent-_left parent){pparent-_left curR;}else{pparent-_right curR;}curR-_parent pparent;}//修改平衡因子curR-_bf parent-_bf 0;}void RotateR(Node* parent){Node* curL parent-_left;Node* curLR curL-_right;parent-_left curLR;if (curLR){curLR-_parent parent;}Node* pparent parent-_parent;curL-_right parent;parent-_parent curL;if (parent _root){_root curL;_root-_parent nullptr;}else{if (pparent-_left parent){pparent-_left curL;}else{pparent-_right curL;}curL-_parent pparent;}curL-_bf parent-_bf 0;}void RotateLR(Node* parent){Node* curL parent-_left;Node* curLR curL-_right;//旋转之前保存pSubLR的平衡因子旋转完成之后//需要根据该平衡因子来调整其他节点的平衡因子int curLR_bf curLR-_bf;//RotateL(curL);RotateR(parent);if (curLR_bf -1){parent-_bf 1;curLR-_bf 0;curL-_bf 0;}else if (curLR_bf 1){parent-_bf 0;curL-_bf -1;curLR-_bf 0;}else if (curLR_bf 0){parent-_bf 0;curL-_bf 0;curLR-_bf 0;}else{assert(false);}}void RotateRL(Node* parent){Node* curR parent-_right;Node* curRL curR-_left;int curRL_bf curRL-_bf;RotateR(curR);RotateL(parent);if (curRL_bf -1){parent-_bf 0;curRL-_bf 0;curR-_bf 1;}else if (curRL_bf 1){parent-_bf -1;curRL-_bf 0;curR-_bf 0;}else if (curRL_bf 0){parent-_bf 0;curRL-_bf 0;curR-_bf 0;}else{assert(false);}}Node* _root nullptr;
}; test.cpp #define _CRT_SECURE_NO_WARNINGS 1
#includeAVL.hpp
int main()
{int arr1[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int arr2[] {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};AVLTreeint, int a1;AVLTreeint, int a2;for (auto e : arr1){a1.insert(make_pair(e,e));}a1.Inorder();for (auto e : arr2){a2.insert(make_pair(e, e));}a2.Inorder();
}
