Red black trees

Red/Black Trees

C#

<lang csharp>// Set6 - Red/Black (3State) Sets

using System; using System.Collections.Generic;

public enum Direction { FromLeft, FromRight };

public enum TriState {

   Header,
   Red,
   Black

}

public class Node {

   public Node Left;
   public Node Right;
   public Node Parent;
   public TriState Color;

   public bool IsHeader
   { get { return Color == TriState.Header; } }

}

public class SetNode<T> : Node {

   public T Data;

   public SetNode()
   {
       Left = this;
       Right = this;
       Parent = null;
       Color = TriState.Header;
   }

   public SetNode(T t)
   {
       Left = null;
       Right = null;
       Color = TriState.Black;
       Data = t;
   }

}

class Utility {

   public static ulong Depth(Node Root)
   {
       if (Root != null)
       {
           ulong Left = Root.Left != null ? Depth(Root.Left) : 0;
           ulong Right = Root.Right != null ? Depth(Root.Right) : 0;
           return Left < Right ? Right + 1 : Left + 1;
       }
       else
           return 0;
   }

   public static ulong Paths(Node Root, ulong weight)
   {
       if (Root != null)
       {
           ulong Left = Root.Left != null ? Paths(Root.Left, weight + 1) : 0;
           ulong Right = Root.Right != null ? Paths(Root.Right, weight + 1) : 0;
           return Left + Right + weight;
       }
       else
           return 0;
   }

   public static Node PreviousItem(Node Node)
   {
       if (Node.IsHeader) { return Node.Right; }

       if (Node.Left != null)
       {
           Node = Node.Left;
           while (Node.Right != null) Node = Node.Right;
       }
       else
       {
           Node y = Node.Parent;
           if (y.IsHeader) return y;
           while (Node == y.Left) { Node = y; y = y.Parent; }
           Node = y;
       }
       return Node;
   }

   public static Node NextItem(Node Node)
   {
       if (Node.IsHeader) return Node.Left;

       if (Node.Right != null)
       {
           Node = Node.Right;
           while (Node.Left != null) Node = Node.Left;
       }
       else
       {
           Node y = Node.Parent;
           if (y.IsHeader) return y;
           while (Node == y.Right) { Node = y; y = y.Parent; }
           Node = y;
       }
       return Node;
   }

   static Node Minimum(Node x)
   {
       while (x.Left != null) x = x.Left;
       return x;
   }

   static Node Maximum(Node x)
   {
       while (x.Right != null) x = x.Right;
       return x;
   }

   static void RotateLeft(Node x,
                          ref Node Root)
   {
       Node y = x.Right;

       x.Right = y.Left;
       if (y.Left != null)
           y.Left.Parent = x;
       y.Parent = x.Parent;

       if (x == Root)
           Root = y;
       else if (x == x.Parent.Left)
           x.Parent.Left = y;
       else
           x.Parent.Right = y;
       y.Left = x;
       x.Parent = y;
   }

   static void RotateRight(Node x,
                           ref Node Root)
   {
       Node y = x.Left;

       x.Left = y.Right;
       if (y.Right != null)
           y.Right.Parent = x;
       y.Parent = x.Parent;

       if (x == Root)
           Root = y;
       else if (x == x.Parent.Right)
           x.Parent.Right = y;
       else
           x.Parent.Left = y;
       y.Right = x;
       x.Parent = y;
   }

   public static void Rebalance(Node x,
                                ref Node Root)
   {
       x.Color = TriState.Red;
       while (x != Root && x.Parent.Color == TriState.Red)
       {
           if (x.Parent == x.Parent.Parent.Left)
           {
               Node y = x.Parent.Parent.Right;
               if (y != null && y.Color == TriState.Red)
               {
                   x.Parent.Color = TriState.Black;
                   y.Color = TriState.Black;
                   x.Parent.Parent.Color = TriState.Red;
                   x = x.Parent.Parent;
               }
               else
               {
                   if (x == x.Parent.Right)
                   {
                       x = x.Parent;
                       RotateLeft(x, ref Root);
                   }
                   x.Parent.Color = TriState.Black;
                   x.Parent.Parent.Color = TriState.Red;
                   RotateRight(x.Parent.Parent, ref Root);
               }
           }
           else
           {
               Node y = x.Parent.Parent.Left;
               if (y != null && y.Color == TriState.Red)
               {
                   x.Parent.Color = TriState.Black;
                   y.Color = TriState.Black;
                   x.Parent.Parent.Color = TriState.Red;
                   x = x.Parent.Parent;
               }
               else
               {
                   if (x == x.Parent.Left)
                   {
                       x = x.Parent;
                       RotateRight(x, ref Root);
                   }
                   x.Parent.Color = TriState.Black;
                   x.Parent.Parent.Color = TriState.Red;
                   RotateLeft(x.Parent.Parent, ref Root);
               }
           }
       }
       Root.Color = TriState.Black;
   }

