Red black trees

Red/Black Trees

C#

// 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) { }
}

Standard ML

(* 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