_RED-BLACK TREES_
by Bruce Schneier

[Example 1: Insert operation, in pseudocode]
 
 
RedBlackInsert(T,x)
{
    TreeInsert(T,x)
    color(x) <-- Red
    while x != root(T) and color(p(x))==Red
        if p(x)==left(p(p(x)))
            y <-- right(p(p(x)))
            if color(y)==Red  
                color(p(x)) <-- Black
                color(y) <-- Black
                color(p(p(x))) <-- Red
                x <-- p(p(x))
            else
                if x==right(p(x))
                    x <-- p(x)
                    RotateLeft(T,x)
                color(p(x)) <-- Black
                color(p(p(x))) <-- Red
                RotateRight(T, p(p(x)))
        else
            /* this is the same as the "then" clause,
             * with "right" and "left" interchanged */
    color(root(T)) <-- Black
}
 


[Example 2: Delete operation, in pseudocode]
 
RedBlackDelete(T,z)
{
    if left(z)==nil(T) or right(z)==nil(T)
        y <-- z
    else
        y <-- TreeSuccessor(z)
    if left(y) != nil(T)
        x <-- left(y)
    else
        x <-- right(y)
    p(x) <-- p(y)
    if p(y) == nil(T)
       root(T) <-- x
    else
       if y==left(p(y))
          left(p(x)) <-- x
       else
          right(p(y)) <-- x
    if y != z
       key(z) <-- key(y)
       /* if y has other fields, copy them too */
    if color(y)==Black
       then RBDeleteFixup(T,x)
}
RBDeleteFixup(T,x)
{
     while x != root(T) and color(x)==Black
        if x==left(p(x))
            w <-- right(p(x))
            if color(w) <-- Black
               color(p(x)) <-- Red
               RotateLeft(T,p(x))
               w <-- right(p(x))
            if color(left(w)) == Black and color(right(w))==Black
               color(w) <-- Red
               x <-- parent(x)
            else 
               if color(right(w)) == Black
                  color(left(w)) <-- Black
                  color(w) <-- Red
                  RotateRight(T,w)
                  w <-- right(p(x))
               color(w) <-- color(p(x))
               color(p(x)) <-- Black
               color(right(w)) <-- Black
               RotateLeft(T,p(x))
               x <-- root(T)

         else
            /* this is same as "then" clause,
             * except that right and left are exchanged */
     color(x) <--Black
}