   static void TSwap<X>(ref X u, ref X v) { X t = u; u = v; v = t; }

   public static Node RebalanceForRemove(Node z,
                                         ref Node Root,
                                         ref Node Leftmost,
                                         ref Node Rightmost)
   {
       Node y = z;
       Node x = null;
       Node x_Parent = null;

       if (y.Left == null)
           x = y.Right;
       else
           if (y.Right == null)
               x = y.Left;
           else
           {
               y = y.Right;
               while (y.Left != null) y = y.Left;
               x = y.Right;
           }

       if (y != z)
       {
           z.Left.Parent = y;
           y.Left = z.Left;
           if (y != z.Right)
           {
               x_Parent = y.Parent;
               if (x != null) x.Parent = y.Parent;
               y.Parent.Left = x;
               y.Right = z.Right;
               z.Right.Parent = y;
           }
           else
               x_Parent = y;

           if (Root == z)
               Root = y;
           else if (z.Parent.Left == z)
               z.Parent.Left = y;
           else
               z.Parent.Right = y;
           y.Parent = z.Parent;
           TSwap(ref y.Color, ref z.Color);
           y = z;
       }
       else  // y == z
       {
           x_Parent = y.Parent;
           if (x != null) x.Parent = y.Parent;
           if (Root == z)
               Root = x;
           else
               if (z.Parent.Left == z)
                   z.Parent.Left = x;
               else
                   z.Parent.Right = x;
           if (Leftmost == z)
               if (z.Right == null)
                   Leftmost = z.Parent;
               else
                   Leftmost = Minimum(x);
           if (Rightmost == z)
               if (z.Left == null)
                   Rightmost = z.Parent;
               else
                   Rightmost = Maximum(x);
       }
       if (y.Color != TriState.Red)
       {
           while (x != Root && (x == null || x.Color == TriState.Black))
               if (x == x_Parent.Left)
               {
                   Node w = x_Parent.Right;
                   if (w.Color == TriState.Red)
                   {
                       w.Color = TriState.Black;
                       x_Parent.Color = TriState.Red;
                       RotateLeft(x_Parent, ref Root);
                       w = x_Parent.Right;
                   }
                   if ((w.Left == null || w.Left.Color == TriState.Black) &&
                       (w.Right == null || w.Right.Color == TriState.Black))
                   {
                       w.Color = TriState.Red;
                       x = x_Parent;
                       x_Parent = x_Parent.Parent;
                   }
                   else
                   {
                       if (w.Right == null || w.Right.Color == TriState.Black)
                       {
                           if (w.Left != null) w.Left.Color = TriState.Black;
                           w.Color = TriState.Red;
                           RotateRight(w, ref Root);
                           w = x_Parent.Right;
                       }
                       w.Color = x_Parent.Color;
                       x_Parent.Color = TriState.Black;
                       if (w.Right != null) w.Right.Color = TriState.Black;
                       RotateLeft(x_Parent, ref Root);
                       break;
                   }
               }
               else
               {
                   Node w = x_Parent.Left;
                   if (w.Color == TriState.Red)
                   {
                       w.Color = TriState.Black;
                       x_Parent.Color = TriState.Red;
                       RotateRight(x_Parent, ref Root);
                       w = x_Parent.Left;
                   }
                   if ((w.Right == null || w.Right.Color == TriState.Black) &&
                       (w.Left == null || w.Left.Color == TriState.Black))
                   {
                       w.Color = TriState.Red;
                       x = x_Parent;
                       x_Parent = x_Parent.Parent;
                   }
                   else
                   {
                       if (w.Left == null || w.Left.Color == TriState.Black)
                       {
                           if (w.Right != null) w.Right.Color = TriState.Black;
                           w.Color = TriState.Red;
                           RotateLeft(w, ref Root);
                           w = x_Parent.Left;
                       }
                       w.Color = x_Parent.Color;
                       x_Parent.Color = TriState.Black;
                       if (w.Left != null) w.Left.Color = TriState.Black;
                       RotateRight(x_Parent, ref Root);
                       break;
                   }
               }
           if (x != null) x.Color = TriState.Black;
       }
       return y;
   }

