红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 -百度百科
特性
每个节点或者是黑色，或者是红色。根节点是黑色。每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]如果一个节点是红色的，则它的子节点必须是黑色的。[从每个叶子到根的所有路径上不能有两个连续的红色节点。]从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。[简称黑高]注意：
特性(3)中的叶子节点，是只为空(NIL或null)的节点。特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。有了上面的几个性质作为限制，即可避免二叉查找树退化成单链表的情况。但是，仅仅避免这种情况还不够，这里还要考虑某个节点到其每个叶子节点路径长度的问题。如果某些路径长度过长，那么，在对这些路径上的及诶单进行增删查操作时，效率也会大大降低。这个时候性质4和性质5用途就凸显了，有了这两个性质作为约束，即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍。
特性
每个红黑树的高度: h ≤ 2 l o g ( N + 1 ) h ≤ 2log(N+1) h≤2log(N+1)
每个红黑树的黑色节点数: N b l a c k ≥ n / 2 Nblack ≥ n / 2 Nblack≥n/2
增加、删除和查找的时间复杂度总为$O(log(n)) $
任何一个节点到叶节点的黑色节点数(Black Height): B H > = h / 2 BH >= h/2 BH>=h/2
根节点到叶节点最多有 l o g ( 2 ( n + 1 ) ) log(2(n+1)) log(2(n+1))个黑色节点
红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是 O ( l g ( n ) ) O(lg(n)) O(lg(n))，效率非常之高。
用于C++实现Map/Set, Java实现TreeMap/HashMap等数据结构，此外还可以用于实时计算程序和函数式编程中。
树中的每个节点包括5个属性：color、key、left、right、parent，如果一个节点没有子节点或父节点，则该节点的相应指针属性的值为NIL
#定义红黑树 class RBTree(object): def __init__(self): self.nil = RBTreeNode(0) self.root = self.nil class RBTreeNode(object): def __init__(self, x): self.key = x self.left = None self.right = None self.parent = None self.color = 'black' self.size=None红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。 旋转包括两种：左旋 和 右旋。下面分别对它们进行介绍。
对x进行左旋，意味着"将x变成一个左节点"。
# 左旋转 def LeftRotate(T, x): y = x.right x.right = y.left # β指向x右侧 if y.left != T.nil: y.left.parent = x #β的父节点指向x y.parent = x.parent # y父节点更为为远x节点 if x.parent == T.nil: T.root = y # 考虑x父节点为根节点情况 elif x == x.parent.left: x.parent.left = y # x为父节点的左侧值 else: x.parent.right = y # x为父节点的右侧值 y.left = x # y的右节点指向x x.parent = y #x的父节点指向y理解左旋之后，看看下面一个更鲜明的例子。你可以先不看右边的结果，自己尝试一下。
与左旋相对应，将Y进行右旋，意味着"将Y变成一个右节点"
# 右旋转 def RightRotate(T, y): x = y.left y.left = x.right # x的β赋值给y if x.right != T.nil: x.right.parent = y # 将β的父节点指向y x.parent = y.parent # y的父节点给x的父节点 if y.parent == T.nil: T.root = x # 考虑父节点为空的情况 elif y == y.parent.right: y.parent.right = x # y为父节点的右侧值 else: y.parent.left = x # y为父节点的左侧值 x.right = y # x的右侧值指向y y.parent = x # y的父节点指向x(01) 左旋 和 右旋 是相对的两个概念，原理类似。理解一个也就理解了另一个。
将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。详细描述如下：
第一步: 将红黑树当作一颗二叉查找树，将节点插入。
红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。 好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！
第二步：将插入的节点着色为"红色"。
为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性： (1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！] (4) 如果一个节点是红色的，则它的子节点必须是黑色的。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。
第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树
第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)"。那它到底会违背哪些特性呢？
对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。对于"特性(2)"，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。对于"特性(4)"，是有可能违背的！那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。
# 红黑树的插入 def RBInsert(T, z): y = T.nil # 新建结点y,y设为空节点 x = T.root # 设“红黑色T”的根节点为 x while x != T.nil: # 找出要插入结点的z在二叉树T的位置y y = x if z.key < x.key: x = x.left else: x = x.right z.parent = y # 插入结点z的父节点设为y if y == T.nil: T.root = z # 情况一 y为空节点，则插入结点设为根 elif z.key < y.key: y.left = z # 情况二 若插入值小于父节点值，放在左侧 else: y.right = z # 情况三 若插入值大于父节点值，放在右侧 z.left = T.nil # 插入值的左右结点为空 z.right = T.nil z.color = 'red' # 默认插入为红色 # 对红黑树结点进行颜色修改和旋转，保持红黑树性质 RBInsertFixup(T, z) return z.key, '颜色为', z.color修改红黑树颜色与旋转
# 红黑树的上色 def RBInsertFixup(T, z): while z.parent.color == 'red': # 当前父节点为红色， 则进行处理,直到符合条件停止 ### z的父节点是祖结点的左孩子 if z.parent == z.parent.parent.left: y = z.parent.parent.right # 将y设置为z的祖结点的右孩子（叔叔结点） if y.color == 'red': # 情况一 ：叔叔结点为红色 z.parent.color = 'black' # 父节点设为黑色 y.color = 'black' # 叔叔节点设为黑色 z.parent.parent.color = 'red' # 祖父设为红色 z = z.parent.parent # 祖父结点设为当前结点 ？？考虑后续操作 else: # 叔叔结点为黑色 if z == z.parent.right: # 情况二 ：且当前结点是右孩子 z = z.parent # 父节点当做新的当前结点 LeftRotate(T, z) # 当前结点为支点进行左旋转 z.parent.color = 'black' # 情况三 ：且当前结点是左孩子，将父节点设为黑色 z.parent.parent.color = 'red' # 祖父结点为红色 RightRotate(T, z.parent.parent) # 当前结点为支点进行右旋转 ### z的父节点是祖结点的右孩子，将上面right和left交换位置，依次执行 else: y = z.parent.parent.left if y.color == 'red': z.parent.color = 'black' y.color = 'black' z.parent.parent.color = 'red' z = z.parent.parent else: if z == z.parent.left: z = z.parent RightRotate(T, z) z.parent.color = 'black' z.parent.parent.color = 'red' LeftRotate(T, z.parent.parent) T.root.color = 'black'根据被插入节点的父节点的情况，可以将"当节点z被着色为红色节点，并插入二叉树"划分为三种情况来处理。 ① 情况说明：被插入的节点是根节点。 处理方法：直接把此节点涂为黑色。 ② 情况说明：被插入的节点的父节点是黑色。 处理方法：什么也不需要做。节点被插入后，仍然是红黑树。 ③ 情况说明：被插入的节点的父节点是红色。 处理方法：那么，该情况与红黑树的“特性(5)”相冲突。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为3种情况(Case)。
现象说明处理策略Case 1当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。(01) 将“父节点”设为黑色。 (02) 将“叔叔节点”设为黑色。 (03) 将“祖父节点”设为“红色”。 (04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。Case 2当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子(01) 将“父节点”作为“新的当前节点”。 (02) 以“新的当前节点”为支点进行左旋。Case 3当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子(01) 将“父节点”设为“黑色”。 (02) 将“祖父节点”设为“红色”。 (03) 以“祖父节点”为支点进行右旋。上面三种情况(Case)处理问题的核心思路都是：将红色的节点移到根节点；然后，将根节点设为黑色。下面对它们详细进行介绍。
为什么要这样处理
“当前节点”和“父节点”都是红色，违背“特性(4)”。所以，将“父节点”设置“黑色”以解决这个问题。
但是，将“父节点”由“红色”变成“黑色”之后，违背了“特性(5)”：因为，包含“父节点”的分支的黑色节点的总数增加了1。
解决这个问题的办法是：
将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”。
第一，为什么“祖父节点”之前是黑色？这个应该很容易想明白，因为在变换操作之前，该树是红黑树，“父节点”是红色，那么“祖父节点”一定是黑色。
第二，为什么将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”；能解决“包含‘父节点’的分支的黑色节点的总数增加了1”的问题。
“第二条原因：包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”，既然这样，我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题； 但是，这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”，现在我们已知“叔叔节点”是“红色”，将“叔叔节点”设为“黑色”就能解决这个问题。 所以，将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”；就解决了该问题。 按照上面的步骤处理之后：当前节点、父节点、叔叔节点之间都不会违背红黑树特性，但祖父节点却不一定。若此时，祖父节点是根节点，直接将祖父节点设为“黑色”，那就完全解决这个问题了；若祖父节点不是根节点，那我们需要将“祖父节点”设为“新的当前节点”，接着对“新的当前节点”进行分析。
为什么要这样处理
首先，将“父节点”作为“新的当前节点”；接着，以“新的当前节点”为支点进行左旋。 为了便于理解，我们先说明第(02)步，再说明第(01)步；为了便于说明，我们设置“父节点”的代号为F(Father)，“当前节点”的代号为S(Son)。
为什么要“以F为支点进行左旋”呢？
根据已知条件可知：S是F的右孩子。而之前我们说过，我们处理红黑树的核心思想：将红色的节点移到根节点；然后，将根节点设为黑色。既然是“将红色的节点移到根节点”，那就是说要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)。 而S又是一个右孩子，因此，我们可以通过“左旋”来将S上移！
按照上面的步骤(以F为支点进行左旋)处理之后：若S变成了根节点，那么直接将其设为“黑色”，就完全解决问题了；若S不是根节点，那我们需要执行步骤(01)，即“将F设为‘新的当前节点’”。
那为什么不继续以S为新的当前节点继续处理，而需要以F为新的当前节点来进行处理呢？
这是因为“左旋”之后，F变成了S的“子节点”，即S变成了F的父节点；而我们处理问题的时候，需要从下至上(由叶到根)方向进行处理；也就是说，必须先解决“孩子”的问题，再解决“父亲”的问题；所以，我们执行步骤(01)：将“父节点”作为“新的当前节点”。
为什么要这样处理
为了便于说明，我们设置“当前节点”为S(Original Son)，“兄弟节点”为B(Brother)，“叔叔节点”为U(Uncle)，“父节点”为F(Father)，祖父节点为G(Grand-Father)。 S和F都是红色，违背了红黑树的“特性(4)”，我们可以将F由“红色”变为“黑色”，就解决了“违背‘特性(4)’”的问题；但却引起了其它问题：违背特性(5)，因为将F由红色改为黑色之后，所有经过F的分支的黑色节点的个数增加了1。那我们如何解决“所有经过F的分支的黑色节点的个数增加了1”的问题呢？ 我们可以通过“将G由黑色变成红色”，同时“以G为支点进行右旋”来解决。
【插入操作口诀】
我根我爸黑，那就很简单。
我爸要是红，伯伯也红，黑爸黑伯红祖父，
伯伯若黑，三角转成直，直也转一次，转后祖父与兄色互换，全部结束根染黑。
将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：
第一步：将红黑树当作一颗二叉查找树，将节点删除。 这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况： ① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。 ② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。 ③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。
第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。 因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。
# 将v替换为u def RBTransplant( T, u, v): if u.parent == T.nil: T.root = v elif u == u.parent.left: u.parent.left = v else: u.parent.right = v v.parent = u.parent # 获取当前值下面的最小值 def TreeMinimum( x): while x.left != T.nil: x = x.left return x # 红黑树的删除 # x保存需要变动子树的信息，y是在两侧信息都保留情况下 右侧最小值 def RBDelete(T, z): y = z y_original_color = y.color # 保存节点原先颜色信息 if z.left == T.nil: x = z.right RBTransplant(T, z, z.right) # 若左边孩子为空 则用右孩子代替（z也可能为叶子节点） elif z.right == T.nil: x = z.left RBTransplant(T, z, z.left) # 若右边孩子为空 则用左孩子代替 else: y = TreeMinimum(z.right) # 第三种情况，该节点有两个孩子 y_original_color = y.color # 保存求得最小子节点的颜色信息 x = y.right if y.parent == z: # 最小值与删除值z直接相连，则右孩子孩子父节点指向最小值 x.parent = y else: # 删除值z与右侧最小值y不直接相连，(主要用最小值的右侧替换最小值) RBTransplant(T, y, y.right) y.right = z.right y.right.parent = y RBTransplant(T, z, y) # 则用y替代z y.left = z.left y.left.parent = y y.color = z.color if y_original_color == 'black': # 修正颜色，因为红色不影响红黑树条件特性 RBDeleteFixup(T, x)修改红黑树颜色与旋转
# 红黑树的着色和旋转 def RBDeleteFixup(T, x): while x != T.root and x.color == 'black': # 循环终止条件 x不是根或者x的颜色为红色 if x == x.parent.left: # 若x是它父节点的左孩子，则 w为父节点的右孩子（兄弟节点） w = x.parent.right if w.color == 'red': # Case 1: x的兄弟节点颜色为红色(此时x的父节点和x的兄弟节点的子节点都是黑节点) w.color = 'black' # (01) 将x的兄弟节点设为“黑色”。 x.parent.color = 'red' # (02) 将x的父节点设为“红色”。 LeftRotate(T, x.parent)# (03) 对x的父节点进行左旋。 w = x.parent.right # (04) 左旋后，重新设置x的兄弟节点。 if w.left.color == 'black' and w.right.color == 'black': # Case 2: x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。 w.color = 'red' # (01) 将x的兄弟节点设为“红色”。 x = x.parent # (02) 设置“x的父节点”为“新的x节点”。 else: # Case 3: x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。 if w.right.color == 'black': w.left.color = 'black' # (01) 将x兄弟节点的左孩子设为“黑色”。 w.color = 'red' # (02) 将x兄弟节点设为“红色”。 RightRotate(T, w) # (03) 对x的兄弟节点进行右旋。 w = x.parent.right # (04) 右旋后，重新设置x的兄弟节点。 # Case 4: x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的 w.color = x.parent.color # (01) 将x父节点颜色 赋值给 x的兄弟节点。 x.parent.color = 'black' # (02) 将x父节点设为“黑色”。 w.right.color = 'black' # (03) 将x兄弟节点的右子节设为“黑色”。 LeftRotate(T, x.parent) # (04) 对x的父节点进行左旋。 x = T.root # (05) 设置“x”为“根节点”。 else: # x是它父节点的右孩子，将上面的操作中“right”和“left”交换位置，然后依次执行 w = x.parent.left if w.color == 'red': w.color = 'black' x.parent.color = 'red' RightRotate(T, x.parent) w = x.parent.left if w.right.color == 'black' and w.left.color == 'black': w.color = 'red' x = x.parent else: if w.left.color == 'black': w.right.color = 'black' w.color = 'red' LeftRotate(T, w) w = x.parent.left w.color = x.parent.color x.parent.color = 'black' w.left.color = 'black' RightRotate(T, x.parent) x = T.root x.color = 'black'前面我们将"删除红黑树中的节点"大致分为两步
在第一步中"将红黑树当作一颗二叉查找树，将节点删除"后，可能违反"特性(2)、(4)、(5)"三个特性。
第二步需要解决上面的三个问题，进而保持红黑树的全部特性。
为了便于分析，我们假设"x包含一个额外的黑色"(x原本的颜色还存在)，这样就不会违反"特性(5)"。为什么呢？
通过RB-DELETE算法，我们知道：删除节点y之后，x占据了原来节点y的位置。 既然删除y(y是黑色)，意味着减少一个黑色节点；那么，再在该位置上增加一个黑色即可。这样，当我们假设"x包含一个额外的黑色"，就正好弥补了"删除y所丢失的黑色节点"，也就不会违反"特性(5)"。 因此，假设"x包含一个额外的黑色"(x原本的颜色还存在)，这样就不会违反"特性(5)"。
现在，x不仅包含它原本的颜色属性，x还包含一个额外的黑色。即x的颜色属性是"红+黑"或"黑+黑"，它违反了"特性(1)"。
现在，我们面临的问题，由解决"违反了特性(2)、(4)、(5)三个特性"转换成了"解决违反特性(1)、(2)、(4)三个特性"。
RBDeleteFixup需要做的就是通过算法恢复红黑树的特性(1)、(2)、(4)。
RBDeleteFixup的思想是：将x所包含的额外的黑色不断沿树上移(向根方向移动)，直到出现下面的姿态：
a) x指向一个"红+黑"节点。此时，将x设为一个"黑"节点即可。
b) x指向根。此时，将x设为一个"黑"节点即可。
c) 非前面两种姿态。
将上面的姿态，可以概括为3种情况。 ① 情况说明：x是“红+黑”节点。 处理方法：直接把x设为黑色，结束。此时红黑树性质全部恢复。 ② 情况说明：x是“黑+黑”节点，且x是根。 处理方法：什么都不做，结束。此时红黑树性质全部恢复。 ③ 情况说明：x是“黑+黑”节点，且x不是根。 处理方法：这种情况又可以划分为4种子情况。这4种子情况如下表所示：
现象说明处理策略Case 1x是"黑+黑"节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。(01) 将x的兄弟节点设为“黑色”。 (02) 将x的父节点设为“红色”。 (03) 对x的父节点进行左旋。 (04) 左旋后，重新设置x的兄弟节点。Case 2x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。(01) 将x的兄弟节点设为“红色”。 (02) 设置“x的父节点”为“新的x节点”。Case 3x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。(01) 将x兄弟节点的左孩子设为“黑色”。 (02) 将x兄弟节点设为“红色”。 (03) 对x的兄弟节点进行右旋。 (04) 右旋后，重新设置x的兄弟节点。Case 4x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。(01) 将x父节点颜色 赋值给 x的兄弟节点。 (02) 将x父节点设为“黑色”。 (03) 将x兄弟节点的右子节设为“黑色”。(04) 对x的父节点进行左旋。 (05) 设置“x”为“根节点”。(01) 将A的兄弟节点(D)设为“黑色”。 (02) 将A的父节点(B)设为“红色”。 (03) 对x的父节点(B)进行左旋。 (04) 左旋后，重新设置A的兄弟节点。
为什么要这样处理
这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”，从而进行进一步的处理。对x的父节点进行左旋；左旋后，为了保持红黑树特性，就需要在左旋前“将x的兄弟节点设为黑色”，同时“将x的父节点设为红色”；左旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。
(01) 将x的兄弟节点设为“红色”。 (02) 设置“x的父节点”为“新的x节点”。
为什么要这样处理
这个情况的处理思想：是将“x中多余的一个黑色属性上移(往根方向移动)”。 x是“黑+黑”节点，我们将x由“黑+黑”节点 变成 “黑”节点，多余的一个“黑”属性移到x的父节点中，即x的父节点多出了一个黑属性(若x的父节点原先是“黑”，则此时变成了“黑+黑”；若x的父节点原先时“红”，则此时变成了“红+黑”)。 此时，需要注意的是：所有经过x的分支中黑节点个数没变化；但是，所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)！为了解决这个问题，我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可，那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。 经过上面的步骤(将x的兄弟节点设为红色)，多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑+红”，直接将“新的x节点”设为黑色，即可完全解决该问题；若“新的x节点”是“黑+黑”，则需要对“新的x节点”进行进一步处理。
(01) 将x兄弟节点的左孩子设为“黑色”。 (02) 将x兄弟节点设为“红色”。 (03) 对x的兄弟节点进行右旋。 (04) 右旋后，重新设置x的兄弟节点。
为什么要这样处理
我们处理“Case 3”的目的是为了将“Case 3”进行转换，转换成“Case 4”,从而进行进一步的处理。转换的方式是对x的兄弟节点进行右旋；为了保证右旋后，它仍然是红黑树，就需要在右旋前“将x的兄弟节点的左孩子设为黑色”，同时“将x的兄弟节点设为红色”；右旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理
(01) 将x父节点颜色 赋值给 x的兄弟节点。 (02) 将x父节点设为“黑色”。 (03) 将x兄弟节点的右子节设为“黑色”。 (04) 对x的父节点进行左旋。 (05) 设置“x”为“根节点”。
为什么要这样处理
我们处理“Case 4”的目的是：去掉x中额外的黑色，将x变成单独的黑色。处理的方式是“：进行颜色修改，然后对x的父节点进行左旋。下面，我们来分析是如何实现的。 为了便于说明，我们设置“当前节点”为S(Original Son)，“兄弟节点”为B(Brother)，“兄弟节点的左孩子”为BLS(Brother’s Left Son)，“兄弟节点的右孩子”为BRS(Brother’s Right Son)，“父节点”为F(Father)。 我们要对F进行左旋。但在左旋前，我们需要调换F和B的颜色，并设置BRS为黑色。为什么需要这里处理呢？因为左旋后，F和BLS是父子关系，而我们已知BL是红色，如果F是红色，则违背了“特性(4)”；为了解决这一问题，我们将“F设置为黑色”。 但是，F设置为黑色之后，为了保证满足“特性(5)”，即为了保证左旋之后： 第一，“同时经过根节点和S的分支的黑色节点个数不变”。 若满足“第一”，只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”，而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1；现在，只需将S由“黑+黑”变成单独的“黑”节点，即可满足“第一”。 第二，“同时经过根节点和BLS的分支的黑色节点数不变”。 若满足“第二”，只需要将“F的原始颜色”赋值给B即可。之前，我们已经将“F设置为黑色”(即，将B的颜色"黑色"，赋值给了F)。至此，我们算是调换了F和B的颜色。 第三，“同时经过根节点和BRS的分支的黑色节点数不变”。 在“第二”已经满足的情况下，若要满足“第三”，只需要将BRS设置为“黑色”即可。 经过，上面的处理之后。红黑树的特性全部得到的满足！接着，我们将x设为根节点，就可以跳出while循环(参考伪代码)；即完成了全部处理。
至此，我们就完成了Case 4的处理。理解Case 4的核心，是了解如何“去掉当前节点额外的黑色”。
【删除操作口诀】
删除节点两后代，交换键值往下看。
删除节点是树根，直接删除或替换。
删除节点无后代，自己若黑修双黑。
删除节点有一子，若是红子染成黑。
【修复双黑操作】
什么是双黑和修复双黑?
双黑是指删除操作中替换节点与删除节点均为黑色的情况，双黑标记表明了当前树违背了黑色节点数目一致的原则，需要进行修复。修复双黑就是为了保证红黑树满足上述合法性的操作。
若不存在兄弟: 双黑要传递给父亲，对父亲进行修复双黑
兄弟是红色: 染红父亲，染黑兄弟，把兄弟转上去，转化为兄弟为黑的情况
兄弟是黑色，此时需要讨论兄弟儿子的情况
兄弟没有红色儿子，先染红兄弟，然后讨论父亲颜色的情况 父亲为红色: 染黑父亲即可父亲为黑色: 对父亲节点修复双黑 兄弟有红色儿子，根据兄弟与兄弟儿子形成的结构进行分类讨论 直线型: 兄弟儿子染成黑色，兄弟染成父亲色，然后把兄弟转上去三角型: 把兄弟儿子染成和父亲同色，把兄弟儿子转到兄弟的位置，再把兄弟的儿子转到父亲的位置红黑树(一)之 原理和算法详细介绍
【干货】几个口诀帮你记忆红黑树的操作实现
红黑树详细分析，看了都说好
https://blog.csdn.net/JERRY_PRI/article/details/8959426
Python实现红黑树
Data Structure Visualizations
直线型: 兄弟儿子染成黑色，兄弟染成父亲色，然后把兄弟转上去 2. 三角型: 把兄弟儿子染成和父亲同色，把兄弟儿子转到兄弟的位置，再把兄弟的儿子转到父亲的位置
[外链图片转存中…(img-Cy9nFzZJ-1572491023242)]
红黑树(一)之 原理和算法详细介绍
【干货】几个口诀帮你记忆红黑树的操作实现
红黑树详细分析，看了都说好
Python实现红黑树
Data Structure Visualizations
