Red-black Tree: A self - balanced tree

A red-black tree is a binary search tree in which each node is colored red or black such that

• The root is black
• The children of a red node are black
• Every root to leaf path has the same number of black nodes

Red-black tree do not necessarily have minimum height, but the height is never greater than 2 log(n), so it guarantees searching in O(log n) time. 

Let B be the number of black nodes in the shortest possible root to leaf path. Longer possible paths may be constructed by inserting red nodes ( since every path must have same number of black nodes). However, it is impossible to have two consecutive red nodes since the children of a red node must be black, thus the longest possible path consists of 2B nodes, alternating black and red. 

The helper methods

Since we will construct a self balanced tree, it is highly possible that when we insert or delete a node, the tree will be imbalanced, thus we need some methods to reconstruct the tree. 

Rotate right

This method is needed when we have two consecutive red nodes on the left. Since there is the rule that any red parents must have two black children, we need to rotate the tree to satisfy the rule. 

private ColoredTreeNode rotateRight(ColoredTreeNode node){
  ColoredTreeNode x = node.left;
  node.left = x.right;
  x.right = node;
  x.color = x.right.color;
  x.right.color = Color.red;
  x.numSubtree = node.numSubtree;
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return x;
 }

 Rotate Left

Update 2015 - 04 01:
This method is actually used when you insert a node to the right, especially when the root is red, or the root doesn't contain a left child, this node will balance the tree.


This method is used when the left child is black and the right child is red. The reason to perform this method is that since this is a left leaning tree, we want the left subtree to always be deeper than right subtree (if not equal to). Note that we don't really care if the parent is red or black. The following figure shows if we have a black parent. If we have a red parent, there is always a black parent of that red parent since the root of the tree is black, so after rotation, we will have two consecutive red left nodes, when we return to the parent's (the red one) parent (the black one), it will rotate right to maintain the correct order.

private ColoredTreeNode rotateLeft(ColoredTreeNode node){
  ColoredTreeNode x = node.right;
  node.right = x.left;
  x.left = node;
  x.color = x.left.color;
  x.left.color = Color.red;
  x.numSubtree = node.numSubtree;
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return x;
 }

Flip node
If both nodes are red, since next time we will add a red node, in order to reduce the re-construct steps, we flip the nodes and make leaf nodes black.

private void flipColors(ColoredTreeNode node){
  node.color = node.color == Color.red ? Color.black : Color.red;
  node.left.color = node.left.color == Color.red ? Color.black : Color.red;
  node.right.color = node.right.color == Color.red ? Color.black : Color.red; 
 }

Move Red Left
This method is used for deleting nodes. Assuming the node is red (we may set the root node to red if needed, see Deletion code below), if the node's left child and the left child's left child are both black, we move the node to the left.

private ColoredTreeNode moveRedLeft(ColoredTreeNode node){
  flipColors(node);
  if(isRed(node.right.left)){
   node.right = rotateRight(node.right);
   node = rotateLeft(node);
   flipColors(node);
  }
  return node;
 }

Move Red Right
This method is also used for deleting nodes. Assuming the node is red, if the node's right child and the right child's left child are both black, move the red node to the right.

private ColoredTreeNode moveRedRight(ColoredTreeNode node){
  flipColors(node);
  if(isRed(node.left.left)){
   node = rotateRight(node);
   flipColors(node);
  }
  return node;
 }

Search
Search a node follows the same rule as that in searching in a BST, since red-black tree is a BST.

public boolean contains(Comparable k) {
  return get(k) != null;
 }
 public Object get(Comparable key){
  return get(root, key);
 }
 private Object get(ColoredTreeNode node, Comparable k){
  while(node != null){
   int cmp = node.key.compareTo((T)k);
   if(cmp > 0) node = node.left;
   else if(cmp < 0) node = node.right;
   else return node.data;
  }
  return null;
 }

Insertion

1. The insertion to the tree first follows the traditional BST insertion rule, but color the newly inserted node to red. 
2. Since the children of a red node are black, if the parent of the node you've just inserted is red, you will have to readjust the color.
3. In case after you readjust the tree, the root of the tree is not black, color the root to black.

