Insertion and Deletion in Red-black trees

Red-black trees, aren’t they amazing? Here is how they’re commonly defined:

It’s a binary search tree, with the following additional properties:

  1. A node is either red or black.
  2. The root is 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.)
  3. All leaves (NIL) are black. (All leaves are same color as the root.)
  4. Both children of every red node are black.
  5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

Red-black trees have worst case time complexity of O(logN) for searching. (N is the number of nodes in the red-black tree). Note that binary search trees have worst case time complexity of O(N) for searching.

There are gazillion resources on internet that will tell you the definition of a red-back and what is the need for them but very few of them explain insertion and deletion operations in easy-to-follow language.
The objective of this post is to help you quickly understand how the insertion and deletion is performed on a red-black tree.

Insertion in a Red-black tree:

Mark the node as red (because red is the best we can do to avoid breaking lesser Red-Black tree laws) and insert it like we are inserting in a BST. The new red node may still break the “no continuous red nodes law”. Let new node be denoted by N, its parent by P, its grandparent by G and its uncle by U.Then we fix it via:

  1. If N is at Root, color it black and terminate.
  2. If P is Black, terminate.
  3. Check U’s color, if red, then mark P and U as black and G as red, go to G (i.e N=G) and repeat all the steps.
  4. If P is at left
    1. If N is a right child, left rotate about P.
    2. Mark P as black and G as red, then right rotate about G and terminate.
  5. If P is at right
    1. If N is a left child, right rotate about P.
    2. Mark P as black and G as red, then left rotate about G and terminate.

Deletion in a Red-black tree:

Assume that you are deleting from a binary search tree and delete the node using the conventional steps.(i.e replace the value in node to deleted by its inorder predecessor or successor), the actual problem is to delete that inorder predecessor/successor node so that the red-black properties of the tree aren’t violated). Then we go ahead and fix the tree such that it satisfies all properties of a red black tree. Let M be the effective node(inorder successor/predecessor) that need to be deleted, and Let N denotes its child node , N’s parent is denoted by P, N’s grandparent by G and its sibling by S.

  1. If N is the root node, replace it by NULL node and terminate.
  2. If M is red, replace it by N and terminate.
  3. If M is black and N is red, replace it by N, color N black and terminate.

     <–If M and N both are black follow the steps–>

  1. Replace M by N. Now forget M ever existed.
  2. If N is a left child:
    1. If S is red, reverse the color of S and P and left rotate about P. Reset S. (It’s guaranteed that new S is Black)
    2. If P, S and S’s children are all black, repaint S to red and set N=P, repeat all steps.
    3. If P is red, but S and S’s children are black, then reverse color of P and S.
    4. If only the left child of S is red, then right rotate about S and reverse color of S and its parent.
    5. If only the right child of S is red, left rotate about P, exchange the color of P and S and color S’s right child to black
  3. If N is a right child
    1. If S is red, reverse the color of S and P and right rotate about P. Reset S. (It’s guaranteed that new S is Black)
    2. If P, S and S’s children are all black, repaint S to red and set N=P, repeat all steps.
    3. If P is red, but S and S’s children are black, then reverse color of P and S.
    4. If only the right child of S is red, then left rotate about S and reverse color of S and its parent.
    5. If only the left child of S is red, right rotate about P, exchange the color of P and S and color S’s left child to black

Demo:
http://www.ece.uc.edu/~franco/C321/html/RedBlack/

References:
http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
http://stackoverflow.com/questions/9469858/how-to-easily-remember-red-black-tree-insert-and-delete

About these ads

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