网站里面那些工作是做晚上兼职的,钱包网站建设策划,小程序免费制作平台,区域销售网站什么做个人主页点击直达#xff1a;小白不是程序媛
C系列专栏#xff1a;C干货铺
代码仓库#xff1a;Gitee 目录
前言
AVL树
AVL树的概念
AVL树结点的定义
AVL树的插入
寻找插入结点的位置
修改平衡因子 AVL树的旋转
右单旋
左单旋
先右旋再左旋
先左旋再右旋 AVL树…
个人主页点击直达小白不是程序媛
C系列专栏C干货铺
代码仓库Gitee 目录
前言
AVL树
AVL树的概念
AVL树结点的定义
AVL树的插入
寻找插入结点的位置
修改平衡因子 AVL树的旋转
右单旋
左单旋
先右旋再左旋
先左旋再右旋 AVL树的验证
AVL树的删除了解
AVL树的性能 前言
前面对map/multimap/set/multiset进行了简单的介绍在其文档介绍中发现这几个容器有个 共同点是其底层都是按照二叉搜索树来实现的但是二叉搜索树有其自身的缺陷假如往树中 插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成O(N)因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。 AVL树
AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) AVL树结点的定义
template class k, class v
struct AVLTreeNode
{AVLTreeNodek, v* _left;//指向右孩子AVLTreeNodek, v* _right;//指向左孩子AVLTreeNodek, v* _parent;//键值对pairk, v _kv;//平衡因子int _bf;//构造函数AVLTreeNode(const pairk, v kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
}; AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为三步 1. 按照二叉搜索树的方式插入新节点 2. 调整节点的平衡因子 3. 将插入后不符合的子树进行旋转调整 寻找插入结点的位置
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-_right;}else if (cur -_kv.first kv.first){parent cur; cur cur-_left;}else{//AVL树是基于搜索二叉树的不会存在相等的情况return false;}}//找到要插入的位置进行插入//创建新的结点cur new Node(kv);if (parent-_kv.first kv.first){//大于放右边parent - _right cur;cur-_parent parent;}else{//小于放左边parent-_left cur;cur-_parent parent;}
修改平衡因子
无论是在哪里插入结点二叉树的高度一定会发生变化高度发生变化平衡因子也会发生变化因此要对平衡因子进行修改。 while (parent){//当新增结点为左子树时相当于左子树高度加1//减数不变被减数增加结果减小if (cur parent-_left){parent-_bf--;}else{//当新增结点为右子树时相当于右子树高度加1//减数增加被减数不变结果增大parent-_bf;}//添加后左右子树高度相等//对父节点往上的结点的平衡因子都没有影响if (parent-_bf 0){break;}//添加节点后对树的高度发生变化//继续向上修改平衡//对新增结点的父节点的父节点的平衡因子进行修改else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}} AVL树的旋转
结点的插入必然会影响父代及以上结点的平衡因子从插入结点的父节点往上修改平衡因子一定会出现平衡因子异常超过1/0/-1这时候就要进行旋转操作了。根据插入节点的位置不同AVL树的旋转分为四种。 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);}
右单旋 新节点插入较高左子树的左侧 抽象图 //右单璇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 (parent _root){_root subL;subL-_parent nullptr;}else{//更新父亲节点为旋转结点if (parent parentParent-_left){parentParent-_left subL;}else {parentParent-_right subL;}//更新旋转结点的父亲结点此时选装结点彻底为父亲结点subL-_parent parentParent;}//更新平衡因子subL-_bf parent-_bf 0;}
左单旋 新节点插入较高右子树的右侧 void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* parentParent parent-_parent;parent-_parent subR;if (subRL){subRL-_parent nullptr;}if (parent _root){_root subR;subR-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subR;}else if (parent parentParent-_right){parentParent-_right subR;}subR-_parent parentParent;}parent-_bf subR-_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){// subRL自己就是新增parent-_bf subR-_bf subRL-_bf 0;}else if (bf -1){// subRL的左子树新增parent-_bf 0;subRL-_bf 0;subR-_bf 1;}else if (bf 1){// subRL的右子树新增parent-_bf -1;subRL-_bf 0;subR-_bf 0;}else{assert(false);}}
先左旋再右旋 新节点插入较高左子树的右侧 void RotateLR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;int bf curright-_bf;RotateL(cur);RotateR(parent);if (bf 0){parent-_bf cur-_bf curright-_bf 0;}else if (bf 1){parent-_bf 0;cur-_bf -1;curright-_bf 0;}else if (bf -1){parent-_bf 1;cur-_bf 0;curright-_bf 0;}} AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);} 2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确 int _Height(Node* root){if (root nullptr)return 0;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool _IsBalance(Node* root){if (root nullptr){return true;}int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return abs(rightHeight - leftHeight) 2 _IsBalance(root-_left) _IsBalance(root-_right);} AVL树的删除了解 因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不 错与删除不同的时删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。 具体实现大家可参考《算法导论》或《数据结构-用面向对象方法与C描述》殷人昆版。 AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这 样可以保证查询时高效的时间复杂度即O(log2(n))。但是如果要对AVL树做一些结构修改的操 作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时 有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数 据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。 今天的对数据结构中基于二叉搜索树的AVL树的分享到这里就结束啦如果觉得文章还不错的话可以三连支持一下个人主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是我前进的动力
