红黑树略胜AVL树
AVL树是一颗高度平衡搜索二叉树： 要求左右高度差不超过1（严格平衡）
有的大佬认为AVL树太过严格，对平衡的要求越严格，会带来更多的旋转（旋转也还是会有一定的消耗！！）
红黑树的出发点：最长路径不超过最短路径的2倍（近似平衡）
相对而言，插入同样的数据，AVL树旋转更多，红黑树旋转更少（这是优势）
红黑树的劣势：
我们在进行查找的时候，我们AVL树最多查找20次左右
红黑树最多查找40次左右
虽然红黑树查找的次数比AVL树多，但是红黑树在插入过程中的旋转更少，更占优势
红黑树的概念
红黑树，是一种搜索二叉树，单在每个节点上增加一个存储位表示节点的颜色，可以是Red或Block，通过对任何一条从根到路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因而是接近平衡的
1.每一个节点不是红色就是黑色
2.根节点是黑色的
3.如果一个节点是红的，那么它的两个孩子节点是黑色的
解读 ： 树中没有连续的红色节点
4.对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含有相同的数目的黑色节点
解读 ： 每条路径的黑色节点数量相等
5.每个叶子节点都是黑色的（此处的叶子节点指的是空节点NIL节点）
为什么这里指的是空节点呢？？
为什么满足上面性质，红黑树就能保证 ： 其最长路径中节点个数不会超过最短路径节点个数的两倍？？
因为每条路径上都有相同数量的黑节点 所以：
这颗树最短路径 ： 一定是全黑
最长路径 ： 一定是一黑一红
这样最短路径一定不超过最长路径的二倍
红黑实现代码
我们在新插入的节点是应该选择红色还是黑色呢？？
我们来看看插入红色，会是什么样？？
发现如果插入黑色一定挨打，如果插入红色有可能不用挨打，拍拍屁股就走人了，就算是挨打，也不用太大费周章的解决
叔叔也是红的，那我把叔叔也变黑，祖父变红
如果这时候 25就是这颗树的根，就结束了，没必要在往后走了（再像办法把25变为黑的）
这时候我们发现还有一个小问题，grandfather变成红了，但是grandfather这时候是根，根不能是红的，我们还得把grandfather变成黑，即可
我们上面的过程，红黑树的插入问题可能光变色就够了，插入节点之后最短并没有超过最长的2倍，也不需要旋转，降长度
------------------------------------------------------------------------------------------------------------------
一下这种情况就需要旋转加变色了
------------------------------------------------------------------------------------------------------------------------------
情况一 ： cur为红，p为红，g为黑，u存在且为红
具像图一：
具像图二：
总共有 4*4*4*4（在ab的任意位置插入，有4种情况） =256 种组合
这些情况是无穷无尽的！！！
有可能 a b下面还有一个黑节点，那么cde的子树就是有两个黑节点的子树了，情况是无穷无尽的了
---------------------------------------------------------------------------------------------------------------------------
情况二 ： 还有的情况是光变色解决不了的！！！！
cur为红，p为红 ， g为黑，u不存在 / u存在且为黑
情况三：就是情况二再变形
双旋 + 变色
情况一变过来之后，我们看叔叔的情况！！！
文章来源：https://www.toymoban.com/news/detail-684618.html
文章来源地址https://www.toymoban.com/news/detail-684618.html
到了这里，关于红黑树（AVL树的优化）上的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[数据结构]-红黑树](https://imgs.yssmx.com/Uploads/2024/02/756302-1.png)