public void insert(Comparable k, Object obj){
  root = insert(k, obj, root);
  //System.out.println(root.key);
  root.color = Color.black;
 }
 private ColoredTreeNode insert(Comparable k, Object obj, ColoredTreeNode root){
  if(root == null){
   //System.out.println("Inserted new node!");
   return new ColoredTreeNode(k, obj, Color.red, 1);
  }
  int cmp = k.compareTo((T)root.key);
  if(cmp < 0)
   root.left = insert(k, obj, root.left);
  else if (cmp > 0)
   root.right = insert(k, obj, root.right);
  else
   root.data = obj;
  /*
   * rotate and re-adjust color
   */
  //the new added node is the right child 
  //of the root, since the tree is left leaning
  //we need to left rotate the tree
                //moreover, it can make the leaf node black
  if(isRed(root.right) && !isRed(root.left))
   root = rotateLeft(root);
  //two consecutive red nodes, rotate right
  if(isRed(root.left) && isRed(root.left.left))
   root = rotateRight(root);
  //a red node must have two black children
  //flip the color if a node have two red children
  //if the parent is black, and the parent's parent is 
  //red, flip the nodes will cause two red parents on the 
  //left, and the tree will rotate right to correct it
  if(isRed(root.left) && isRed(root.right))
   flipColors(root);
  root.numSubtree = size(root.left) + size(root.right) + 1;
  return root; 
 }

Deletion
Deletion is a little bit more complicated, I am going to use some illustrations.

1. Delete the left most leaf (node with the minimum key).

public void deleteMin(){
  if(isEmpty())
   throw new NoSuchElementException("Empty tree!");
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = deleteMin(root);
  if(!isEmpty())
   root.color = Color.black;
 }
 private ColoredTreeNode deleteMin(ColoredTreeNode node){
  if(node.left == null)
   return null;
  if(!isRed(node.left) && !isRed(node.left.left))
   node = moveRedLeft(node);
  node.left = deleteMin(node.left);
  return balance(node);
 }

2. Delete the right most leaf(node with the maximum key)

public void deleteMax(){
  if(isEmpty())
   throw new NoSuchElementException("Empty tree!");
  //delete a red node
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = deleteMax(root);
  if(!isEmpty()) 
   root.color = Color.black;
 }
 private ColoredTreeNode deleteMax(ColoredTreeNode node){
  //note the root is red from the above method
  if(isRed(node.left))
   root = rotateRight(node);
  //BST, max is always at right
  if(node.right == null)
   return null;
  if(!isRed(node.right) && !isRed(node.right.left))
   node = moveRedRight(node);
  node.right = deleteMax(node.right);
  return balance(node);
 }

3. Delete a node given a key

This follows the traditional BST deletion rule. Find the node, replace it with the node with the smallest key in the right subtree (or node with the largest key in the left subtree) and then recursively delete the replaced node. The recursion will follow either deleting the min (the left most leaf) or the max(deleting the right most leaf)'s rule. 

public void delete(Comparable key){
  if(!contains(key)){
   System.err.println("Symbol table does not contain " + key);
   return;
  }
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = delete(root, key);
  if(!isEmpty())
   root.color = Color.black;
  //assert check();
 }
 private ColoredTreeNode delete(ColoredTreeNode node, Comparable key){
  if(key.compareTo((T)node.key) < 0){
   if(!isRed(node.left) && !isRed(node.left.left))
    node = moveRedLeft(node);
   node.left = delete(node.left, key);
  }
  else {
   if(isRed(node.left))
    node = rotateRight(node);
   if(key.compareTo((T)node.key) == 0 && (node.right == null))
    return null;
   if(!isRed(node.right) && !isRed(node.right.left))
    node = moveRedRight(node);
   if(key.compareTo((T)node.key) == 0){
    //find minimum node in the right subtree
    ColoredTreeNode x = min(node.right);
    node.key = x.key;
    node.data = x.data;
    node.right = deleteMin(node.right);
   }
   else
    node.right = delete(node.right, key);
  }
  return balance(node); 
 }

