首页
学习
活动
专区
圈层
工具
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

C++:AVL树

AVL树概念 AVL树是一种具有特殊性质的二叉搜索树,AVL树的左右子树也都是AVL树,且左右子树的高度差的绝对值不超过1,超过1就说明AVL树失衡,需要调整。...AVl树是一颗高度平衡的二叉搜索树,通过高度控制高度差去控制平衡。...AVL树整体节点和分布与完全二叉树类似,高度控制在logN范围内,那么增删查改的效率也可以控制在O(logN),相比二叉搜索树有了本质提升。 以下这棵树就是AVL树。...向AVL树插入新节点的过程与二叉搜索树的插入类似,但有区别的是,插入新节点后需要更新平衡因子,然后根据平衡因子的情况判断AVL树是否失衡,失衡就对AVL树进行调整。...左单旋其实就是从树的左边将树逆时针旋转。

15310

C++:AVL树

AVL树,即是高度平衡的二叉搜索树。 一棵AVL树是一棵平衡二叉搜索树,也能是一棵空树。...AVL树的性质: ①它的左右子树都是AVL树 ②左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) ③如果一棵二叉搜索树是高度平衡的,它就是AVL树。...AVL树的定义: AVL树的定义中:①拥有键值对。②多加一个双亲节点,用于调整平衡二叉树。③增加平衡因子,用于判断插入或删除后,是否还是一棵AVL树。...即图中的b子树 { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1)//说明是在右子树c上新增节点...验证AVL树 由于AVL树是在二叉搜索树的基础上加了平衡性后得到的树,因此需要确认一棵树是AVL树,那么就需要以下两步: 1.先确定是否是一棵二叉搜索树:如果中序遍历可得到一个有序的序列,就说明为二叉搜索树

41530
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    【c++】AVL树

    目录 1.AVL树的介绍 2.构建AVL树 2.1节点构建 2.2 AVL树的插入 2.3AVL树的旋转 左左:右单旋 右右:左单旋 左右:先左单旋再右单旋 右左:先右单旋再左单旋 完善插入函数: 2.4...其他函数 1.AVL树的介绍 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查 找元素相当于在顺序表中搜索元素,效率低下 当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过...1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度 一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树: 它的左右子树都是AVL树 左右子树高度之差==(简称平衡因子)的绝对值不超过...左左:右单旋 新节点插入较高左子树的左侧,我们进行右单旋 30c,我们在这里调节位置关系,调节后平衡因子均为0 void RotateR(Node*parent) { Node* subL...->_bf = subL->_bf = 0; 最后,由于这里 parent 和 subL 的平衡因子都恢复到平衡状态,更新它们的平衡因子为 0 这里插入情况很多 右右:左单旋 30c

    9000

    【C++】AVL树

    底层结构 前面对map/multimap/set/multiset进行了简单的介绍: 【C++】map和set ,在其文档介绍中发现,这几个容器有个共同点是:其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷...h==1: 在20的左边或者右边新增都会引发旋转 h==2 高度为2的AVL树有三种: b和c是x/y/z中的任意一种 a只能是z这种情况,如果a是x这种情况: 那么当a插入一个节点...,而插入可以选择4个节点中任何一个,所以 h==3 高度为3最满的就是下面这样,4个节点可能是满的C44,四个节点中任意选三,四个节点中任意选两个,四个节点中任意选一个,这些都可能是高度为h的情况...根据节点插入位置的不同,AVL树的旋转分为四种: 新节点插入较高左子树的左侧—左左:右单旋(左边高,往右边压) b变成60的左边,30c子树 所以当h==1时候,也是同样的右边压...= ppNode; } parent->_bf = subL->_bf = 0; } 新节点插入较高右子树的右侧—右右:左单旋 现在右边高,让subRL变成30的右边,30c:

    13510

    【C++】AVL树

    AVL树 一、AVL树概念 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。...当新插入节点在较高右子树的右侧,即在 c 子树的位置插入;以上这个图叫做抽象图,因为情况太多了画不完,所以用抽象图表示更为直观;要在 c 子树插入引起旋转,那么 c 一定为高度为 h 的满AVL树或者空树...我们在 c 子树插入节点,导致以 30 为根的二叉树不平衡,要让它平衡,只能想办法让右子树的高度减少一层,左子树的高度增加一层;即将 60 往上提,30 旋转下来;因为 60 比 30 大,所以 60...如下图所示: 因为我们只能从 b 或 c 子树插入新节点,那么我们怎么区分它在哪里插入的呢?...通过观察我们可以发现,在 b 或者 c 子树插入新节点,一定会影响 subLR;所以分为以下三种情况: 当在 subLR 的左子树插入, subLR 的 _bf 就变成了 -1;此时旋转完成后,parent

    16410

    【C++】AVL树

    目录 一、概念 二、原理及实现 1.定义 2.插入 1)更新平衡因子 2)旋转 三、性能分析 ---- 一、概念 二叉搜索树虽可以缩短查找的效率,但 如果数据有序或接近有序二叉搜索树将退化为单支树,查...1( 需要对树中的结点进行调整 ) ,即可降低树的高度,从而减少平均搜索长度。...一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树: 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的,它就是 AVL...树。...K和V详情参考:二叉搜索树 2.插入 AVL 树就是在二叉搜索树的基础上引入了平衡因子,因此 AVL 树也可以看成是二叉搜索树。

    33830

    C++——AVL树

    概念 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。...1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。...一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树: 它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 右子树高度-左子树高度=平衡因子 这棵树是平衡的...}; 旋转 旋转的目的; 1.让这棵树的左右树高度差不超过1 2.旋转之后也要保持这棵树是AVL树 3.更新调节平衡因子 4.旋转后的高度要和插入前相同 左单旋与右单旋 左单旋: 对于左单旋这张图针对的是很多种情况...验证AVL树 这里还需要加一个平衡因子的判断; int _Height(Node* root)//计算树的高度 { if (root == nullptr) return 0; int

    27320

    【C++】树(Tree)

    堆排序的实现基础是树,在此之前我们需要先了解堆,在了解堆之前先来了解下树。 树的概念 跟我们生活中的树一样,都是由根和节点构成的。像这样的,最下面的是根部,然后向上依次是枝条和叶子。...树的基本术语 如图,是一棵树,凡是在下一层有分支的节点都叫做根节点,例如A是B/C/D的根节点,B是E/F的根节点,根节点也叫做父节点,父节点下面连接的那一行节点叫做孩子节点,同一层的节点称为兄弟节点,...完全二叉树 像这样的出最后一层之外都是满的,最后一层节点都是紧挨着的叫做完全二叉树, 满二叉树 顾名思义,满二叉树就是满的,除了最后一层其余节点度数都是2,最后一层的节点的度数是1; 手搓二叉树 实现二叉树的各项功能前我们现在创建一个二叉树...二叉树的遍历 二叉树的遍历分为4种,前序遍历,中序遍历,后序遍历,层序遍历。...0 : max(TreeHeight(root->left), TreeHeight(root->right))+1; } 树的高度等于子树中的较大的高度+1; 判断是否是完全二叉树 // 判断二叉树是否是完全二叉树

    16010

    C++【AVL树】

    ---- 前言 普通的二叉搜索树可能会退化为单支树(歪脖子树),导致搜索性能严重下降,为了解决这个问题,诞生了平衡二叉搜索树,主要是通过某些规则判断后,降低二叉树的高度,从而避免退化,本文介绍的 AVL...树就属于其中一种比较经典的平衡二叉搜索树,它是通过 平衡因子 的方式来降低二叉树高度的,具体怎么操作,可以接着往下看 ---- ️正文 1、认识AVL树 AVL 树由 前苏联 的两位数学家:G.M.Adelson-Velskii...树在原 二叉搜索树 的基础上添加了 平衡因子 bf 以及用于快速向上调整的 父亲指针 parent,所以 AVL 树是一个三叉链结构 所以 AVL 树的节点通过代码定义如下: //AVL树的节点类(...树差不多,但又没有那么严格 的 平衡二叉搜索树 了 而这种 平衡二叉搜索树 就是数据结构中大名鼎鼎的大哥:红黑树,关于 红黑树 的天才设计将在下文中介绍,值得一提的是 红黑树在减少旋转次数的同时,还能做到与...AVL 树的差距至多不超过 2 倍,这是非常牛叉的设计,依赖于 颜色:红 与 黑 本文中涉及的代码:《AVL 树博客》 ---- 总结 以上就是本次关于 C++【AVL树】的全部内容了,在本文中,我们首先了解了什么是

    18920

    【C++】AVL树

    2.3.2右单旋 • 本图1展⽰的是10为根的树,有a/b/c抽象为三棵⾼度为h的⼦树(h>=0),a/b/c均符合AVL树的要 求。...这⾥a/b/c是⾼度为h的⼦树, 是⼀种概括抽象表⽰,他代表了所有右单旋的场景,实际右单旋形态有很多种,具体图2/图3/图4/ 图5进⾏了详细描述。...有a/b/c抽象为三棵⾼度为h的⼦树(h>=0),a/b/c均符合AVL树的要 求。...这⾥a/b/c是⾼度为h的⼦树, 是⼀种概括抽象表⽰,他代表了所有右单旋的场景,实际右单旋形态有很多种,具体跟上⾯左旋类 似。...图7和图8分别为左右双旋中h==0和h==1具体场景分析,下⾯我们将a/b/c⼦树抽象为⾼度h的AVL ⼦树进⾏分析,另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树,因为

    13010

    【C++】AVL树

    AVL树的概念 1. AVL树是一种 自平衡二叉搜索树,具有以下性质: 空树性质:一棵AVL树可以是空树。...递归性质:如果非空,则AVL树满足以下条件: 左右子树均为AVL树。 左右子树的高度差(即平衡因子)的绝对值不超过1。 2....AVL树整体结点数量和分布与完全二叉树类似,高度可以控制在log(N),那么增删查改的效率也可以控制在log(N),相比二叉搜索树有了本质的提升。 AVL树的插入 整体的插入规则 1....先按 二叉搜索树规则 进行插入。 2. 新增结点只会影响祖先结点的高度 ,也就是可能会影响部分祖先结点的平衡因子。...保持二叉搜索树性质的前提下,让旋转的树从不平衡变平衡。 3. 旋转总共分为四种, 左单旋 、 右单旋 、 左右双旋 、 右左双旋 。

    8010

    【C++】红黑树

    今日更新了红黑树的相关内容 欢迎大家关注点赞收藏⭐️留言 红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。...最长路径<=最短路径*2 (最长路径就是一红一黑间隔,最短路径就是全黑) 节点的定义 红黑树的插入操作 红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步: 按照二叉搜索的树规则插入新节点...如果x==1,c/d/e就是m/n/p/q四种组合之一。此时新增节点的位置就是a和b的孩子之一。 方法跟上面x==0的情况一样。...AVL树的比较 红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(logN),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数, 所以在经常进行增删的结构中性能比...AVL树更优,而且红黑树实现比较简单,所以实际运用中红 黑树更多。

    9110

    C++实现AVL树

    为什么要有AVL树 我们都知道二叉搜索树的规则,插入一个节点时,如果比当前节点值大就到右边,反之则到左边。这样使得中序遍历这颗树可以得到一个有序的数组。...1.AVL树 AVL树是具有以下性质的二叉搜索树: 1.它的左右子树都是AVL树 2.左右子树高度之差(简称平衡因子)的绝对值不超过1. 如果一颗二叉搜索树是高度平衡的。那么它就是AVL树。...AVL树的插入可以说是AVL树最重要的内容,不过因为AVL树是再二叉平衡树的基础上加入了平衡因子,所以最开始的插入操作和二叉平衡树是相同的。...,先进行的二叉搜索树中的插入操作,然后在节点插入过后,因为AVL树的平衡性可能会改变,所以我们要开始对树进行处理。...为此我们还要写一个验证AVL树的函数。 我们都知道,AVL树一定也是二叉搜索树,所以如果中序打印出来不是一个有序的数组那么一定出问题了。验证完二叉搜索树后就是验证其为AVL树。

    10910

    C++:红黑树

    红黑树的概念 红黑树是一棵二叉搜索树,但是红黑树通过增加一个存储位表示结点的颜色RED或BLACK。...,使用parent节点是为了旋转 ,_col(RED) //默认是红色 {} }; 红黑色的插入操作 红黑树是在二叉搜索树的基础上加入了平衡限制条件的树,因此红黑树的插入分为两步: 第一步:按照二叉搜索树的规则插入新节点...红黑树的旋转直接复用AVL树的旋转的代码即可。 验证红黑树 红黑树的验证分两步:①通过中序遍历验证其是否满足二叉搜索树的性质。②验证是否满足红黑树的性质。...AVL树的对比 ⭐相同点:红黑树和AVL树都是高效的平衡二叉树,增删改查的时间复杂度都是O(log_2 N)。...也就是因为红黑树在修改操作方面的性能比AVL树好,因此红黑树都用在了C++的STL库(map/set、mutil_map/mutil_set),Java库、Linux内核等等地方。

    27020

    【c++】红黑树

    目录 1.红黑树的介绍与性质 2.节点定义 3.红黑树的插入: 情况一:父节点与叔节点均为红 情况二:父节点为红,叔节点为黑或者不存在 情况三:父节点为红,叔节点为黑或者不存在(双旋) 代码实现 4.红黑树的验证...1.红黑树的介绍与性质 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。...叔叔不存在,或者存在且为黑 { // 情况二:叔叔不存在或者存在且为黑 // 旋转+变色 // g // u p // c..._col = BLACK; grandfather->_col = RED; } else { // g // u p // c...如果左子树或右子树有一个不满足红黑树性质,则整个函数返回false 最终,IsBalance将返回一个布尔值,表示树是否满足红黑树的性质。

    11700
    领券