Red-Black Tree in C#


Red-Black Trees are another self balancing binary search tree data structure.  Much like the AVL Tree which is also self balancing and has the same time complexity O(log n) for best, average & worst case. Red-Black Trees are a bit more efficient in insertion and deletion in that they require less work to be done, since the we don’t have to traverse the tree for imbalances, we simply look at the parent node colour and perform a fix.

I would highly recommend looking at the AVL Tree and how that works before implementing this, as it gives you a good idea of how it works in detail and will help in understanding the Red-Black Tree.

The Red-Black tree is defined by and must meet these requirements:

  • A node is either red or black. Meaning every node has a property that determines the colour, for example using an enum.
  • The root is always black. (This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice-versa, this rule has little effect on analysis.)
  • All leaves (NIL) are black. (All leaves are same colour as the root.)
  • Every red node must have two black child nodes.
  • Every path from a given node to any of its descendant leaves contains the same number of black nodes. (Any leaf node must have the same number of black parent nodes)
  • In the RB Tree balance is maintained by “painting” nodes red or black, and by performing necessary re-arrangements of nodes. Unlike the AVL Tree where balance is maintained by balance factor checking (using heights). Both however require rotation of nodes.

RB Tree operations:

  • Insertion: Insertion is somewhat different from the AVL Tree insertion. In the RB Tree, we first insert as we would normally in a binary search tree. Then we colour the newly inserted node red.  After this is done, we check for any violations. A violation is when the newly added node is the same colour as the parent node. Therefore we apply a fix.
  • Find: Again, just like the AVL Tree, since the RB Tree is already balanced searching is optimised therefore regular implementation of Find() is sufficient
  • Deletion: When we delete from RB Tree, if the node to be deleted was red, just delete it as in the BST case. If the to-be-deleted node is black, we empty of its value and associate the now valueless but still coloured node with whatever node comes to take its place (which could be a terminal node). If we allow the empty but coloured node to be counted when measuring the black-node-length of a simple path, we will have retained the original black height of the tree.  PLEASE SEE THIS FOR DELETION CASES AND ILLUSTRATIONS.
  • Rotations: rotations are done using 2 methods: LeftRotate() and RightRotate(). We use these instead of the AVL rotations (Right-Right, Right-Left, Left-Right, and Left-Left).

Insertion Cases:

  • Case 1:
    1. Uncle is Red

    • Solution for Case 1:
      1. Swap colors of Parent, Uncle, and Grandparent
      2. Grandparent becomes the new node to check for violations
  • Case 2:
    1. Uncle is Black
    2a. Node is a Left Child of a Right Child
    2b. Node is a Right Child of a Left Child

    • Solution for Case 2:
      1a. Right rotate around Parent for 2a = Go to Case 3
      1b. Left rotate around Parent for 2b = Go to Case 3
  • Case 3:
    1. Uncle is Black
    2a. Node is a Right Child of a Right Child
    2b. Node is a Left Child of a Left Child

    • Solution for Case 3:
      1a. Left rotate around Grandparent for 2a
      1b. Right rotate around Grandparent for 2b
      2. Swap colours of Parent and Grandparent
      3. Grandparent becomes the new node to check for violations

Illustrations for Insertion Cases

CaptureMethods used:

  • Insert(): a public and a private version of this method, private will do all the recursive work as well as call FixTree() to correct any violations that occur. Private takes a node reference/pointer that acts as the current node in traversal, and finally takes in another Node reference that points to a new node object to store in the tree.
  • InsertFixUp(): private method, takes a node reference/pointer and returns void. This method is called in Insert() and it is where we will determine if there are any violations in the tree; and performs necessary rotations/re-colouring. This method works by first checking whether we have a violation using a while loop, then we go and check all the cases 1, 2, and 3 and perform necessary fixes to restore the Red-Black property of the tree.
    • As shown on the illustrations above:
    • a. Node z is red.
      b. If z.p is the root, then z.parent is black.
      c. If the tree violates any of the red-black properties, then it violates at most
      one of them, and the violation is of either property 2 or property 4. If the
      tree violates property 2, it is because z is the root and is red. If the tree
      violates property 4, it is because both z and z.parent are red.
  • Find(): implementation as used in a regular BST since the RB tree is self balancing, searching is already optimised, takes a int parameter, and returns a reference to the Node found, if nothing found, then NULL is returned
  • DisplayTree(): simply calls a RecursiveInOrder() method to display the nodes onto the console window
  • Delete(): this method goes ahead and deletes as normal, then we call DeleteFixUp() to fix the tree should there be any violations & restore red-black tree properties.
  • DeleteFixUp(): this private method takes a node reference, and returns void. This method checks for any violations within the tree and performs a fix should there be any violations after a deletion has occurred.
  • Rotations: RightRotate() and LeftRotate() are implemented
  • TreeSuccessor(): takes a Node reference, and returns a Node reference, finds the successor for a given Node
  • Minimum(): Finds the minimum node in the/subtree of a given Node

Objects

  • Node: the node object in this implementation has 4 properties: a data field, a left pointer, a right pointer, and pointer to the parent node. The parent reference is important in this implementation as it will be used for checking violations.

 

Capture

Red-Black Tree illustration with black sentinel nodes (null)

 

Rotation Animation

Rotation Illustrations

Rotation Illustrations

Implementation in C# (please also see commenting on the code)

class Program
    {
        static void Main(string[] args)
        {
            RB tree = new RB();
            tree.Insert(5);
            tree.Insert(3);
            tree.Insert(7);
            tree.Insert(1);
            tree.Insert(9);
            tree.Insert(-1);
            tree.Insert(11);
            tree.Insert(6);
            tree.DisplayTree();
            tree.Delete(-1);
            tree.DisplayTree();
            tree.Delete(9);
            tree.DisplayTree();
            tree.Delete(5);
            tree.DisplayTree();
            Console.ReadLine();
        }
    }
    enum Color
    {
        Red,
        Black
    }
    class RB
    {
        /// <summary>
        /// Object of type Node contains 4 properties
        /// Colour
        /// Left
        /// Right
        /// Parent
        /// Data
        /// </summary>
        public class Node
        {
            public Color colour;
            public Node left;
            public Node right;
            public Node parent;
            public int data;

            public Node(int data) { this.data = data; }
            public Node(Color colour) { this.colour = colour; }
            public Node(int data, Color colour) { this.data = data; this.colour = colour; }
        }
        /// <summary>
        /// Root node of the tree (both reference & pointer)
        /// </summary>
        private Node root;
        /// <summary>
        /// New instance of a Red-Black tree object
        /// </summary>
        public RB() { }
        /// <summary>
        /// Left Rotate
        /// </summary>
        /// <param name="X"></param>
        /// <returns>void</returns>
        private void LeftRotate(Node X)
        {
            Node Y = X.right; // set Y
            X.right = Y.left;//turn Y's left subtree into X's right subtree
            if (Y.left != null)
            {
                Y.left.parent = X;
            }
            if (Y != null)
            {
                Y.parent = X.parent;//link X's parent to Y
            }
            if (X.parent == null)
            {
                root = Y;
            }
            if (X == X.parent.left)
            {
                X.parent.left = Y;
            }
            else
            {
                X.parent.right = Y;
            }
            Y.left = X; //put X on Y's left
            if (X != null)
            {
                X.parent = Y;
            }

        }
        /// <summary>
        /// Rotate Right
        /// </summary>
        /// <param name="Y"></param>
        /// <returns>void</returns>
        private void RightRotate(Node Y)
        {
            // right rotate is simply mirror code from left rotate
            Node X = Y.left;
            Y.left = X.right;
            if (X.right != null)
            {
                X.right.parent = Y;
            }
            if (X != null)
            {
                X.parent = Y.parent;
            }
            if (Y.parent == null)
            {
                root = X;
            }
            if (Y == Y.parent.right)
            {
                 Y.parent.right = X;
            }
            if(Y == Y.parent.left)
            {
                 Y.parent.left = X;
            }

            X.right = Y;//put Y on X's right
            if (Y != null)
            {
                Y.parent = X;
            }
        }
        /// <summary>
        /// Display Tree
        /// </summary>
        public void DisplayTree()
        {
            if (root == null)
            {
                Console.WriteLine("Nothing in the tree!");
                return;
            }
            if (root != null)
            {
                InOrderDisplay(root);
            }
        }
        /// <summary>
        /// Find item in the tree
        /// </summary>
        /// <param name="key"></param>
        public Node Find(int key)
        {
            bool isFound = false;
            Node temp = root;
            Node item = null;
            while (!isFound)
            {
                if (temp == null)
                {
                    break;
                }
                if (key < temp.data)
                {
                    temp = temp.left;
                }
                if (key > temp.data)
                {
                    temp = temp.right;
                }
                if (key == temp.data)
                {
                    isFound = true;
                    item = temp;
                }
            }
            if (isFound)
            {
                Console.WriteLine("{0} was found", key);
                return temp;
            }
            else
            {
                Console.WriteLine("{0} not found", key);
                return null;
            }
        }
        /// <summary>
        /// Insert a new object into the RB Tree
        /// </summary>
        /// <param name="item"></param>
        public void Insert(int item)
        {
            Node newItem = new Node(item);
            if (root == null)
            {
                root = newItem;
                root.colour = Color.Black;
                return;
            }
            Node Y = null;
            Node X = root;
            while (X != null)
            {
                Y = X;
                if (newItem.data < X.data)
                {
                    X = X.left;
                }
                else
                {
                    X = X.right;
                }
            }
            newItem.parent = Y;
            if (Y == null)
            {
                root = newItem;
            }
            else if (newItem.data < Y.data)
            {
                Y.left = newItem;
            }
            else
            {
                Y.right = newItem;
            }
            newItem.left = null;
            newItem.right = null;
            newItem.colour = Color.Red;//colour the new node red
            InsertFixUp(newItem);//call method to check for violations and fix
        }
        private void InOrderDisplay(Node current)
        {
            if (current != null)
            {
                InOrderDisplay(current.left);
                Console.Write("({0}) ", current.data);
                InOrderDisplay(current.right);
            }
        }
        private void InsertFixUp(Node item)
        {
            //Checks Red-Black Tree properties
            while (item != root && item.parent.colour == Color.Red)
            {
                /*We have a violation*/
                if (item.parent == item.parent.parent.left)
                {
                    Node Y = item.parent.parent.right;
                    if (Y != null && Y.colour == Color.Red)//Case 1: uncle is red
                    {
                        item.parent.colour = Color.Black;
                        Y.colour = Color.Black;
                        item.parent.parent.colour = Color.Red;
                        item = item.parent.parent;
                    }
                    else //Case 2: uncle is black
                    {
                        if (item == item.parent.right)
                        {
                            item = item.parent;
                            LeftRotate(item);
                        }
                        //Case 3: recolour & rotate
                    item.parent.colour = Color.Black;
                    item.parent.parent.colour = Color.Red;
                    RightRotate(item.parent.parent);
                    }

                }
                else
                {
                    //mirror image of code above
                    Node X = null;

                    X = item.parent.parent.left;
                    if (X != null && X.colour == Color.Black)//Case 1
                    {
                         item.parent.colour = Color.Red;
                         X.colour = Color.Red;
                         item.parent.parent.colour = Color.Black;
                         item = item.parent.parent;
                    }
                    else //Case 2
                    {
                        if (item == item.parent.left)
                        {
                            item = item.parent;
                            RightRotate(item);
                        }
                        //Case 3: recolour & rotate
                    item.parent.colour = Color.Black;
                    item.parent.parent.colour = Color.Red;
                    LeftRotate(item.parent.parent);

                    }

                }
                root.colour = Color.Black;//re-colour the root black as necessary
            }
        }
        /// <summary>
        /// Deletes a specified value from the tree
        /// </summary>
        /// <param name="item"></param>
        public void Delete(int key)
        {
            //first find the node in the tree to delete and assign to item pointer/reference
            Node item = Find(key);
            Node X = null;
            Node Y = null;

            if (item == null)
            {
                Console.WriteLine("Nothing to delete!");
                return;
            }
            if (item.left == null || item.right == null)
            {
                Y = item;
            }
            else
            {
                Y = TreeSuccessor(item);
            }
            if (Y.left != null)
            {
                X = Y.left;
            }
            else
            {
                X = Y.right;
            }
            if (X != null)
            {
                X.parent = Y;
            }
            if (Y.parent == null)
            {
                root = X;
            }
            else if (Y == Y.parent.left)
            {
                Y.parent.left = X;
            }
            else
            {
                Y.parent.left = X;
            }
            if (Y != item)
            {
                item.data = Y.data;
            }
            if (Y.colour == Color.Black)
            {
                DeleteFixUp(X);
            }

        }
        /// <summary>
        /// Checks the tree for any violations after deletion and performs a fix
        /// </summary>
        /// <param name="X"></param>
        private void DeleteFixUp(Node X)
        {

            while (X!= null && X != root && X.colour == Color.Black)
            {
                if (X == X.parent.left)
                {
                    Node W = X.parent.right;
                    if (W.colour == Color.Red)
                    {
                        W.colour = Color.Black; //case 1
                        X.parent.colour = Color.Red; //case 1
                        LeftRotate(X.parent); //case 1
                        W = X.parent.right; //case 1
                    }
                    if (W.left.colour == Color.Black && W.right.colour == Color.Black)
                    {
                        W.colour = Color.Red; //case 2
                        X = X.parent; //case 2
                    }
                    else if (W.right.colour == Color.Black)
                    {
                        W.left.colour = Color.Black; //case 3
                        W.colour = Color.Red; //case 3
                        RightRotate(W); //case 3
                        W = X.parent.right; //case 3
                    }
                    W.colour = X.parent.colour; //case 4
                    X.parent.colour = Color.Black; //case 4
                    W.right.colour = Color.Black; //case 4
                    LeftRotate(X.parent); //case 4
                    X = root; //case 4
                }
                else //mirror code from above with "right" & "left" exchanged
                {
                    Node W = X.parent.left;
                    if (W.colour == Color.Red)
                    {
                        W.colour = Color.Black;
                        X.parent.colour = Color.Red;
                        RightRotate(X.parent);
                        W = X.parent.left;
                    }
                    if (W.right.colour == Color.Black && W.left.colour == Color.Black)
                    {
                        W.colour = Color.Black;
                        X = X.parent;
                    }
                    else if (W.left.colour == Color.Black)
                    {
                        W.right.colour = Color.Black;
                        W.colour = Color.Red;
                        LeftRotate(W);
                        W = X.parent.left;
                    }
                    W.colour = X.parent.colour;
                    X.parent.colour = Color.Black;
                    W.left.colour = Color.Black;
                    RightRotate(X.parent);
                    X = root;
                }
            }
            if(X != null)
            X.colour = Color.Black;
        }
        private Node Minimum(Node X)
        {
            while (X.left.left != null)
            {
                X = X.left;
            }
            if (X.left.right != null)
            {
                X = X.left.right;
            }
            return X;
        }
        private Node TreeSuccessor(Node X)
        {
            if (X.left != null)
            {
                return Minimum(X);
            }
            else
            {
                Node Y = X.parent;
                while (Y != null && X == Y.right)
                {
                    X = Y;
                    Y = Y.parent;
                }
                return Y;
            }
        }
    }

Complexity Analysis:

  • Insertion: Best, average, worst – O(Log n)
  • Deletion: Best, average, worst – O(Log n)
  • Find: Best, average, worst – O(Log n)
  • Space: O(n)

Interactive Red-Black Tree Demo

Video Illustration of Red-Black Tree

Advertisements

6 thoughts on “Red-Black Tree in C#

  1. Pingback: AVL Tree in C# | Bits and Pieces of Code

  2. It doen’t work so good, it throw some exeptions, try with next values and you’ll see:
    tree.Insert(26);
    tree.Insert(56);
    tree.Insert(34);
    tree.Insert(98);
    tree.Insert(21);
    tree.Insert(14);
    tree.Insert(28);
    tree.Insert(92);
    tree.Insert(12);
    tree.Insert(45);

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s