Skip to content

Instantly share code, notes, and snippets.

@maxpert maxpert/LLRBTree.cs
Last active Feb 22, 2016

Embed
What would you like to do?
LLRBTree implementation in C#

LL Red-Black Tree implementation in C-Sharp

I was greatly inspired by the left leaning red-black tree. As an excercise I decided to implement one for myself in C#. Turns out it's pretty solid in turns of both performance and stability, so I decided to publish the source code of implementation. Read the (Paper)[http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf] for more details. It contains basic CRUD methods, and since it's generic you can store and retrieve anything efficently O(lg(n)). Feel free to use the code and contribute.

/// Copyright Zohaib Sibte Hassan under Apache 2.0 License http://www.apache.org/licenses/LICENSE-2.0
using System;
namespace sibte.so
{
public class LLRBTree<K, V> where K : IComparable
{
private const bool RED = true;
private const bool BLACK = false;
internal class Node
{
public V Value;
internal K Key;
internal bool Color;
internal Node Left;
internal Node Right;
public Node(K key, V val)
{
this.Key = key;
this.Value = val;
this.Color = RED;
this.Left = null;
this.Right = null;
}
}
private Node rootNode;
internal Node Root => this.rootNode;
public V Search(K key, V defaultVal)
{
Node r = this.rootNode;
while (r != null)
{
int cmp = r.Key.CompareTo(key);
if (cmp == 0)
{
return r.Value;
}
if (cmp < 0)
{
r = r.Left;
}
else
{
r = r.Right;
}
}
return defaultVal;
}
public void Insert(K key, V val)
{
this.rootNode = LLRBTree<K, V>.Insert(this.rootNode, key, val);
this.rootNode.Color = BLACK;
}
public void DeleteMin()
{
Node deletedNode;
this.rootNode = LLRBTree<K, V>.DeleteMin(this.rootNode, out deletedNode);
if (this.rootNode != null)
{
this.rootNode.Color = BLACK;
}
}
public void Delete(K key)
{
this.rootNode = LLRBTree<K, V>.Delete(this.rootNode, key);
if (rootNode != null)
{
this.rootNode.Color = BLACK;
}
}
private static Node Insert(Node p, K key, V val)
{
if (p == null)
{
return new Node(key, val);
}
if (LLRBTree<K, V>.IsRed(p.Left) && LLRBTree<K, V>.IsRed(p.Right))
{
LLRBTree<K, V>.FlipColors(p);
}
int cmp = key.CompareTo(p.Key);
if (cmp == 0)
{
p.Value = val;
}
if (cmp < 0)
{
p.Left = LLRBTree<K, V>.Insert(p.Left, key, val);
}
else
{
p.Right = LLRBTree<K, V>.Insert(p.Right, key, val);
}
if (LLRBTree<K, V>.IsRed(p.Right) && !LLRBTree<K, V>.IsRed(p.Left))
{
p = LLRBTree<K, V>.RotateLeft(p);
}
if (LLRBTree<K, V>.IsRed(p.Left) && LLRBTree<K, V>.IsRed(p.Left.Left))
{
p = LLRBTree<K, V>.RotateRight(p);
}
return p;
}
private static Node Delete(Node p, K key)
{
if (p == null)
{
return null;
}
if (key.CompareTo(p.Key) < 0)
{
if (p.Left == null)
{
return p;
}
if (!LLRBTree<K, V>.IsRed(p.Left) && p.Left != null && !LLRBTree<K, V>.IsRed(p.Left.Left))
{
p = LLRBTree<K, V>.MoveRedLeft(p);
}
p.Left = LLRBTree<K, V>.Delete(p.Left, key);
return LLRBTree<K, V>.Fix(p);
}
// Right side of tree
if (LLRBTree<K, V>.IsRed(p.Left))
{
p = LLRBTree<K, V>.RotateRight(p);
}
if (key.CompareTo(p.Key) == 0 && p.Right == null)
{
return null;
}
if (!LLRBTree<K, V>.IsRed(p.Right) && p.Right != null && !LLRBTree<K, V>.IsRed(p.Right.Left))
{
p = LLRBTree<K, V>.MoveRedRight(p);
}
if (key.CompareTo(p.Key) == 0)
{
Node deletedNode;
p.Right = LLRBTree<K, V>.DeleteMin(p.Right, out deletedNode);
if (deletedNode == null)
{
throw new ArgumentOutOfRangeException("Delete min node was null");
}
p.Value = deletedNode.Value;
p.Key = deletedNode.Key;
}
else
{
p.Right = LLRBTree<K, V>.Delete(p.Right, key);
}
return LLRBTree<K, V>.Fix(p);
}
private static Node DeleteMin(Node p, out Node deleted)
{
if (p == null)
{
deleted = null;
return null;
}
if (p.Left == null)
{
deleted = p;
return null;
}
if (!LLRBTree<K, V>.IsRed(p.Left) && !LLRBTree<K, V>.IsRed(p.Left.Left))
{
p = LLRBTree<K, V>.MoveRedLeft(p);
}
p.Left = LLRBTree<K, V>.DeleteMin(p.Left, out deleted);
return LLRBTree<K, V>.Fix(p);
}
private static Node Fix(Node p)
{
if (LLRBTree<K, V>.IsRed(p.Right))
{
p = LLRBTree<K, V>.RotateLeft(p);
}
if (LLRBTree<K, V>.IsRed(p.Left) && LLRBTree<K, V>.IsRed(p.Left.Left))
{
p = LLRBTree<K, V>.RotateRight(p);
}
if (LLRBTree<K, V>.IsRed(p.Left) && LLRBTree<K, V>.IsRed(p.Right))
{
LLRBTree<K, V>.FlipColors(p);
}
return p;
}
private static Node MoveRedLeft(Node p)
{
LLRBTree<K, V>.FlipColors(p);
if (LLRBTree<K, V>.IsRed(p.Right.Left))
{
p.Right = LLRBTree<K, V>.RotateRight(p.Right);
p = LLRBTree<K, V>.RotateLeft(p);
LLRBTree<K, V>.FlipColors(p);
}
return p;
}
private static Node MoveRedRight(Node p)
{
LLRBTree<K, V>.FlipColors(p);
if (LLRBTree<K, V>.IsRed(p.Left.Left))
{
p = LLRBTree<K, V>.RotateRight(p);
LLRBTree<K, V>.FlipColors(p);
}
return p;
}
private static void FlipColors(Node p)
{
p.Color = !p.Color;
p.Left.Color = !p.Left.Color;
p.Right.Color = !p.Right.Color;
}
private static Node RotateLeft(Node p)
{
var tmp = p.Right;
p.Right = tmp.Left;
tmp.Left = p;
tmp.Color = p.Color;
p.Color = RED;
return tmp;
}
private static Node RotateRight(Node p)
{
var tmp = p.Left;
p.Left = tmp.Right;
tmp.Right = p;
tmp.Color = p.Color;
p.Color = RED;
return tmp;
}
private static bool IsRed(Node p)
{
if (p == null)
{
return false;
}
return p.Color == RED;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.