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>