LLRBTree implementation in C#

Readme.md

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.

LLRBTree.cs

/// 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;
        }
    }
}