Binary Search Tree

Aim: - Construction of Binary Search Tree for a given list

Binary Tree is a dynamic data structure, which means, that its size is only limited by amount of free memory. Binary search tree(BST) is also such type of data structure, which meets the following requirements:

·         it is a binary tree;

·         each node contains a value;

·         a total order is defined on these values

·         left subtree of a node contains only values lesser, than the node's value;

·         right subtree of a node contains only values greater, than the node's value.

Binary search tree is used to construct map data structure. In practice, data can be often associated with some unique key. For instance, in the phone book such a key is a telephone number. Storing such a data in binary search tree allows to look up for the record by key faster, than if it was stored in unordered list. Also, BST can be utilized to construct set data structure, which allows storing an unordered collection of unique values and making operations with such collections.

Implementation:- BST can be implemented as a linked data structure in which each node is an object with three fields as represented below

 

Where the left-link and right-link are references to left and right sub-trees respectively otherwise NIL, signifies that there exists no corresponding child.

Example:- construction of BST for a List (6,3,2,9,1,5,4)

  


 

Summary:- Performance of a binary search tree depends on its height. In order to keep tree balanced and minimize its height, the idea of binary search trees was advanced in balanced search trees like AVL trees.

Java Program to Construct Binary Search Tree for a given list

import java.io.*;

class BinaryTree{

    private Node root;

    private static class Node  {

        Node left;

        Node right;

        int data;

           public Node(int cdata)  {

                left=null;

                right=null;

                data=cdata;

           }

    }

    public BinaryTree() throws Exception {

            root=null;

    }

    public void insert(int data)  {

        root=insert(root,data);

    }

    public Node insert(Node node,int data){

    if(node==null)

        node=new Node(data);

    else if(data<=node.data)

        node.left=insert(node.left, data);

    else

       node.right=insert(node.right, data);

    return(node);

    }

    public void Disp()  {

       if(root==null)

           System.out.println(" No Elements in the Tree ") ;

        else

        {

            inorder(root);

            System.out.println("\n Height of the tree ===> "+height(root));

        }

    }

    public int height(Node node){

       if(node==null)

           return(0);

        return max( height(node.left)+1, height(node.right)+1);

    }

    int max(int a,int b)

    {

        return(a>b?a:b);   

    }

    public void inorder(Node node){

        if(node!=null)  

        {

            inorder(node.left);

            System.out.print("   "+node.data);

            inorder(node.right);

       }

    }

    public boolean lookup(int data) {

        return(lookup(root,data));

    }

    public boolean lookup(Node node,int data){

        if(node==null)

            return false;

        if(data==node.data)

            return true;

        if(data<node.data)

            return(lookup(node.left,data));

        return(lookup(node.right,data));

    }

}

 

public class BST {

    public static void main(String agrs[]) throws Exception  {

        BinaryTree B= new BinaryTree();

        int n, item;

        DataInputStream in= new DataInputStream(System.in);

        System.out.print("Enter number of items to be inserted ");

        n=Integer.parseInt(in.readLine());

        System.out.println("Enter any "+n+" integers");

        while(n>0)

       {

            item=Integer.parseInt(in.readLine());

            B.insert(item);

            n--;

        }

        System.out.print("Elements in the tree are ");

        B.Disp();

        System.out.print(" Enter item to be searched ");

        item=Integer.parseInt(in.readLine());

        if(B.lookup(item))

           System.out.println("Sucessfull Search ");

        Else

           System.out.println("Unsucessfull Search ");

    }

}

 

OUTPUT:

Enter number of items to be inserted7

Enter any 7 integers

6  3  2  9  8  5  4

Elements in the tree are    2   3   4   5   6   8   9

 Height of the tree ===> 4

 

 Enter item to be searched 5

Sucessfull Search

 

Enter item to be searched 1

UnSucessfull Search

DIGITAL CLOCK APPLET PROGRAM

import java.util.*;

import java.awt.*;

import java.applet.*;

public class MyClock extends Applet implements Runnable

{

    Thread t;

    int hh,mm,ss;

    Font myf=new Font("Arial",Font.BOLD,50);

    public void init()

    {

            t=new Thread(this);

            t.start();

    }

    public void run()

    {

        for(;;)

        {

            Calendar tm=Calendar.getInstance();

            hh=tm.get(Calendar.HOUR);

            mm=tm.get(Calendar.MINUTE);

            ss=tm.get(Calendar.SECOND);

            try

            {

                t.sleep(1000);

                repaint();

            }

            catch(Exception e)

            {

            }

        }

    }

    public void paint(Graphics s)