   public static int BlackCount(Node Node, Node Root)
   {
       if (Node == null)
           return 0;
       else
       {
           int count = Node.Color == TriState.Black ? 1 : 0;

           if (Node == Root)
               return count;
           else
               return count + BlackCount(Node.Parent, Root);
       }
   }

}

public struct SetEntry<T> : IEnumerator<T> {

   public SetEntry(SetNode<T> n) { Node = n; }

   public T Value { get { return Node.Data; } }

   public bool IsEnd { get { return Node.IsHeader; } }

   public bool MoveNext()
   {
       Node = (SetNode<T>)Utility.NextItem(Node);
       return Node.IsHeader ? false : true;
   }

   public bool MovePrevious()
   {
       Node = (SetNode<T>)Utility.PreviousItem(Node);
       return Node.IsHeader ? false : true;
   }

   public void Reset()
   {
       while (!MoveNext()) ;
   }

   object System.Collections.IEnumerator.Current { get { return Node.Data; } }

   T IEnumerator<T>.Current { get { return Node.Data; } }

   public static bool operator ==(SetEntry<T> x, SetEntry<T> y) { return x.Node == y.Node; }
   public static bool operator !=(SetEntry<T> x, SetEntry<T> y) { return x.Node != y.Node; }

   public override string ToString() { return Value.ToString(); }

   public void Dispose() { }

   public SetNode<T> Node;

}

class Set<T> : IEnumerable<T> {

   IComparer<T> Comparer;
   SetNode<T> Header;
   ulong Nodes;

   //*** Constructors/Destructor ***

   public Set()
   {
       Comparer = Comparer<T>.Default;
       Header = new SetNode<T>();
       Nodes = 0;
   }

   public Set(IComparer<T> c)
   {
       Comparer = c;
       Header = new SetNode<T>();
       Nodes = 0;
   }

   //*** Properties ***

   SetNode<T> Root
   {
       get { return (SetNode<T>)Header.Parent; }
       set { Header.Parent = value; }
   }

   SetNode<T> LeftMost
   {
       get { return (SetNode<T>)Header.Left; }
       set { Header.Left = value; }
   }

   SetNode<T> RightMost
   {
       get { return (SetNode<T>)Header.Right; }
       set { Header.Right = value; }
   }

   public SetEntry<T> Begin
   { get { return new SetEntry<T>((SetNode<T>)Header.Left); } }

   public SetEntry<T> End
   { get { return new SetEntry<T>(Header); } }

   public ulong Length { get { return Nodes; } }

   public ulong Depth { get { return Utility.Depth(Root); } }

   //*** Indexer ***

   public bool this[T Key]
   {
       get
       {
           SetNode<T> Node = Search(Key);
           if (Node == null) return false; else return true;
       }
   }

   //*** Methods ***

   SetNode<T> Add(T Key,
                  SetNode<T> y,
                  Direction From)
   {
       SetNode<T> z = new SetNode<T>(Key);
       Nodes++;

       if (y == Header)
       {
           Root = z;
           RightMost = z;
           LeftMost = z;
       }
       else if (From == Direction.FromLeft)
       {
           y.Left = z;
           if (y == LeftMost) LeftMost = z;
       }
       else
       {
           y.Right = z;
           if (y == RightMost) RightMost = z;
       }

       z.Parent = y;
       Utility.Rebalance(z, ref Header.Parent);
       return z;
   }