The full source code (!)
I used the real "Color" in java.awt.Color class, which is not a very good idea. The color is represented using 3 1byte memory, one color will take 3 bytes. However, since we are only consider red and black in this case, a boolean variable red = true (or false), which only takes 1 bit, is enough. The source code can also be found on my Github.

package redBlackTree;

import java.awt.Color;
import java.util.*;

/**
 * This class implements a left leaning red-black tree
 * if there is an extra node, it will always be at the 
 * left side
 * @author shirleyyoung
 * @param 
 *
 * @param 
 */

public class RedBlackBST {
 private ColoredTreeNode root;
 
 /**
  * constructor
  */
 public RedBlackBST(){
  root = null;
  //System.out.println("New tree constructed!");
 }
 
 /************************************************
  * Search
  ************************************************/
 public boolean contains(Comparable k) {
  return get(k) != null;
 }
 public Object get(Comparable key){
  return get(root, key);
 }
 private Object get(ColoredTreeNode node, Comparable k){
  while(node != null){
   int cmp = node.key.compareTo((T)k);
   if(cmp > 0) node = node.left;
   else if(cmp < 0) node = node.right;
   else return node.data;
  }
  return null;
 }
 /*************************************************
  * insertion
  *************************************************/
 public void insert(Comparable k, Object obj){
  root = insert(k, obj, root);
  //System.out.println(root.key);
  root.color = Color.black;
  assert check();
 }
 private ColoredTreeNode insert(Comparable k, Object obj, ColoredTreeNode root){
  if(root == null){
   //System.out.println("Inserted new node!");
   return new ColoredTreeNode(k, obj, Color.red, 1);
  }
  int cmp = k.compareTo((T)root.key);
  if(cmp < 0)
   root.left = insert(k, obj, root.left);
  else if (cmp > 0)
   root.right = insert(k, obj, root.right);
  else
   root.data = obj;
  /*
   * rotate and re-adjust color
   */
  //the new added node is the right child 
  //of the root, since the tree is left leaning
  //we need to left rotate the tree
  if(isRed(root.right) && !isRed(root.left))
   root = rotateLeft(root);
  //two consecutive red nodes, rotate right
  if(isRed(root.left) && isRed(root.left.left))
   root = rotateRight(root);
  //a red node must have two black children
  //flip the color if a node have two red children
  //if the parent is black, and the parent's parent is 
  //red, flip the nodes will cause two red parents on the 
  //left, and the tree will rotate right to correct it
  if(isRed(root.left) && isRed(root.right))
   flipColors(root);
  root.numSubtree = size(root.left) + size(root.right) + 1;
  //System.out.println(root.key);
  return root; 
 }
 /*****************************************************
  * Deletion
  *****************************************************/
 /**
  * delete the node with minimum key
  */
 public void deleteMin(){
  if(isEmpty())
   throw new NoSuchElementException("Empty tree!");
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = deleteMin(root);
  if(!isEmpty())
   root.color = Color.black;
 }
 private ColoredTreeNode deleteMin(ColoredTreeNode node){
  if(node.left == null)
   return null;
  if(!isRed(node.left) && !isRed(node.left.left))
   node = moveRedLeft(node);
  node.left = deleteMin(node.left);
  return balance(node);
 }
 /**
  * delete the node with the maximum key
  */
 public void deleteMax(){
  if(isEmpty())
   throw new NoSuchElementException("Empty tree!");
  //delete a red node
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = deleteMax(root);
  if(!isEmpty()) 
   root.color = Color.black;
 }
 private ColoredTreeNode deleteMax(ColoredTreeNode node){
  //note the root is red from the above method
  if(isRed(node.left))
   root = rotateRight(node);
  //BST, max is always at right
  if(node.right == null)
   return null;
  if(!isRed(node.right) && !isRed(node.right.left))
   node = moveRedRight(node);
  node.right = deleteMax(node.right);
  return balance(node);
 }
 /**
  * delete a node given a key
  * @param key
  */
 public void delete(Comparable key){
  if(!contains(key)){
   System.err.println("Symbol table does not contain " + key);
   return;
  }
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = delete(root, key);
  if(!isEmpty())
   root.color = Color.black;
  assert check();
 }
 private ColoredTreeNode delete(ColoredTreeNode node, Comparable key){
  if(key.compareTo((T)node.key) < 0){
   if(!isRed(node.left) && !isRed(node.left.left))
    node = moveRedLeft(node);
   node.left = delete(node.left, key);
  }
  else {
   if(isRed(node.left))
    node = rotateRight(node);
   if(key.compareTo((T)node.key) == 0 && (node.right == null))
    return null;
   if(!isRed(node.right) && !isRed(node.right.left))
    node = moveRedRight(node);
   if(key.compareTo((T)node.key) == 0){
    //find minimum node in the right subtree
    ColoredTreeNode x = min(node.right);
    node.key = x.key;
    node.data = x.data;
    node.right = deleteMin(node.right);
   }
   else
    node.right = delete(node.right, key);
  }
  return balance(node); 
 }
 /**********************************************
  * reconstruct methods
  **********************************************/
 
