红黑树的概念？什么是红黑树？
红黑树是一种含有红黑节点并能自平衡的二叉查找树。区别于avl树, avl树是完美平衡二叉树, 红黑树是弱平衡二叉树。
红黑树的五大性质（最核心）
1.每个节点要么是黑色, 要么是红色。
2.根节点是黑色。 ---> 硬性规定, 无法推导出这个结论。
3.每个叶子节点(Nil)是黑色。 ---> 叶子节点都是黑色虚节点(color=black;value=None)
4.每个红色节点的两个子节点一定都是黑色(父节点也是黑色)。
5.任意一个节点到每个叶子节点的路径都包含相同数量的黑节点。 (红黑树不是完美平衡, 但是黑色完美平衡)
红黑树的规律（由五大性质推导出）
结论：性质4 5作为约束可以保证任意节点到每个叶子节点路径最长不会超过最短路径的2倍
原因：最极端情况下：出现最短路径时, 这条路径必然都是黑节点; 出现最长路径时, 这条路径必然是红黑节点相间构成, 此时路径上红节点数量=黑节点数量; 再结合性质5, 极端情况下最长路径也仅仅是最短路径的两倍。
红黑树的操作
红黑树自平衡的原子操作：变色, 旋转(圆心, 方向)
红黑树的插入操作
思路：每次插入之后要操作保持红黑树的性质。1. 查找插入的位置 2.插入后自平衡
自平衡的4种情况：(设curr为当前节点)
红黑树的删除操作
思路：如果被删除节点没有孩子，直接删除即可。如果删除节点只有一个孩子：1.删除节点为红色时, 直接拿孩子补位即可; 2.删除节点为黑色时, 2.1.孩子为红色, 直接拿孩子替换并将孩子染成黑色; 2.2.孩子为黑色则复杂得多。如有两个孩子, 则先要找到该节点前驱(左子树最大)或者后继(右子树最小), 习惯上一般选择后继, 这里我们用后继。然后前驱或后继的值复制到要删除的节点, 最后删除前驱或后继。由于前驱和后继不可能有两个孩子, 删除前驱后继=删除只有一个孩子或没有孩子的节点。
复杂度分析
毫无疑问，红黑树和avl树没有理用额外空间，所以他们空间复杂度都为O(1)
avl树和红黑树查询时间复杂度均为O(logn)平均查询时间红黑树稍微慢一点但是没慢多少。虽然对于插入和删除节点, avl树和红黑树最坏情况下时间复杂度均为O(logn), 但在自平衡的时候, 红黑树由于有黑色节点的存在(上文中自平衡的情况2), 每次parent为黑色时复杂度降为O(1)。根据性质4 5 得出红黑树的每条路径上黑节点数量 大于等于 红节点数量, 所以至少50%的概率parent为黑色。所以红黑树自平衡的平均时间复杂度 小于等于 avl树平均时间复杂度的一半。
本文转自我知乎原文: 红黑树超全讲解纯干货带流程图方便收藏
欢迎关注我的知乎账号：进击的steve