   public SetNode<T> Add(T Key)
   {
       SetNode<T> y = Header;
       SetNode<T> x = Root;

       int c = -1;
       while (x != null)
       {
           y = x;
           c = Comparer.Compare(Key, x.Data);
           if (c < 0)
               x = (SetNode<T>)x.Left;
           else if (c > 0)
               x = (SetNode<T>)x.Right;
           else
               throw new EntryAlreadyExistsException();
        }

       Direction From = c < 0 ? Direction.FromLeft : Direction.FromRight;
       return Add(Key, y, From);
   }

   System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
   { return new SetEntry<T>(Header); }

   IEnumerator<T> IEnumerable<T>.GetEnumerator()
   { return new SetEntry<T>(Header); }

   public void Remove(T Key)
   {
       SetNode<T> root = Root;

       for (; ; )
       {
           if (root == null)
               throw new EntryNotFoundException();

           int Compare = Comparer.Compare(Key, root.Data);

           if (Compare < 0)
               root = (SetNode<T>)root.Left;

           else if (Compare > 0)
               root = (SetNode<T>)root.Right;

           else // Item is found
           {
               Utility.RebalanceForRemove(root, ref Header.Parent, ref Header.Left, ref Header.Right);
               Nodes--;
               break;
           }
       }
   }

   public SetNode<T> Search(T Key)
   {
       if (Root == null)
           return null;
       else
       {
           SetNode<T> search = Root;

           do
           {
               long result = Comparer.Compare(Key, search.Data);

               if (result < 0) search = (SetNode<T>)search.Left;

               else if (result > 0) search = (SetNode<T>)search.Right;

               else break;

           } while (search != null);

           return search;
       }
   }

   public override string ToString()
   {
       string StringOut = "{";

       SetEntry<T> start = Begin;
       SetEntry<T> end = End;
       SetEntry<T> last = End; last.MovePrevious();

       while (start != end)
       {
           string NewStringOut = start.Value.ToString();
           if (start != last) NewStringOut = NewStringOut + ",";
           StringOut = StringOut + NewStringOut;
           start.MoveNext();
       }

       StringOut = StringOut + "}";
       return StringOut;
   }

   public void Validate()
   {
       if (Nodes == 0 || Root == null)
       {
           if (Nodes != 0) { throw new InvalidEmptySetException(); }
           if (Root != null) { throw new InvalidEmptySetException(); }
           if (Header.Left != Header) { throw new InvalidEndItemException(); }
           if (Header.Right != Header) { throw new InvalidEndItemException(); }
       }

       int Length = Utility.BlackCount(LeftMost, Root);

       for (SetEntry<T> Iterator = Begin; Iterator != End; Iterator.MoveNext())
       {
           SetNode<T> x = Iterator.Node;
           SetNode<T> L = (SetNode<T>)x.Left;
           SetNode<T> R = (SetNode<T>)x.Right;

           if (x.Color == TriState.Red)
               if ((L != null && L.Color == TriState.Red) ||
                   (R != null && R.Color == TriState.Red))
                   throw new InvalidNodeColorException();

           if (L != null && Comparer.Compare(x.Data, L.Data) <= 0)
               throw new OutOfKeyOrderException();

           if (R != null && Comparer.Compare(R.Data, x.Data) <= 0)
               throw new OutOfKeyOrderException();

           if (L == null && R == null &&
               Utility.BlackCount(x, Root) != Length)
               throw new InvalidBlackCountException();
       }

       if (Root != null)
       {
           SetNode<T> x = Root;
           while (x.Left != null) x = (SetNode<T>)x.Left;

           if (LeftMost != x) throw new InvalidEndItemException();

           SetNode<T> y = Root;
           while (y.Right != null) y = (SetNode<T>)y.Right;

           if (RightMost != y) throw new InvalidEndItemException();
       }
   }

}

class Program {

   static void Main()
   {
       Set<string> S = new Set<string>();

       for (int i = 0; i < 10; i++)
           S.Add("S" + i.ToString());

       Console.WriteLine("Depth = {0}", S.Depth);

       S.Validate();

       for (int i = 0; i < 10; i += 2)
           S.Remove("S" + i.ToString());

       Console.WriteLine("Depth = {0}", S.Depth);

       S.Validate();

       foreach (string Str in S)
           Console.WriteLine("{0}", Str);

       if (S["S" + 3.ToString()])
           Console.WriteLine("{0} is in {1}", "S" + 3.ToString(), S);
       else
           Console.WriteLine("{0} is not in {1}", "S" + 3.ToString(), S);
   }

}

