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