原文链接：https://blog.csdn.net/qq_32727095/article/details/112667573
- 红黑树是一棵自平衡二叉树，
- 以前也叫平衡二叉B树
平衡二叉树又叫AVL树，具有以下性质:
- 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树
平衡二叉树好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
红黑树的性质
image.png
- 节点是RED或者BLACK
- 根节点是Black
- 叶子节点（外部节点、空节点）都是black
- red节点的parent都是black，red节点的子节点都是black；从根节点到叶子节点的所有路径上不能有2个连续的red节点
- 从任一节点到叶子节点的所有路径都包含相同数目的black节点
红黑树 与 4阶B树
image.png
下面是一个与上面的红黑树等价的 4阶B树；
image.png
红黑树基础代码
image.png
添加节点12种情况（）（默认为red）
- 当 parent 是黑色，不做任何处理，添加完成后任是一棵红黑树。有 4 种情况满足红黑树的性质 4 ：parent 为 BLACK
- 当前parent为红色，有 8 种情况不满足红黑树的性质 4 ：parent 为 RED（ Double Red ）
（1）4种为上溢的情况：【判定条件：uncle 节点是红色】上溢（LL，RR，LR，RL），将parent,unicode染成黑色，grand向上合并。并且将grand染成红色当作新节点处理【递归】；grand向上合并时，可能会继续发生上溢，若上溢到根节点，只需将根节点染成black
（2）4种为旋转的情况：【判定条件：uncle 节点不是红色（包括null）】
①：旋转【LL】【RR】：将parent染成黑色，grand染成红色，然后对grand进行旋转，若grand是LL的情况：右旋转，若grand是RR的情况，左旋转
②：旋转【LR】【RL】：将自己染成黑色，grand染成红色，然后对grand进行旋转，若grand是LR的情况：parent左旋转，grand右旋转，若grand是RL的情况：parent右旋转，grand左旋转
image.png
image.png
image.png
image.png
image.png
image.png
红黑树的平衡
- 相比AVL树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2被
- 是一种弱平衡、黑高度平衡
- 红黑树的最大高度是2*log2(n+1),依然O（logn）级别
平均复杂的
- 搜索： O（logn）
- 添加：O（logn），O(1)此的旋转操作
AVL树VS红黑树
AVL树
- 平衡标准比较严格：每个左右子树的高度差不超过 1
- 最大高度是 1.44 ∗ l o g 2 n + 2 − 1.328 （100W 个节点，AVL树最大树 高28）
- 搜索、添加、删除都是 O ( l o g n ) 复杂度，其中添加仅需 O ( 1 ) 次旋转调整、删除最多需要 O ( l o g n ) 次旋转调整
红黑树
- 平衡标准比较宽松：没有一条路径会大于其他路径的 2倍
- 最大高度是 2 ∗ l o g 2 ( n + 1 ) （ 100W 个节点，红黑树最大树 高40）
- 搜索、添加、删除都是 O ( l o g n )复杂度，其中添加、删除都仅需 O(1) 次旋转调整
- 搜索的次数远远大于插入和删除，选择AVL树；
搜索、插入、删除次数几乎差不多，选择红黑树 - 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树
- 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树
