optimal binary search tree program in java

import java.io.*;
import java.util.*;
class Optimal
{
public int p[]; // Probabilities with which we search for an element
public int q[]; // Probabilities that an element is not found
public int a[]; // Elements from which OBST is to be built
public int w[][]; // Weight w[i][j] of a tree having root r[i][j]
public int c[][]; // Cost c[i][j] of a tree having root r[i][j]
public int r[][]; // Represents Root
public int n; // Number of nodes
int front,rear,queue[];
public Optimal(int SIZE)
{
p=new int[SIZE];
q= new int[SIZE];
a=new int[SIZE];
w=new int[SIZE][SIZE];
c=new int[SIZE][SIZE];
r=new int[SIZE][SIZE];
queue=new int[SIZE];
front=rear=-1;
}
public int Min_Value(int i, int j)
{
int m,k=0;
int minimum = 32000;
for (m=r[i][j-1] ; m<=r[i+1][j] ; m++)
{
if ((c[i][m-1]+c[m][j]) < minimum)
{
minimum = c[i][m-1] + c[m][j];
k = m;
}
}
return k;
}
public void OBST()
{
int i, j, k, l, m;
for (i=0 ; i {
// Initialize
w[i][i] = q[i];
r[i][i] = c[i][i] = 0;
// Optimal trees with one node
w[i][i+1] = q[i] + q[i+1] + p[i+1];
r[i][i+1] = i+1;
c[i][i+1] = q[i] + q[i+1] + p[i+1];
}
w[n][n] = q[n];
r[n][n] = c[n][n] = 0;
// Find optimal trees with m nodes
for (m=2 ; m<=n ; m++)
{
for (i=0 ; i<=n-m ; i++)
{
j = i+m;
w[i][j] = w[i][j-1] + p[j] + q[j];
k = Min_Value(i,j);
c[i][j] = w[i][j] + c[i][k-1] + c[k][j];
r[i][j] = k;
}
}
}
public void build_tree()
{
int i, j, k;
System.out.print("The Optimal Binary Search Tree For The Given Nodes Is ....\n");
System.out.print("\n The Root of this OBST is :: "+r[0][n]);
System.out.print("\n The Cost Of this OBST is :: "+c[0][n]);
System.out.print("\n\n\tNODE\tLEFT CHILD\tRIGHT CHILD");
System.out.println("\n -------------------------------------------------------");
queue[++rear] = 0;
queue[++rear] = n;
while(front != rear)
{
i = queue[++front];
j = queue[++front];
k = r[i][j];
System.out.print("\n "+k);
if (r[i][k-1] != 0)
{
System.out.print(" "+r[i][k-1]);
queue[++rear] = i;
queue[++rear] = k-1;
}
else
System.out.print(" -");
if(r[k][j] != 0)
{
System.out.print(" "+r[k][j]);
queue[++rear] = k;
queue[++rear] = j;
}
else
System.out.print(" -");
}
System.out.println("\n");
}
}
/* This is the main function */
class OBSTDemo
{
public static void main (String args[] )throws IOException
{
Optimal obj=new Optimal(10);
int i;
System.out.print("\n Optimal Binary Search Tree \n");
System.out.print("\n Enter the number of nodes ");
obj.n=getInt();
System.out.print("\n Enter the data as ....\n");
for (i=1;i<=obj.n;i++)
{
System.out.print("\n a["+i+"]");
obj.a[i]=getInt();
}
for (i=1 ; i<=obj.n ; i++)
{
System.out.println("p["+i+"]");
obj.p[i]=getInt();
}
for (i=0 ; i<=obj.n ; i++)
{
System.out.print("q["+i+"]");
obj.q[i]=getInt();
}
obj.OBST();
obj.build_tree();
}
public static String getString() throws IOException
{
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader b = new BufferedReader(input);
String str = b.readLine();//reading the string from console
return str;
}
public static char getChar() throws IOException
{
String str = getString();
return str.charAt(0);//reading first char of console string
}
public static int getInt() throws IOException
{
String str = getString();
return Integer.parseInt(str);//converting console string to numeric value
}
}

/*optimal binary search tree program in java Output

Optimal Binary Search Tree

Enter the number of nodes 4

Enter the data as ....

a[1]1

a[2]2

a[3]3

a[4]4

p[1]
3
p[2]
3
p[3]
1
p[4]
1

q[0] 2
q[1] 3
q[2] 1
q[3] 1
q[4] 1
The Optimal Binary Search Tree For The Given Nodes Is ....

The Root of this OBST is :: 2
The Cost Of this OBST is :: 32

NODE LEFT CHILD RIGHT CHILD
-------------------------------------------------------

2 1 3
1 - -
3 - 4
4 - - */

Facing difficulties in understanding the program ?

Ask Your Queries in Comment Box

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *