1、本篇博文的目标 AVL树为了保证平衡因子的绝对值不大于1，需要对节点进行旋转。如下面的这篇博文所示。...AVL树的旋转_Colourful．的博客-CSDN博客_avl树旋转 如果想要对树进行旋转，就需要具备两个先要的条件 （1）平衡因子的判断 （2）旋转的类型 2、如何计算平衡因子和不平衡的情况下的旋转类型...所以只需要通过递归的方式计算左子树和右子树的差值即可。所以问题就转换成了计算树的深度。 【树的旋转类型】 通过上面的引用的博文可知，树的旋转需要知道是是下面的那种类型？...（1）left- left (2) right - right (3) left -right (4) right -left 计算是那种类型只需要在树的深度计算的时候，对树进行递归的时候记录树的递归路径即可...另外一个是trace， //是arrayLIst的集合,该集合就记录了树的旋转类型 //计算平衡因子只需要把getDepth（左子树的节点）的depth和getDepth右子树的depth相减即可。
平衡二叉树 AVL（ 发明者为Adel'son-Vel'skii 和 Landis）是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。...注：AVL 树也是一种二叉查找树，故删除策略可以参照前面文章来实现，只是删除节点后，如果平衡被打破，则也需要进行旋转以保持平衡。...中序遍历后输出，即1～16的顺序排列。...注意：输入数组元素就不要搞成有序的了，如果代码中没有调整的实现，整个树就是个右斜树，但即使实现了调整，也会使得每插入一次就调整一次，何必内耗啊。...很显然，平衡二叉树的优势在于不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。
AVL树的结构及其相关性质，对于平衡树来说，AVL无疑是最完美的结构，但实际上AVL树由于完美的结构因此也要花费一定的代价，由于AVL树的结构很敏感，查找虽然最快，但插入节点后一旦偏离AVL结构就会进行旋转...可见红黑树的这种结构，虽然在不满足条件时会发生旋转，但敏感程度相比AVl树大大降低。...二.红黑树的结构 2.1 红黑树节点的定义 相比较AVL树，红黑树的结点仍是三叉链这个结构，为后续不满足结构的条件旋转做准备。...插入节点的颜色必须为红 ---- 检测新节点插入后，红黑树的性质是否造到破坏 因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时...和上篇中的AVL一样，对于这种弯的结构，只进行一次旋转是不可能成功的，因此需要进行两部旋转，上图只旋转了一次，变成了情况2，因此需要再旋转一次，就能满足红黑树结构的性质。
红黑树的性质（规则） 红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质： 性质1：每个节点要么是黑色，要么是红色。 性质2：根节点是黑色。...反证法：假设有一颗红黑满二叉树结点都为黑色结点时，此时添加一个黑色结点，不满足（5）特性，但是就算经过旋转，也无法满足（5）特性，大家都是黑色，变不了红黑树。...不满足性质4：每个红色结点的两个子结点一定都是黑色。需要进行RB变色。 ? 旋转 当破坏了平衡时，在调整的时候需要用到左旋和右旋： ? ?...因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。...(3) 删除代价： RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。
前言 前面一节我们介绍了平衡搜索二叉树AVL树，我们知道，AVL树虽然查找效率很高，但是不能过多的修改，因为它为了保持平衡要不断的进行旋转。...我们今天介绍的红黑树也是一种平衡搜索树，不过它所要求的平衡没有AVL树那么严格，因此对它进行修改操作时所要进行的旋转比AVL树要进行的旋转少。...第二步、分析插入结点后红黑树的性质是否被破坏 新结点默认为红色， 1.如果双亲节点的颜色是黑色，则没有违反红黑树性质，不需要调整； 2.如果双亲节点的颜色是红色，则违反性质4需要进行调整。...动态演示： 升序： 降序： 随机插入构建红黑树： 右旋转： 左旋转： 六、验证红黑树 验证红黑树分为两步： 1.检测是否满足二叉搜索树 中序遍历是否为有序序列...相对而言，插入和旋转的次数更少，在经常进行增删的结构中性能比AVL树更优，而且红黑树的实现比AVL树简单，因此更加常用。 总结 以上就是今天要讲的内容，本文介绍了C++中红黑树的相关概念。
每个叶子结点都是黑色的(此处的叶子结点指的是空结点) ---- 思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？ 答案：下面标黄处。...三、红黑树的实现 在把红黑树的逻辑了解完后，我们来实现一下吧。...检测新节点插入后，红黑树的性质是否造到破坏， // 若满足直接退出，否则对红黑树进行旋转着色处理 } // 根节点的颜色可能被修改，将其改回黑色 pRoot->_color =...; }; ② 检测新节点插入后，红黑树的性质是否造到破坏（重点） 先看每种情况下如何处理，最后有总结帮助记忆 因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何 性质，则不需要调整...旋转是啥，你不知道，惩罚你去看这篇文章的前传——avl树篇有解释）。
大家可以对照着看一下上面的图，看它是否满足这些性质。 思考：为什么满足上面的性质，红黑树就能保证：其最长路径中结点个数不会超过最短路径结点个数的两倍？...比如这样的 那另外: 其实分析上面的性质，红黑树是可以全黑的，全部黑色结点，只要满足上面的性质即可。...当然不是，和AVL树一样，插入新结点之后，我们要去判断此时这棵树是否还满足是一棵红黑树，如果不满足就要进行相应的调整。 那红黑树又是如何进行调整的呢？ 4....如果g是根节点，调整完成后，需要将g改为黑色。 这样它才满足是一棵红黑树。 那上面是g是根结点的情况，那如果g是一棵子树呢？...因为AVL树在插入和删除节点后，会进行更多的旋转操作以维持一个较为严格的平衡，所以插入和删除操作的时间复杂度更高。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树： 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) ?...如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功 2....红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的，则它的两个孩子结点是黑色的 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点 每个叶子结点都是黑色的...检测新节点插入后，红黑树的性质是否造到破坏， // 若满足直接退出，否则对红黑树进行旋转着色处理 } // 根节点的颜色可能被修改，将其改回黑色 pRoot->_color...红黑树的检测分为两步： 检测其是否满足二叉搜索树(中序遍历是否为有序序列) 检测其是否满足红黑树的性质 bool IsValidRBTree(){ Node* pRoot = _root; /
例如： 下图就是一个红黑树，同时也是一颗二叉搜索树 和AVL树不同的是，AVL树依靠着平衡因子的限制的平衡性比红黑树要更高 红黑树的性质 1. 每个结点不是红色就是黑色 2....每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 我们要尤其注意一个点： 红黑树的叶子节点是空节点，而非我们之前传统意义上的叶子节点 对于性质3的简化就是，一条路径上不能出现连续的红节点 基于上面给出的性质...2倍，他的要求并没有AVL树那么严格，所以红黑树的旋转次数要比AVL树少很多，效率自然就提升了，故而实际应用中红黑树要比AVL树用的更多一些。...检测新节点插入后，红黑树的性质是否造到破坏 因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点...检测其是否满足二叉搜索树(中序遍历是否为有序序列) 2. 检测其是否满足红黑树的性质 由于博主的能力有限，本篇博文的分享到这里就结束了，感谢大家的支持！
左旋：设x为当前结点，y为x的右结点，β为y的左节点，P为x的父结点，则x以y为支点进行左旋转，旋转后，P指向y, x的右结点指向β, y的左结点指向x。...右旋：设y为当前结点，x为y的左结点，β为x的右结点，P为y的父结点，则y以x为支点进行右旋转，旋转后，P指向x，y的左结点指向β，x的右结点指向y。...解释：这种形态经过一次变换就可以满足红黑树的性质，首先将父结点设置为黑色满足了性质四，但是违反了性质5，然后将祖父结点设置为红色，通样则父结点这个分支满足了红黑树性质，但是叔叔结点的分支违反了性质5。...所以需要再将祖父结点右旋，这样全部都满足了红黑树性质。...2.删除第三种情况和插入第二种情况也类似，这种情况下树的形态都不能一次性转化为满足红黑树性质的形态，都需要做一次中转，变成可以通过一次操作满足红黑树性质的形态。
AVL 树虽然查询效率高，但是插入、删除效率低，需要不断旋转以保持平衡。而红黑树通过牺牲一些查询效率，提高了插入、删除的效率。 AVL树 AVL 树是最早发明的自平衡二叉查找树。...为了保持红黑树的性质，我们可以对相关结点做一系列的调整，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的五个性质...旋转操作本身并不复杂，这里先分析到这吧。 插入操作 红黑树的插入过程和二叉查找树插入过程基本类似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。...插入红色节点后，会出现 5 种情况，分别如下： 情况一 插入的新节点 N 是红黑树的根节点，这种情况下，我们把节点 N 的颜色由红色变为黑色，性质 2（根是黑色）被满足。...同时 N 被染成黑色后，红黑树所有路径上的黑色节点数量增加一个，性质 5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍然被满足。
红黑树性质 1、每个结点或是红色的，或是黑色的 2、根节点是黑色的 3、每个叶结点（NIL）是黑色的 4、如果一个节点是红色的，则它的两个儿子都是黑色的。...5、对于每个结点，从该结点到其叶子结点构成的所有路径上的黑结点个数相同。 和AVL树的比较 AVL树是一棵严格的平衡树，它所有的子树都满足二叉平衡树的定义。...因此AVL树高被严格控制在XXX，因此AVL树的查找比较高效。但AVL树插入、删除结点后旋转的次数比红黑树多。 红黑树用非严格的平衡来降低插入删除时旋转的次数。...由于黑节点个数至少为红节点的两倍，因此父为黑的情况较多，而这种情况在插入后无需任何调整，这就是红黑树比AVL树插入效率高的原因！ 2....要么有且仅有一个左孩子 然后将孩子顶替它原来的位置，最后将被删的节点值覆盖待删除的那个节点A。 红黑树按照二叉搜索树的方式删除节点，之后再进行相应的旋转操作，使得删除后的树仍然是一棵红黑树。
所以就有了改进版的二叉搜索树->AVL树（平衡二叉搜索树） 在1962年，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后...一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树： 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1 / 0 / 1 ) 如果一棵二叉搜索树是高度平衡的，它就是AVL...首先选择有四种：右单旋 ，左单旋，左右双旋，右左双旋 我们依次来介绍： ️右单旋： 我们先来看什么情况需要使用右单旋： 这是最简单的情况，简单的向右旋转，使其满足AVL树的性质！...parent满足AVL树的性质！ ️...说明相比原来，高度并没有变化（由 0 删除一边而来），可以停止更新平衡因子 ⚠️parent 修改后变为 ∓2 ： 说明两边此时高度差不满足AVL树，需要进行旋转！
一棵AVL树要具有以下性质： 该树如果是空树，那么它是AVL树； 它的左右子树是AVL树； 左右子树的高度差（命名为平衡因子）的绝对值不超过1（可以是1/0/-1） 上图的红色标识的是该结点的平衡因子...平衡因子为0，说明新插入结点不影响该子树的高度，满足AVL树的性质，不再进行调整 //pparent平衡因子为±1，说明插入前pparent的平衡因子为0，此时以pparent为根的子树的高度加1...如果新增的节点就是60，那么旋转后的平衡因子更新如下： 30结点/60结点/90结点的平衡因子都为0； 如果新增的节点在60结点的左子树，那么旋转后的平衡因子更新如下： 30结点的平衡因子为1；...平衡因子为0，说明新插入结点不影响该子树的高度，满足AVL树的性质，不再进行调整 //pparent平衡因子为±1，说明插入前pparent的平衡因子为0，此时以pparent为根的子树的高度加1...但是如果对AVL树做一些结构修改的操作，它的性能就会比较低下，例如，插入元素时要维护其绝对平衡的性质，旋转的次数会比较多。其中删除的效果最差，有可能让旋转一直持续到根节点。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 红黑树，作为一棵二叉查找树，满足二叉查找树的一般性质。...为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。...对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。...操作：先旋转再变色 经过P、G变换（旋转），变换后P的位置就是当年G的位置，所以红P变为黑，而黑G变为红都是为了不违反性质5，而维持到达叶节点所包含的黑节点的数目不变！...四、红黑树与AVL树的区别 红黑树旋转操作非常局部化，而且次数极少（插入最多两次旋转，删除最多三次旋转），而改变颜色的操作不会影响到用户对树的query操作（即不要lock），另外很多树，如AVL树，2
但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多...，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于avl树为了维持平衡的 开销要小得多。...AVL树的定义: 一棵AVL树满足以下的条件: 1>它的左子树和右子树都是AVL树 2>左子树和右子树的高度差不能超过1 从条件1可能看出是个递归定义,如GNU一样....性质: 1> 一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1) 2> 一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)). 3> 一棵n个结点的AVL...树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).
如下图所示，不平衡的原因是因为A的左孩子B的左子树插入了新结点而导致了A的不平衡，那么就要利用LL旋转来调整不平衡结点A，由于平衡二叉树一定是二叉搜索树，设定插入结点为C，那么根据二叉搜索树的性质一定有...，A>B>C，那么进行如下调整：把B当作根节点，A作为B的右子树（二叉搜索树的性质）。...如下图所示，不平衡的原因是因为A的右孩子B的右子树插入了新结点而导致了A的不平衡，那么就要利用RR旋转来调整不平衡结点A，由于平衡二叉树一定是二叉搜索树，设定插入结点为C，那么根据二叉搜索树的性质一定有...如下图所示，不平衡的原因是因为A的左孩子B的右子树插入了新结点而导致了A的不平衡，那么就要利用LR旋转来调整不平衡结点A，由于平衡二叉树一定是二叉搜索树，设定插入结点为C，那么根据二叉搜索树的性质一定有...如下图所示，不平衡的原因是因为A的右孩子B的左子树插入了新结点而导致了A的不平衡，那么就要利用RL旋转来调整不平衡结点A，由于平衡二叉树一定是二叉搜索树，设定插入结点为C，那么根据二叉搜索树的性质一定有
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。 红黑树的性质 ⭐1.每个节点不是红色就是黑色。 ⭐2.根节点是黑色的。...也就是说每条路径都有相同数量的黑色节点。 ⭐5.每个叶子结点都是黑色的(此处的叶子结点指的是空结点。 从性质上分析红黑树的近似平衡 一颗红黑树最短的路径是这条路径全黑。最长是一红一黑相间路径。...第二步：检测新节点插入后，红黑树的性质是否造到破坏。...红黑树的旋转直接复用AVL树的旋转的代码即可。 验证红黑树 红黑树的验证分两步：①通过中序遍历验证其是否满足二叉搜索树的性质。②验证是否满足红黑树的性质。...⭐不同点：红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言降低了插入和旋转的次数。而AVL树是高度平衡的二叉搜索树，旋转的次数比红黑树的要频繁。
则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。 在插入或者删除结点时，为了满足平衡二叉树的性质，就需要进行自平衡操作，即二叉树的旋转。...AVL树是最早发明的自平衡二叉查找树，是最原始典型的平衡二叉树。AVL指的是发明该树的两个作者名字的简称，通常说的平衡二叉树指的是AVL树。...AVL树的旋转 AVL树的旋转类型有4种：LL（left-left）旋转、LR（left-righ）旋转、RR（right-right）旋转和RL（right-left）旋转。...接着为了满足性质4就需要进行变色，有时候只靠变色是无法保持平衡的，此时就还需要进行旋转，需要具体情况具体分析。...B树（B-tree） B树是平衡多路查找树，英文名是B-tree，有的翻译为B-树，B就是balanced。B树满足以下性质： 1）根结点至少有两个子女。
当然，还有一些更好的，但实现起来更复杂的数据结构，能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。...AVL树的定义: 一棵AVL树满足以下的条件: 1>它的左子树和右子树都是AVL树 2>左子树和右子树的高度差不能超过1 性质: 1>一棵n个结点的AVL树的其高度保持在0(log2...(n)),不会超过3/2log2(n+1) 2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)). 3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n...为了保证平衡，AVL树中的每个结点都有一个平衡因子，它表示这个结点的左、右子树的高度差，AVL树上所有结点的平衡因子值只能是-1、0、1。...红黑树更新旋转次数，插入最多2次，删除最多3次；平衡二叉树因为严格平衡，插入最多2次，删除可达O（n），被删除结点以上父节点皆有可能旋转。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
