删除
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.
改正這一問題的辦法就是将如今路徑上黑節點個數加1，則在這樣的假設下，性質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指向根結點，此時能夠簡單的”移除“額外的黑色。
- 運作适當的旋轉和又一次着色，退出循環。
在while循環中。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是黑色的，且右孩子是黑色的。