    {

        String now="";

        s.setColor(Color.BLUE);

        s.setFont(myf);

        now=String.valueOf(hh)+":"+String.valueOf(mm)+":"+String.valueOf(ss);

        s.drawString(now,100,100);

    }

}

BELLMAN-FORD ALGORITHM

Bellman-Ford algorithm solves the single-source shortest-path problem in the general case in which edges of a given digraph can have negative weight as long as G contains no negative cycles.

GIVEN DIGRAPH

START BY SOURCE NODE(0)

FINALLY AFTER N-1 STEPS

FOR MORE INFO http://en.wordpress.com/tag/bellman-ford/

JAVA PROGRAM TO IMPLEMENT BELLMAN-FORD ALGORITHM

import java.io.*;

import java.util.*;

public class BellmanFord {

    LinkedList<Edge> edges;

    int d[];

    int n,e,s;

    final int INFINITY=999;

    private static class Edge  {

          int u,v,w;

          public Edge(int a, int b, int c)     {

                u=a;

                v=b;

                w=c;

           }

    }

    BellmanFord() throws IOException    {

        int item;

        edges=new LinkedList<Edge>();

        DataInputStream in= new DataInputStream(System.in);

        System.out.print("Enter number of vertices ");

        n=Integer.parseInt(in.readLine());

        System.out.println("Cost Matrix");

        for(int i=0;i<n;i++)

            for(int j=0;j<n;j++)   {

                item=Integer.parseInt(in.readLine());

                if(item!=0)

                    edges.add(new Edge(i,j,item));

            }

        e=edges.size();

        d=new int[n];

        System.out.print("Enter the source vertex ");

        s=Integer.parseInt(in.readLine());

   }

    void relax() {

        int i,j;

        for(i=0;i<n;++i)

                    d[i]=INFINITY;;

                d[s] = 0;

                for (i = 0; i < n - 1; ++i)

                     for (j = 0; j < e; ++j)

                         if (d[edges.get(j).u] + edges.get(j).w < d[edges.get(j).v])

                            d[edges.get(j).v] = d[edges.get(j).u] + edges.get(j).w;

    }

    boolean cycle() {

       int j;

       for (j = 0; j < e; ++j)

                         if (d[edges.get(j).u] + edges.get(j).w < d[edges.get(j).v])

                     return false;

       return true;

    }

    public static void main(String args[]) throws IOException   {

            BellmanFord r=new BellmanFord();

            r.relax();

            if(r.cycle())

             for(int i=0;i<r.n;i++)

               System.out.println(r.s+" ==> "+r.d[i]);

            else

                System.out.println(" There is a nagative edge cycle ");

    }

}

Heap sorting

Aim: - Implementation of Heap sort algorithm using Linked list as a data structure

The heap data structure is a special type of binary tree. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point. The heap data structure can also be used for an efficient implementation of a priority queue. There are two types of heap

1.      Max-heap: All nodes of heap satisfy the relation that the key value at each node is at least as large as the value at its children

2.      Min-heap: All nodes of heap satisfy the relation that the key value at each node is at least as small as the value at its children

Heap sorting algorithm first organizes the data to be sorted into a heap. It does this with the following steps for sorting with max-heap

1.  Remove the topmost item (the largest) and replace it with the rightmost leaf

2.  Re-establish the heap

3.  Repeat steps 1 and 2 until there are no more items left in the heap 

     The following example shows the steps after heap as been constructed how sorting will work and how it adjust the heap.

Summary:- The complexity of the heap sort is O(nlog(n)). Heap sort is better option for large data sets. Unlike mergesort, heapsort requires no extra space. On the other hand, heapsort is not stable. A sorting algorithm is stable, if it leaves the order of equal elements unchanged.

Java Program to implement Heap sort algorithm using Linked list as a data structure

import java.util.*;

import java.io.*;

class Heap {

    LinkedList list= new LinkedList();

    int n;

    Heap(int x)  {

        n=x;

    }

    public void insert() throws IOException {

        DataInputStream in=new DataInputStream(System.in);

        int item;

        System.out.print("Enter any "+n+" integer elements");

        for(int i=0;i<n;i++)

        {

            item=Integer.parseInt(in.readLine());

            list.addLast(item);

        }

    }

    public void disp() throws IOException   {

            System.out.println(" "+list);

    }

