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

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

Wednesday, February 25, 2015

Blocks of Code

Java allows two or more statements to be grouped into blocks of code, also called code blocks. This is done by enclosing the statements between opening and closing curly braces. Once a block of code has been created, it becomes a logical unit that can be used any place that a single statement can. For example, a block can be a target for Java’s if and for statements.
Consider this if statement:

if(x < y) { // begin a block
x = y;
y = 0;
} // end of block

Here, if x is less than y, then both statements inside the block will be executed.

Let’s look at another example. The following program uses a block of code as the target
of a for loop.

/*
Demonstrate a block of code.
Call this file "BlockTest.java"
*/
class BlockTest {
      public static void main(String args[]) {
               int x, y;
               y = 20;
// the target of this loop is a block

               for(x = 0; x<10; x++) {
                        System.out.println("This is x: " + x);
                        System.out.println("This is y: " + y);
                        y = y - 2;
                }
        }
}

The output generated by this program is shown here:
This is x: 0
This is y: 20
This is x: 1
This is y: 18
This is x: 2
This is y: 16
This is x: 3
This is y: 14
This is x: 4
This is y: 12
This is x: 5
This is y: 10
This is x: 6
This is y: 8
This is x: 7
This is y: 6
This is x: 8
This is y: 4
This is x: 9

This is y: 2

In this case, the target of the for loop is a block of code and not just a single statement.

Read more

Two Control Statement

1. The if Statement
The java if statement works much like the IF statement in any other language.  Its simplest form is;

if(condition) statement;

Here, condition is a Boolean expression. If condition is true, then the statement is executed. If condition is false, then the statement is bypassed.
 Here is an example:

if(num < 100) System.out.println("num is less than 100");

In this case, if num contains a value that is less than 100, the conditional expression is true, and println( ) will execute. If num contains a value greater than or equal to 100, then the println( ) method is bypassed.

Here are a few conditional expression.
Operator
Meaning
< 
Less than
> 
Greater than
==
Equal to

 Notice that the test for equality is the double equal sign.

/*
Demonstrate the if.
Call this file "IfSample.java".
*/
class IfSample {
        public static void main(String args[]) {
                int x, y;
                x = 10;
                y = 20;

                 if(x < y) System.out.println("x is less than y");
                 x = x * 2;

                 if(x == y) System.out.println("x now equal to y");
                 x = x * 2;
  
                 if(x > y) System.out.println("x now greater than y");
                 // this won't display anything

                  if(x == y) System.out.println("you won't see this");
        }
}
  
The output generated by this program is shown here:
x is less than y
x now equal to y
x now greater than y

Notice one other thing in this program. The line
int x, y;
declares two variables, x and y, by use of a comma-separated list.

2. The for Loop
Loop statements are an important part of nearly any programming language. Java is no exception.
The simplest form of the for loop is;

for(initialization; condition; iteration) statement;

The initialization portion of the loop sets a loop control variable to an initial value. The condition is a Boolean expression that tests the loop control variable. If the outcome of that test is true, the for loop continues to iterate. If it is false, the loop terminates. The iteration expression determines how the loop control variable is changed each time the loop iterates.

Simple program of for loop;
/*
Demonstrate the for loop.
Call this file "ForTest.java".
*/
class ForTest {
        public static void main(String args[]) {
               int x;
               for(x = 0; x<10; x = x+1)
                       System.out.println("This is x: " + x);
        }
}

This program generates the following output:
This is x: 0
This is x: 1
This is x: 2
This is x: 3
This is x: 4
This is x: 5
This is x: 6
This is x: 7
This is x: 8
This is x: 9














Read more

A Second Short Program

/*
Here is another short example.
Call this file "Example2.java".
*/
class Example2 {
       public static void main(String args []) {
              int num;         // this declares a variable called num
              num = 100;      // this assigns num the value 100
              System.out.println("This is num: " + num);
              num = num * 2;
              System.out.print("The value of num * 2 is ");
              System.out.println(num);
       }
}

When you run this program you will see like this output;

This is num: 100
The value of num * 2 is 200

Let's take a close look at why this output is generated.
The first new line in this program ,
  int num;         // this declares a variable called num
This line declares an integer variable called num. Java requires that variables be declared before they are used. The declaration form is,

