Friday, August 7, 2015

Red Black Tree

What is Red-black-tree ?
   Red-black tree is a binary search tree data structure with extra color field which is either RED or BLACK. By constraining the node colors on any simple path from the root to leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.

Each node of the tree contains the attributes color, key, left, right, and parent.

Red-Black-Tree properties:
1. Every node is either RED or BLACK.
2. The root is BLACK.
3. Every leaf (NIL) is BLACK.
4. If a node is RED, then both its children are BLACK.
5. For each node, all simple paths from the node to descendant leaves contain the same number of
    black nodes.



Rotation
Why need rotation?
* The search tree operation TREE-INSERT and TREE-DELETE, when run on a red-black tree with n keys, take O(lgn) time. Because they modify the tree, the result may violate the red-black tree properties. To restore these properties, we must change the colors of some of the nodes in the tree and also change the pointer structure. So, we change the pointer structure through Rotation.

What is Left-rotation?
* When we do a left rotation on a node x, we assume that its right child y is not T.nil ; x may be the any node in the tree whose right child is not T.nil. The left rotation "pivots" around the link from x to y. It makes y the new rood of the subtree, with x as y's left child and y's left child as x's right child.

LEFT-ROTATE (T , x)
1       y = x.left
2       x.right  = y.left
3       if y.left != T.nil
4            y.left.p = x
5       y.p = x.p
6       if x.p == T.nil
7             T.root = y
8       elseif x == x.p.left
9             x.p.left = y
10     else  x.p.right = y
11     y.left = x
12     x.p = y



















0 comments:

Post a Comment