    public void construct(int num) throws IOException   {

        int i,j,k,v;

        boolean heap;

        list.addFirst(0);

        for(i=num/2;i>0;i--)

        {

        k=i;

        v=Integer.valueOf(list.get(k).toString());

        heap =false;

        while(!heap && 2*k<=num) {

            j=2*k;

            if(j<num)

                if(Integer.valueOf(list.get(j).toString())<Integer.valueOf(list.get(j+1).toString()))

                    j++;

            if(v>=Integer.valueOf(list.get(j).toString()))

                    heap=true;

            else

           {

                list.set(k,list.get(j));     

                   k=j;

            }

        }

        list.set(k,v);

        }

        list.removeFirst();

    }

    public void sort() throws IOException {

      construct(n);

      for(int i=1;i<=n;i++)  {

           Object temp=list.get(n-i);

           list.set(n-i, list.getFirst());

           list.set(0, temp);

           construct(n-i);

      }

   }

}

public class Sorting {

public static void main(String args[]) throws IOException {

    try{

        DataInputStream in=new DataInputStream(System.in);

        int count;

        System.out.println("Enter how many elements to be inserted");

        count=Integer.parseInt(in.readLine());

        Heap h1=new Heap(count);

        h1.insert();

        System.out.print(" Before sorting the list is ");

        h1.disp();

        h1.sort();

        System.out.print("\n After sorting the list is ");

        h1.disp();

       }

    catch(Exception e)   {

            System.out.println("Exception ="+e);

        }

    }

}

 

 

OUTPUT:

Enter how many elements to be inserted 8

Enter any 8 integer elements

8

7

6

5

4

4

3

2

 Before sorting the list is  [8, 7, 6, 5, 4, 4, 3, 2]

 After sorting the list is  [2, 3, 4, 4, 5, 6, 7, 8]

Merge Sort Java Program

Java Program to implement Merge sort algorithm using Linked list as a data structure

import java .io.*;

import java.util.*;

class Sorter {

    LinkedList <Integer> merge(LinkedList <Integer>list1, LinkedList <Integer>list2)   {

        LinkedList <Integer> list = new LinkedList <Integer>();

        while((!list1.isEmpty())&&!list2.isEmpty())   {

           if(list1.getFirst().compareTo(list2.getFirst())<0)

               list.add(list1.removeFirst());

           else    list.add(list2.removeFirst());

       }

       list.addAll(list1);       list.addAll(list2);

       return list;

   }

   LinkedList <Integer> mergesort(LinkedList <Integer>list)   {

                LinkedList <Integer> leftlist = new LinkedList <Integer>();

                LinkedList <Integer> rightlist = new LinkedList <Integer>();

                if(list.size()<=1)

                    return list;

                int middle=list.size()/2;

                split(list,leftlist,rightlist,middle);

                leftlist=mergesort(leftlist);

                rightlist=mergesort(rightlist);

                list=merge(leftlist,rightlist);

                return list;

  }

  void split(LinkedList<Integer> list, LinkedList<Integer> leftlist, LinkedList<Integer> rightlist, int  mid) 

  {

        for(int i=1;i<=mid;i++)

            leftlist.addLast(list.removeFirst());

        rightlist.addAll(list);

  }

}

 

public class Mergesort {

    public static void main(String args[]) throws IOException   {

                Sorter s=new Sorter();

                LinkedList <Integer> list=new LinkedList <Integer> ();

                DataInputStream in=new DataInputStream(System.in);

                System.out.print("Enter how many numbers");

                int n=Integer.parseInt(in.readLine());

                  System.out.print("Enter any "+n+" integer elements");

                for(int x=1;x<=n;x++)

                     list.add(Integer.parseInt(in.readLine()));

                System.out.println("Berfore Sorting "+list);

                System.out.println("After Sorting "+s.mergesort(list));

    }   

}

 

 OUTPUT:

Enter how many numbers 6

Enter any 6 integer elements

8  6 4 2 1 3

Berfore Sorting [8, 6, 4, 2, 1, 3]

After Sorting [1, 2, 3, 4, 6, 8]

Merge Sort

Aim: - Implementation of Merge sort algorithm using Linked list as a data structure

Mergesort is a divide and conquer algorithm. The sorting elements are stored in a collection. This collection is divided into two sub-collections and these are again sorted via merge sort. Once the two collections are sorted then the result is combined.

Conceptually, a merge sort works as follows

1.      If the list is of length 0 or 1, then it is already sorted. Otherwise;

2.      Divide the unsorted list into two sub-lists of about half the size.

3.      Sort each sub-list recursively by re-applying merge sort.

4.      Merge the two sub-lists back into one sorted list.

Example:- List (8,3,2,9,7,1,5,4)

 

 

Summary:- Merge sort is relatively a simple to code, fast, stable sorting routine with guaranteed O(n log n) efficiency. When sorting arrays, merge sort requires additional scratch space proportional to the size of the input array