Algorithms for Red Black Tree Operations
(from CLRS text)

Iterative-Tree-Search (x, k)
while x <> NIL and k <> key[x]
    do if k < key[x]
        then x := left[x]
        else x := right[x]
return x



Tree-Minimum(x)
while left[x] <> NIL
    do x := left[x]
return x



Tree-Maximum(x)
while right[x] <> NIL
    do x := right[x]
return x



Tree-Successor(x)
if right[x] <> NIL
    then return Tree-Minimum(right[x])
y := p[x]
while y <> NIL and x = right[y]
    do x := y
       y := p[y]
return y



Left-Rotate(T,x)
y := right[x]
right[x] := left[y]
if left[y] <> NIL
   then p[left[y]] := x
p[y] := p[x]
if p[x] = NIL
    then root[T] := y
    else if x = left[p[x]]
            then left[p[x]] := y
            else right[p[x]] := y
left[y] := x
p[x] := y



Right-Rotate(T,x)
this procedure is symmetric to the Left-rotate



RB-Insert(T,x)
Tree-Insert(T,x)
color[x] := RED
while x <> root[T] and color[p[x]] = RED
    do if p[x] = left[p[p[x]]]
          then y := right[p[p[x]]]
               if color[y] = RED
                  then color[p[x]] := BLACK
                       color[y] := BLACK
                       color[p[p[x]]] := RED
                       x := p[p[x]]
                  else if x = right[p[x]]
                          then x := p[x]
                               Left-Rotate(T,x)
                        color[p[x]] := BLACK
                        color[p[p[x]] := RED
                        Right-Rotate(T,p[p[x]])
          else (same as then clause
                with "right" and "left" exchanged)
color[root[T]] := BLACK



RB-Delete(T,z)
if left[z] = nil[T] or right[z] = nil[T]
   then y := z
   else y := Tree-Successor(z)
if left[y] <> nil[T]
   then x := left[y]
   else x := right[y]
p[x] := p[y]
if p[y] = nil[T]
   then root[T] := x
   else if y = left[p[y]]
           then left[p[y]] := x
           else right[p[y]] := x
if y <> z
   then key[z] := key[y]
        (if y has other fields, copy them, too)
if color[y] = BLACK
   then RB-Delete-Fixup(T,x)
return y



RB-Delete-Fixup(T,x)
while x <> root[T] and color[x] = BLACK
    do if x = left[p[x]]
          then w := right[p[x]]
               if color[w] = RED
                  then color[w] := BLACK
                       color[p[x]] := RED
                       Left-Rotate(T,p[x])
                       w := right[p[x]]
                if color[left[w]] = BLACK and color[right[w]] = BLACK
                   then color[w] := RED
                        x := p[x]
                   else if color[right[w]] = BLACK
                           then color[left[w]] := BLACK
                                color[w] := RED
                                Right-Rotate(T,w)
                                w := right[p[x]]
                        color[w] := color[p[x]]
                        color[p[x]] := BLACK
                        color[right[w]] := BLACK
                        Left-Rotate(T,p[x])
                        x := root[T]
       else (same as then clause
             with "right" and "left" exchanged)
color[x] := BLACK