7. Optimal Binary Search Tree. 

#include<iostream>
using namespace std;

class obst
{
	int p[10],q[10];											// p -> probability of success	:	q -> probability of failure
	int arr[10];												// array of elements
	int weight[10][10],root[10][10],cost[10][10];				// resultant for obst i.e.,weight , root , cost
	int n;														// n -> no. of elements							
								   
public:

	void get()
	{
		cout<<"ENTER NUMBER OF ELEMENTS = ";
		cin>>n;
		cout<<": INPUT DATA ( ELEMENT , PROBABILITIES ) :"<<endl;
		for( int i = 1 ; i <= n ; i++ ) 
		{
			cout<<"ELEMENT "<<i<<" = ";							//element
			cin>>arr[i];
			cout<<"p ["<<i<<"] = ";								//success probability
			cin>>p[i];
			cout<<"q ["<<i-1<<"] = ";							//failure probability
			cin>>q[i-1];		
		}
		cout<<"q ["<<n<<"] = ";									// last failure probability
		cin>>q[n];
	}
	
	void constobst()
	{
		get();
		int k = 0,j = 0;												//a variable which stores the index of minimum cost
		
		//Initialize the values of weight, cost and root
		for( int i = 0 ; i <= n ; i++)
		{
			weight[i][i] = q[i];								// as according to formula ,i.e., ( w[i][j] = q[i] + p[k] + q[k] )
																// where, i < k < j ; so as no value of k when i = j therefore (w[i][i] = q[i] + 0)
			cost[i][i] = root[i][i] = 0;						// initial cost and root is 0
		}
		
		// m is the difference of j and i
		for( int m = 1 ; m <= n ; m++)
		{
			for(int i = 0 ; i < n ; i++)
			{	
				j = i + m;
				weight[i][j] = weight[i][j-1] + p[j] + q[j];				// weight of all elements
				k = kmin(i,j);									// call to kmin function which returns the index value of k by which we get minimum cost
				cost[i][j] = cost[i][k-1] + cost[k][j] + weight[i][j];	
				root[i][j] = k;
			}
		}
		cout<<"ROOT NODE       : "<<arr[root[0][n]];
		cout<<endl<<"LEFT NODE of "<<arr[root[0][n]]<<"  : ";
		obtree( 0 , root[0][n] -1 );
		cout<<endl<<"RIGHT NODE of "<<arr[root[0][n]]<<" : ";
		obtree(root[0][n] , n );
	}
	
	int kmin(int i , int j)
	{
		int min = 999 , z = 0;
		
		// if j - i = 1 then only possible value of k is j : as i < k <= j
		if( j - i == 1)
		{
			return j;
		}
		else
		{
			//  i < k <= j ; and we need to minimise the value of (cost[i][k-1] + cost[k][j])
			for(int k = i+1 ; k <= j ; k++)
			{
				if(min > (cost[i][k-1] + cost[k][j]))
				{
					z = k;
					min = (cost[i][k-1] + cost[k][j]);
				}
			}
		}
		return z;
	}	
	
	void obtree(int i , int j)
	{
		if(root[i][j] == 0)
		{
			cout<<"NULL"<<endl;
			return;
		}
		cout<<arr[root[i][j]]<<endl;
		cout<<endl<<"LEFT NODE OF "<<arr[root[i][j]]<<"  : ";
		obtree( i , root[i][j] -1 );
		cout<<endl<<"RIGHT NODE OF "<<arr[root[i][j]]<<" : ";
		obtree(root[i][j] , j );
	}
					
};

int main()
{
	obst o;
	o.constobst();
	return 0;
}

Comments

Post a Comment

Popular posts from this blog

2. Beginning with an empty binary search tree, Construct binary search tree by inserting the values in the order given. After constructing a binary tree -i.Insert new nodeii.Find number of nodes in longest path iii.Minimum data value found inthe tree iv.Change a tree so that the roles of the left and right pointers are swapped at every node v.Search a value

#include<iostream> #include<math.h> using namespace std; struct Bstnode { int data; Bstnode *left = NULL; Bstnode *right = NULL; }; class Btree { int n; int x; int flag; public: Bstnode * root; Btree() { root = NULL; } Bstnode *GetNewNode(int in_data) { Bstnode * ptr = new Bstnode(); ptr->data = in_data; ptr->left = NULL; ptr->right = NULL; return ptr; } Bstnode *insert( Bstnode *temp , int in_data) { if( temp == NULL ) { temp = GetNewNode(in_data); } else if( temp->data > in_data) { temp->left = insert(temp->left , in_data); } else { temp->right = insert( temp->right , in_data); } return temp; } void input() { cout<<"ENTER NUMBER OF ELEMENTS IN THE BST : "; cin>>n; for(int i = 0 ; i < n ; i++) { cout<<"NUMBER = "; cin>>x; root = insert(root , x); } } int search(Bstnode *temp ,int in_data) { if( te...
Read more

1. A book consists of chapters, chapters consist of sections and sections consist of subsections. Construct a tree and print the nodes. Find the time and space requirements of your method.

#include<iostream> using namespace std; struct node { string name; node *B[5]; }; class book { int c,s,sub; public: node *temp = new node; void Getnewnode() { for(int i = 0 ; i<5 ; i++) { temp->B[i] = new node; temp->B[i]->name = "empty"; for(int j=0; j<5; j++) { temp->B[i]->B[j] = new node; temp->B[i]->B[j]->name = "empty"; for(int k = 0 ; k<5; k ++) { temp->B[i]->B[j]->B[k] = new node; temp->B[i]->B[j]->B[k]->name = "empty"; } } } } void add_title() { cout<<": ENTER THE TITLE OF THE BOOK = "; cin>>temp->name; Getnewnode(); } void add_chapter() { string cname; int cnum; cout<<": ENTER NUMBER OF CHAPTERS IN THE BOOK = "; cin>>cnum; c = cnum; for(int i = 0 ; i < cnum ; i++) { cout<<endl<<"Chapter "<...
Read more

4. Write a function to get the number of vertices in an undirected graph and its edges. You may assume thatno edge is input twice. i.Use adjacency list representation of the graph and find runtime of the functionii.Use adjacency matrix representation of the graph and find runtime of the function

#include<iostream> using namespace std; class node { public: char data; node *start = NULL; node *next; void list(char ch) { node *ptr = new node; node *temp = new node; ptr->data = ch; if(start == NULL) { start = ptr; start->next = NULL; } else { temp = start; while(temp->next != NULL) { temp = temp->next; } ptr->next = NULL; temp->next = ptr; } } void displaylist() { node *temp = new node; if(start == NULL) { cout<<"LIST IS EMPTY"<<endl; } else { temp = start; while(temp != NULL) { cout<<temp->data<<"->"; temp = temp->next; } cout<<endl; } } }; class graph { int a[10][10]; char arr[5] = {'A','B','C','D','E'}; int vertices; node al[5]; public: graph() { cout<<"ENTER THE NUMBER OF VERTICES IN THE GRAPH \t::\t"; cin>>ve...
Read more