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



















Read more

Lexical Issues

Java programs are a collection of whitespace, identifiers, literals, comments, operators, separators, and keywords.

Whitespace
In Java, whitespace is a space, tab, or newline.
Java is a free-form language. This means that you do not need to follow any special indentation rules.
For instance, the Example program could have been written all on one line or in any other strange way you felt like typing it, as long as there was at least one whitespace character between each token that was not already delineated by an operator or separator.

Identifiers

Read more

Binary Search Tree

The search tree data structure supports many dynamic set operations:
               -  SEARCH
               - MINIMUM
               - MAXIMUM
               - PREDECESSOR
               - SUCCESSOR
               - INSERT
               - DELETE
and also can use search tree as "Dictionary" and "priority queue".

Binary Search tree
    We can represent such a tree by linked data structure in which each node is an object.
Each node contains attributes left, right, parent and element.



Figure: Binary search tree. 
       For any node x, the key in the left subtree of x are at most x.key, and the key in the right subtree of x are at least x.key. Different binary search trees can represent the same set of values. 
The worst-case running time for most search-tree operation is proportional to the height of the tree.
(a) A binary search tree on 9 nodes with height 3.
(b) A binary search tree on 9 nodes with height 6.

      There for, "Tree (a) is more efficient than Tree (b)".
    

Binary search tree property:
Let x be a node in a binary search tree. 
    - If y is a node in the left subtree of x, then y.key <= x.key.
    - If i is a node in the right subtree of x, then y.key >= x.key.

EX:

The binary-search-tree property allows us to print out all the key in a binary search tree in sorted order by a simple recursive algorithm, called an inorder tree walk.
To use the following procedure to print all the elements in a binary search tree T, we call INORDER-TREE-WALK(T.root).

TREE-WALK(x)
1    if x != NIL
2          TREE-WALK(x.left)
3          print x.key
4          TREE-WALK(x.right)

Here  Ө(n) time to walk an n nodes binary search tree.

Querying a binary search tree
Searching:
           Given a pointer to the root of the tree and a key k, TREE-SEARCH returns a pointer to a node with key k if one exists, otherwise, it returns NIL.

TREE-SEARCH (x , k)
1      if x == NIL or k == x.key
2            return x
3      if k < x.key
4           return TREE-SEARCH (x.left , k)
5      else return TREE-SEARCH (x.right , k)

The running time of TREE-SEARCH is O(h), where h is the height of the tree.
We can rewrite this procedure in an iterative fashion by "unrolling" the recursion into a while loop.

ITERATIVE-TREE-SEARCH (x , k)
1       while x != NIL and k != x.key
2              if k < x.key
3                     x = x.left
4              else x = x.right
5        return x

Minimum:
We can always find an element in a binary sear tree whose key is a minimum by following left child pointers from the root until we encounter a NIL.

TREE-MINIMUM (x)
1      while x.left != NIL
2             x = x.left
3       return x

Maximum:
We can always find an element in a binary sear tree whose key is a maximum by following right child pointers from the root until we encounter a NIL.

TREE-MAXIMUM (x)
1      while x.right != NIL
2             x = x.right
3       return x

the running time of both maximum and minimum is O(h).

Successor and predecessor:
Successor of a node x is the node with the smallest key greater than x.key.

TREE-SUCCESSOR (x)
1       if x.right != NIL
2              return  TREE-MAXIMUM (x.right)
3       y = x.p
4       while y != NIL and x == y.right 
5             x = y
6             y = y.p
7       return y

We break the code for TREE-SUCCESSOR into two cases.
       If the right subtree of node is nonempty, then the successor of x is just the leftmost node in x's right subtree, which is calling TREE-MINIMUM (x.right).
       On the other hand, if the right subtree of node x is empty and x has successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x.

Insertion and Deletion
Insertion:
To insert a new value v into a binary search tree T.
         take a node z for which,
          - z.key = v,
          - z.left = NIL,
          - z.right = NIL

TREE-INSERT(T,z)
1     y = NIL
2     x = T.root
3     while x != NIL
4            y = x
5            if z.key < x.key
6                      x = x.left
7            else    x = x.right
8     z.p = y
9     if y == NIL
10          T.root = y      // tree was empty
11   elseif  z.key < y.key
12           y.left = z
13   else  y.right = z




Read more