删除
RB-TRANSPLANT(T,u,v）函数是将u子树用v来取代，在替换的时候分为了三种情况，假设u就是root结点则直接替换u，假设树里面还包括有其他结点。则将u的左右子树转移到v的左右子树上面。
RB-TRANSPLANT(T,u,v)
if u.p == T.nil T.root = v else if u == u.p.left u.p.left = v else u.p.right = v v.p = u.p
删除代码
RB-DELETE(T,z)
y = z y-original-color = z.color if z.left == T.nil //左子树为空 x = z.left RB-TRANSPLANT(T, z, z.left) //左孩子结点替换z的位置 else if z.right == T.nil //右子树为空 x = z.right RB-TRANSPLANT(T, z, z.right) //右孩子结点替换z的位置 else y = TREE-MINIMUM(z.right) //左右孩子都不为空的情况下，找到z的右孩子的最左边的孩子 y-original-color = y.color x = y.right //记住y的右孩子 if y.p == z //z.right的最左孩子是本身时 x.p = y else RB-TRANSPLANT(T, y, x) //用x去替换y的位置 y.right = z.right y.right.p = y RB-TRANSPLANT(T, z, y) //用y去替换z的位置 y.left = z.left y.left.p = y y.color = z.color if y-original-color == BLACK //假设y是红色则不影响 RB-DELETE-FIXUP(T,x)
假设y是黑色则可能已经引入了一个或多个红黑性质被破坏的情况，所以会调用RB-DELETE-FIXUP来修复红黑树的性质。
假设y是红色。则y被删除或移动时，红黑性质任然保持，
原因例如以下：- 树中的黑高没有变化。
- 不存在两个相邻的红结点。由于y在树中占领了z的位置，在考虑到z的颜色。树中y的新位置不可能有两个相邻的红结点。另外。假设y不是z的右孩子，则y的原始右孩子x取代y。
假设y是红色。则x一定是黑色，因此用x取代y不可能使两个红结点相邻。
3. 假设y是红色，就不可能是根结点。所以根结点任就是黑色。
假设y是黑色的，则会产生三个问题，能够通过调用RB-DELETE-FIXUP进行补救。
- 假设y是原来的根结点，则y的一个红色的孩子称为新的根结点，这就违反了性质2.
- 假设x和x.p是红色的，则违反了性质4.
- 在树中移动y将导致先前包括y的不论什么简单路径上黑结点个数降低1.因此，y的不论什么祖先不满足性质5.
当将黑节点y删除或移动时，将其黑色的“下推‘给结点x。
如今的问题变为结点x可能既不是红色，又不是非常色，从而违反了性质1.如今结点x是双重黑色或者红黑色，这就分别给包括x的简单路径上黑结点数贡献2或1.x的color属性任然是RED(假设x是红黑色的)或者BLACK(假设x是双重黑色的)。换句话说，结点额外的黑色是针对x结点的，而不是反映在它的color属性上的。
删除结点之后的修复
RB-DELETE-FIXUP(T,x)
while x != T.nil and x.color == BLACK if x == x.p.left w = x.p.right if w.color == RED //x的叔叔结点是红色 w.color = BLACK //case 1 x.p.color = RED //case 1 RB-ROTATE-LEFT(T, x.p) //case 1 w = x.p.right //case 1 if w.right.color == BLACK and w.left.color == BLACK //w的两个子结点都是黑色 w.color = RED //case 2 x = x.p //case 2 else if w.right.color == BLACK //w的左孩子是红色，右孩子是黑色 w.left.color = BLACK //case 3 w.color = RED //case 3 RB-ROTATE-RIGHT(T, w) //case 3 w = x.p.right //case 3 else //w的两个孩子都是红色或者是右孩子是红色 w.right.color = BLACK //case 4 w.color = x.p.color //case 4 x.p.color = BLACK //case 4 RB-ROTATE-LEFT(T, x.p) //case 4 x = T.root //case 4 else w = x.p.left if w.color == RED x.p.color = RED w.color = BLACK RIGHT-ROTATE(T, x.p) w = x.p.left if w.right.color == BLACK and w.left.color == BLACK w.color = RED x = x.p else if w.left.color == BLACK w.right.color = BLACK w.color = RED LEFT-ROTATE(T, w) w = x.p.left else w.left.color = BLACK w.color = x.p.color x.p.color = BLACK RIGHT-ROTATE(T, x.p) x = T.root x.color = BLACK
第1~22行中while循环的目标是将额外的黑色沿树上移，直到：
- x指向红黑结点，此时在第23行中。将x着为黑色。
- x指向根结点，此时能够简单的”移除“额外的黑色。
- 运行适当的旋转和又一次着色，退出循环。
在第2行要推断x是其父结点x.p的左孩子还是右孩子。
情况1： x的兄弟结点w是红色的
情况1发生的在结点x的兄弟结点w为红色时。由于w必须有黑色子结点。所以能够改变w和x.p的颜色。然后对x.p做一次左旋转而不违反红色树的不论什么性质。如今。x的新兄弟结点是旋转之前w的某个子结点，其颜色为黑色。这样。就将情况1转换为情况2、3、4处理。
当结点w为黑色时。直接就属于2、3、4中的一种。这些情况是由w的孩子结点的颜色来区分的。
情况2：x的兄弟结点w是黑色的，并且w的两个子结点都是黑色的。
情况3：x的兄弟结点w是黑色的，w的左孩子是红色的，右孩子是黑色的。
情况4：x的兄弟结点w是黑色的，且右孩子是黑色的。