public class EntryNotFoundException : Exception {

   static String message = "The requested entry could not be located in the specified collection.";

   public EntryNotFoundException() : base(message) { }

}

public class InvalidEndItemException : Exception {

   static String message = "The validation routines detected that the end item of a tree is invalid.";

   public InvalidEndItemException() : base(message) { }

}

public class InvalidEmptySetException : Exception {

   static String message = "The validation routines detected that an empty tree is invalid.";

   public InvalidEmptySetException() : base(message) { }

}

public class OutOfKeyOrderException : Exception {

   static String message = "A trees was found to be out of Key order.";

   public OutOfKeyOrderException() : base(message) { }

}

public class SetInvalidParentException : Exception {

   static String message = "The validation routines detected that the Parent structure of a tree is invalid.";

   public SetInvalidParentException() : base(message) { }

}

public class InvalidBlackCountException : Exception {

   static String message = "An invalid black node count was encountered.";

   public InvalidBlackCountException() : base(message) { }

}

public class InvalidNodeColorException : Exception {

   static String message = "The color of a node is invalid.";

   public InvalidNodeColorException() : base(message) { }

}

public class EntryAlreadyExistsException : Exception {

   static String message = "The set entry already exists.";

   public EntryAlreadyExistsException() : base(message) { }

}</lang>

Standard ML

<lang sml>(* These red-black trees are manipulated using zippers.

* It is up to the user to insert the elements in the correct place.
* However, the implementation guarantees that, when a tree is rebalanced,
* the relative order of the elements will be respected.
*)

signature SEARCH_TREE = sig

 type 'a tree
 type 'a leaf
 type 'a hole
 
 datatype 'a focus = Leaf of 'a leaf | Node of 'a * 'a hole
 
 val empty : 'a tree
 
 val root : 'a tree -> 'a focus
 val left : 'a * 'a hole -> 'a focus
 val right : 'a * 'a hole -> 'a focus
 
 val insert : 'a * 'a leaf -> 'a tree
 val update : 'a * 'a hole -> 'a tree
 val delete : 'a hole -> 'a tree
 val splay : 'a leaf -> 'a tree
 
 val fromAsc : 'a list -> 'a tree
 val fromDesc : 'a list -> 'a tree

end

