Showing posts with label Advance Algorithm. Show all posts
Showing posts with label Advance Algorithm. Show all posts

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

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

Tuesday, May 12, 2015

Selection Sort


It is a simplest algorithm.
First look for the minimum in the array and then swap that element with the 0th position. Then find the second minimum element and swap with the index 1 element and so on.


SelectionSort ( A , n ) 
{
      for i <--- 0 to n-2
       {
            min <-- i
            for j <--- i+1 to n-1
             {
                   if ( A[i] <  A[min] )
                           min <--- j
                   
                    temp <-- A[i]
                    A[i] <--- A[min]
                    A[min] <-- temp
              }
        }
}
Read more

Bubble Sort Algorithm



In this algorithm, we scan the array from left to right multiple times. We will call each scan one pass on the array like we will first look at the 0th element then look at the index 1 and so on.

BubbleSort(A,n) // "A" is the array name and "n" is the length of array
{
       for k <---- 1 to n-1
       {
             flag <------ 0
             for i <---- 0 to n-k-1
              {
                     if ( A[i] > A[i+1] )
                      {
                            swap ( A[i] , A[i+1] )
                            flag <----- 1
                       }
               }
               if ( flag == 0 ) break
        }
}
Read more