 private ColoredTreeNode rotateRight(ColoredTreeNode node){
  ColoredTreeNode x = node.left;
  node.left = x.right;
  x.right = node;
  x.color = x.right.color;
  x.right.color = Color.red;
  x.numSubtree = node.numSubtree;
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return x;
 }
 
 private ColoredTreeNode rotateLeft(ColoredTreeNode node){
  ColoredTreeNode x = node.right;
  node.right = x.left;
  x.left = node;
  x.color = x.left.color;
  x.left.color = Color.red;
  x.numSubtree = node.numSubtree;
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return x;
 }
 /**
  * flip the color of the node and its children
  * @param node
  */
 private void flipColors(ColoredTreeNode node){
  node.color = node.color == Color.red ? Color.black : Color.red;
  node.left.color = node.left.color == Color.red ? Color.black : Color.red;
  node.right.color = node.right.color == Color.red ? Color.black : Color.red; 
 }
 /**
  * Assuming that node is red and both node.left and node.left.left
  * are black, make node.left or one of its children red
  * @param node
  * @return
  */
 private ColoredTreeNode moveRedLeft(ColoredTreeNode node){
  flipColors(node);
  if(isRed(node.right.left)){
   node.right = rotateRight(node.right);
   node = rotateLeft(node);
   flipColors(node);
  }
  return node;
 }
 /**
  * Assuming node is red and both node.right and node.right.left
  * are black, make node.right or one of its children red
  * @param node
  * @return
  */
 private ColoredTreeNode moveRedRight(ColoredTreeNode node){
  flipColors(node);
  if(isRed(node.left.left)){
   node = rotateRight(node);
   flipColors(node);
  }
  return node;
 }
 private ColoredTreeNode balance(ColoredTreeNode node){
  if(isRed(node.right))
   node = rotateLeft(node);
  if(isRed(node.left) && isRed(node.left.left))
   node = rotateRight(node);
  if(isRed(node.left) && isRed(node.right))
   flipColors(node);
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return node;
 }
 /***************************************************
  * Other helper and utility methods
  ***************************************************/
 /**
  * check if a tree node is red,
  * if not, it is black
  * @param node
  * @return
  */
 private boolean isRed(ColoredTreeNode node){
  if(node == null)
   return false;
  return node.color == Color.red;
 }
 /**
  * return number of nodes in the tree
  * @return
  */
 public int size(){
  return size(root);
 }
 /**
  * return number of nodes in the subtree rooted at node
  * @param node
  * @return
  */
 private int size(ColoredTreeNode node){
  if(node == null)
   return 0;
  return node.numSubtree;
 }
 