type var-name;

Here, type specifies the type of variable being declared, and var-name is the name of the variable.

The next line is;

  num = 100;      // this assigns num the value 100

Assigns to num the value 100. In Java, the assignment operator is a single equal sign.
The next line in the program,

 System.out.println("This is num: " + num);

In this statement, the plus sign causes the value of num to be appended to the string that
precedes it, and then the resulting string is output. (Actually, num is first converted from an integer into its string equivalent and then concatenated with the string that precedes it).
Using the + operator, you can join together as many items as you want within a single
println( ) statement.

The next line of code assigns num the value of num times 2.

 num = num * 2;

Java uses the * operator to indicate multiplication.
Here are the next two lines in this program;

 System.out.print("The value of num * 2 is ");
 System.out.println(num);

The print( ) method is just like println( ), except that it does not output a newline character after each call. So, the built-in method print( ) is used to display the string "The value of num*2 is". This string is not followed by a newline. This means that when the next output is generated, it will start on the same line.











Read more

Tuesday, February 24, 2015

A very first simple program in Java

Let's look at the simple  actual java program.

/*
This is a simple Java program.
Call this file "Example.java".
*/
class Example {
     // Your program begins with a call to main( ).
      public static void main(String args[]) {
              System.out.println("This is a simple Java program.");
      }
}

The first thing that you must learn about Java is that the name you give to a source file is very important. For this example,
the name of the source file should be Example.java.

Let’s closely examine each part of the program.
The program begins with the following lines:

/*
This is a simple Java program.
Call this file "Example.java".
*/

This is a comment. The contents of a comment are ignored by the compiler. Instead, a comment describes or explains the operation of the program to anyone who is reading its source code. in real applications, comments generally explain how some part of the program works or what a specific feature does. Java have three type of comments. This comment is "multiline comment".

The next line of the code in the program,

class Example {

This line uses the keyword class to declare that a new class is being defined. Example
is an identifier that is the name of the class. The entire class definition, including all of its members, will be between the opening curly brace ({) and the closing curly brace (}).

The next line in the program is the single-line comment,

 // Your program begins with a call to main( ).

This is the second type of comment in Java. A single-line comment begins with a //
and ends at the end of the line.

The next line of code is,

 public static void main(String args[]) {

This line begins the main( ) method. All Java applications begin execution by calling main( ).
Let’s take a brief look at each part now.

The public keyword is an access modifier, which allows the programmer to control the
visibility of class members. When a class member is preceded by public, then that member may be accessed by code outside the class in which it is declared.

The keyword static allows main( ) to be called without having to instantiate a particular instance of the class. This is necessary since main( ) is called by the Java Virtual Machine before any objects are made.

The keyword void simply tells the compiler that main( ) does not return a value.

*** Very important think is Java is case-sensitive. Thus, Main is different from main

Any information that you need to pass to a method is received by variables specified within the set of parentheses that follow the name of the method. These variables are called parameters.
If there are no parameters required for a given method, you still need to include the empty parentheses.

In main( ), there is only one parameter, String args[ ] declares a parameter named args, which is an array of instances of the class String. args receives any command-line arguments present when the program is executed.

The last character on the line is the {. This signals the start of main( )’s body. All of the code that comprises a method will occur between the method’s opening curly brace and its closing curly brace.

The next line of code is,

System.out.println("This is a simple Java program.");

This line outputs the string "This is a simple Java program." followed by a new line on the screen. Output is actually accomplished by the built-in println( ) method. In this case, println( ) displays the string which is passed to it.
The line begins with System.out. While too complicated to explain in detail at this time, briefly, System is a predefined class that provides access to the system, and out is the output stream that is connected to the console.

Finally how can we compile and run this program?
To compile the Example program, execute the compiler, javac, specifying the name of the source file on the command line,

C:\>javac Example.java

The javac compiler creates a file called Example.class that contains the bytecode version of the program.the Java bytecode is the intermediate representation of your program that contains instructions the Java Virtual Machine will execute. Thus, the output of javac is not code that can be directly executed.
To actually run the program, you must use the Java application launcher called java. To do so, pass the class name Example as a command-line argument, as shown here:

C:\>java Example

When the program is run, the following output is displayed:
This is a simple Java program.






Read more