红黑树

y=x.right
x.right=y.left
if y.left!=T.nil
   y.left.p=x
y.p=x.p
if x.p==T.nil
   T.root=u
elseif x==x.p.left
   x.p.left=y
else x.p.right=y
y.left=x
x.p=y

y=T.nil
x=T.root
while x!=T.nil
   y=x
   if z.key<x.key
      x=x.left
   else x=x.right
z.p=y
if y==T.nil
   T.root=z
elseif z.key<y.key
   y.left=z
else y.right=z
z.left=T.nil
z.right=T.nil
z.color=RED
RB-INSERT-FIXUP(T,z)

while z.p.color==RED
   if z.p==z.p.p.left
      y=z.p.p.p.right
      if y.color==RED
         z.p.color=BLACK
         y.color=BLACK
         z.p.p.color=RED
         z=z.p.p
      elseif z==z.p.right
         z=z.p
         LEFT-ROTATE(T,z)
         z.p.color=BLACK
         z.p.p.color=RED
         RIGHT-ROTATE(T,z.p.p)
      else (same as then clause with "right" and "left" exchanged)
   T.root.color=BLACK

if u.p==T.nil
   T.root=v
elseif u==u.p.left
   u.p.left=v
else u.p.right=v
v.p=u.p

y=z
y-original-color=y.color
if z.left==T.nil
   x=z.right
   RB-TRANSPLANT(T,z,z.right)
elseif z.right==T.nil
   x=z.left
   RB-TRANSPLANT(T,z,z.left)
else
   y=TREE-MINIMUM(z.right)
   y-original-color=y.color
   x=y.right
   if y.p==z
      x.p=y
   else
      RB-TRANSPLANT(T,y,y.right)
      y.right=z.right
      y.right.p=y
   RB-TRANSPLANT(T,z,y)
   y.left=z.left
   y.left.p=y
   y.color=z.color
if y-original-color==BLACK
   RB-DELETE-FIXUP(T,x)

while x!=T.root and x.color==BLACK
   if(x==x.p.left)
      w=x.p.right
      if w.color==RED
         w.color=BLACK
         x.p.color=RED
         LEFT-ROTATE(T,x.p)
         w=x.p.right
      if w.left.color==BLACK and w.right.color==BLACK
         w.color=RED
         x=x.p
      else
         if w.right.color==BLACK
            w.left.color=BLACK
            w.color=RED
            RIGHT-ROTATE(T,w)
            w=x.p.right
         w.color=x.p.color
         x.p.color=BLACK
         w.right.color=BLACK
         LEFT-ROTATE(T,x.p)
         x=T.root
   else (same as then clause with "right" and "left" exchanged)
x.color=BLACK