 /**
  * find the node with the smallest key in subtree rooted at node
  * @param node
  * @return
  */
 public Comparable min(){
  if(isEmpty())
   return null;
  return min(root).key;
 }
 private ColoredTreeNode min(ColoredTreeNode node){
  if(node.left == null)
   return node;
  return min(node.left);
 }
 /**
  * find the node with the largest key in subtree rooted at node
  * @param node
  * @return
  */
 public Comparable max(){
  if(isEmpty())
   return null;
  return max(root).key;
 }
 private ColoredTreeNode max(ColoredTreeNode node){
  if(node.right == null)
   return node;
  return max(node.right);
 }
 
 /**
  * if it is an empty tree
  * @return
  */
 public boolean isEmpty(){
  return root == null;
 }
 
 /*******************************************************
  * check integrity of the tree
  *******************************************************/
 private boolean check(){
  if(!isBST()) 
   System.out.println("Not a BST!");
  if(!isSizeConsistent())
   System.out.println("Subtree counts not consistent!");
  if(!isBalanced())
   System.out.println("Not balanced tree!");
  return isBST() && isSizeConsistent() && isBalanced();
 }
 private boolean isSizeConsistent(){
  return isSizeConsistent(root);
 }
 private boolean isSizeConsistent(ColoredTreeNode root){
  if(root == null)
   return true;
  if(root.numSubtree != size(root.left) + size(root.right) + 1)
   return false;
  return isSizeConsistent(root.left) && isSizeConsistent(root.right);
 }
 private boolean isBST(){
  return isBST(root, null, null);
 }
 private boolean isBST(ColoredTreeNode node, Comparable min, Comparable max){
  if(node == null) return true;
  if(min != null && node.key.compareTo((T)min) <= 0) return false;
  if(max != null && node.key.compareTo((T)max) >= 0) return false;
  return isBST(node.left, min, node.key) && isBST(node.right, node.key, max);
 }
 /**
  * check if every root to leaf path have the same number
  * of black nodes
  * @return
  */
 public boolean isBalanced(){
  int blackNodes = 0;
  ColoredTreeNode node = root;
  while(node != null){
   if(!isRed(node))
    blackNodes++;
   node = node.left;
  }
  return isBalanced(root, blackNodes);
 }
 private boolean isBalanced(ColoredTreeNode node, int blackNodes){
  if(node == null) return blackNodes == 0;
  if(!isRed(node)) blackNodes--;
  return isBalanced(node.left, blackNodes) && isBalanced(node.right, blackNodes);
 }
 /**
  * output for check
  */
 public void printTree ()
 {
  if (root == null)
   return;
  Queue> queue = new LinkedList> ();
  queue.offer(root);
  //System.out.println(queue.peek().key);
  while (!queue.isEmpty())
  {
   int size = queue.size();
   for (int i = 0; i < size; i++)
   {
    ColoredTreeNode head = queue.poll();
    System.out.print(head.key + " ");
    if(head.left != null)
     queue.offer(head.left);
    if(head.right != null)
     queue.offer(head.right);
   }
   System.out.println("");

  }
 }
}
public class ColoredTreeNode {
 Comparable key;
 Object data; 
 Color color;
 ColoredTreeNode left;
 ColoredTreeNode right;
 int numSubtree; //subtree count
 public ColoredTreeNode(Comparable key, Object data, Color c, int N){
  this.key = key;
  this.data = data;
  left = null;
  right = null;
  color = c;
  numSubtree = N;
 }

}

Some notes about AVL tree
In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if any time they differ by more than one, rebalancing is done to restore the property. Look up, insertion and deletion all take O(logn) time. For lookup-intensive applications, AVL trees are faster than red-black trees because they are more rigidly balances.

Insertion
Every time a new node is inserted, it is necessary to check each of the node's ancestors for consistency with the rules of AVL. The balance factor is calculated as:

balanceFactor = height(left subtree) - height(right subtree)

Since with a single insertion the height of an AVL subtree cannot increase by more than one, the temporary balance factor of a node will be in the range from -2 to 2. For each node checked, if the balance factor remains in the range from -1 to 1, then only corrections of the balance factor, but no rotations are necessary. However, if the balance factor becomes less than -1 or greater than 1, the subtree rooted at this is unbalanced.

Deletion follows BST deletion rule, but needs to check balance factor each time.