structure RedBlackTree :> SEARCH_TREE = struct

 datatype 'a tree
   = Empty
   | Red of 'a tree * 'a * 'a tree
   | Black of 'a tree * 'a * 'a tree
 
 val empty = Empty
 fun pure x = Red (Empty, x, Empty)
 
 fun l2 ((a,x,b),y,c) = (a, x, Red (b,y,c))
 fun r2 (a,x,(b,y,c)) = (Red (a,x,b), y, c)
 
 fun u3 (a,x,b,y,c) = Black (a, x, Red (b,y,c))
 fun l3 (a,x,b,y,c) = Red (Black a, x, Black (b,y,c))
 fun r3 (a,x,b,y,c) = Red (Black (a,x,b), y, Black c)
 fun m3 (a,x,(b,y,c),z,d) = Red (Black (a,x,b), y, Black (c,z,d))
 
 datatype 'a step = L of 'a * 'a tree | R of 'a tree * 'a | T | W
 
 fun upd (Red xs, T :: ss) = upd (Black xs, ss)
   | upd (a, L (x,b) :: ss) = upd (Red (a,x,b), ss)
   | upd (b, R (a,x) :: ss) = upd (Red (a,x,b), ss)
   | upd (xs, _) = xs
 
 fun ins (Red a, L (x,b) :: L (y,c) :: T :: ss) = ins (l3 (a,x,b,y,c), ss)
   | ins (Red b, R (a,x) :: L (y,c) :: T :: ss) = ins (m3 (a,x,b,y,c), ss)
   | ins (Red b, L (y,c) :: R (a,x) :: T :: ss) = ins (m3 (a,x,b,y,c), ss)
   | ins (Red c, R (b,y) :: R (a,x) :: T :: ss) = ins (r3 (a,x,b,y,c), ss)
   | ins (Red xs, nil) = Black xs
   | ins xs = upd xs
 
 fun del (a, T :: L (x, Red (b,y,c)) :: ss) = del (a, T :: L (x,b) :: L (y,c) :: ss)
   | del (c, T :: R (Red (a,x,b), y) :: ss) = del (c, T :: R (b,y) :: R (a,x) :: ss)
   | del (a, T :: L (x, Black (Red b,y,c)) :: ss) = upd (m3 (a,x,b,y,c), ss)
   | del (c, T :: R (Black (a,x,Red b), y) :: ss) = upd (m3 (a,x,b,y,c), ss)
   | del (a, T :: L (x, Black b) :: ss) = del (Black (r2 (a,x,b)), ss)
   | del (b, T :: R (Black a, x) :: ss) = del (Black (l2 (a,x,b)), ss)
   | del xs = upd xs
 
 fun old (Red b, W :: L (y,c) :: R (a,x) :: ss) = old (m3 (a,x,b,y,c), ss)
   | old (Red a, W :: L (x,b) :: ss) = old (Red (l2 (a,x,b)), ss)
   | old (Red b, W :: R (a,x) :: ss) = old (Red (r2 (a,x,b)), ss)
   | old xs = upd xs
 
 fun new (b, W :: L (y,c) :: R (a,x) :: ss) = new (u3 (a,x,b,y,c), ss)
   | new (a, W :: L (x,b) :: ss) = old (Red (a,x,b), ss)
   | new (b, W :: R (a,x) :: ss) = old (Red (a,x,b), ss)
   | new xs = del xs
 
 fun cut (Black (a,x,b), Black (c,y,d), ss) = cut (b, c, W :: L (y,d) :: R (a,x) :: ss)
   | cut (a, Red (b,x,c), ss) = cut (a, b, W :: L (x,c) :: ss)
   | cut (Red (a,x,b), c, ss) = cut (b, c, W :: R (a,x) :: ss)
   | cut (xs, _, ss) = new (xs, ss)
 
 type 'a leaf = 'a step list
 type 'a hole = 'a tree * 'a tree * 'a step list
 
 fun splay ss = upd (Empty, ss)
 fun update (x, (a, b, ss)) = upd (Red (a,x,b), ss)
 fun insert (x, ss) = ins (pure x, ss)
 val delete = cut
 
 datatype 'a focus = Leaf of 'a leaf | Node of 'a * 'a hole
 
 fun focus (Empty, ss) = Leaf ss
   | focus (Red (a,x,b), ss) = Node (x, (a, b, ss))
   | focus (Black (a,x,b), ss) = Node (x, (a, b, T :: ss))
 
 fun root xs = focus (xs, nil)
 fun left (x, (a, b, ss)) = focus (a, L (x,b) :: ss)
 fun right (x, (a, b, ss)) = focus (b, R (a,x) :: ss)
 
 datatype 'a step = ^ of 'a tree * 'a
 
 fun upd (a ^ x, b) = Black (a,x,b)
 fun rot (a ^ x, b ^ y) = Red (a,x,b) ^ y
 fun cut (us, vs) = foldl op:: us vs
 fun ins (Red a ^ x :: us, vs) = ins (us, Black a ^ x :: vs)
   | ins (u :: us, v :: vs) = cut (us, rot (u, v) :: vs)
   | ins xs = cut xs
 
 fun cons (x, ss) = ins (ss, Empty ^ x :: nil)
 fun fromAsc xs = foldl upd Empty (foldl cons nil xs)
 
 datatype 'a step = ^ of 'a * 'a tree
 
 fun upd (x ^ b, a) = Black (a,x,b)
 fun rot (x ^ a, y ^ b) = x ^ Red (a,y,b)
 fun cut (us, vs) = foldl op:: vs us
 fun ins (us, x ^ Red a :: vs) = ins (x ^ Black a :: us, vs)
   | ins (u :: us, v :: vs) = cut (rot (u, v) :: us, vs)
   | ins xs = cut xs
 
 fun cons (x, ss) = ins (x ^ Empty :: nil, ss)
 fun fromDesc xs = foldl upd Empty (foldl cons nil xs)

end</lang>