Logo
×

Optimal binary search tree using dynamic programming

Implementation

// We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
#include <bits/stdc++.h>
using namespace std;


//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
int sum(int frequency[], int i, int j);


// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
int optCost(int frequency[], int i, int j)
{
	if (j < i) 
		return 0;
	if (j == i) 
		return frequency[i];
	
	//In this step, we have to get the sum of the i and i+1…… frequency j. 
	int freqsum = sum(frequency, i, j);
	
	// regularizing the minimal value or data.
	int min = INT_MAX;
	
	// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for (int r = i; r <= j; ++r)
	{
		int cost = optCost(frequency, i, r - 1) +
				optCost(frequency, r + 1, j);
		if (cost < min)
			min = cost;
	}
	
	// at this step, we have to return the minimal value.
	return min + freqsum;
}


// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of the binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
int Opt_SearchTree(int kys[],
					int frequency[], int n)
{
	// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
	return optCost(frequency, 0, n - 1);
}


// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
int sum(int frequency[], int i, int j)
{
	int s = 0;
	for (int k = i; k <= j; k++)
	s += frequency[k];
	return s;
}


// writing the main code.
int main()
{
	int kys[] = {10, 12, 20};
	int frequency[] = {34, 8, 50};
	int n = sizeof(kys) / sizeof(kys[0]);
	cout << "Cost of Optimal BST is "
		<< Opt_SearchTree(kys, frequency, n);
	return 0;
}

Output:

Optimal binary search tree using dynamic programming

Example 2)

// We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
#include <stdio.h>
#include <limits.h>
//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
int sum(int frequency[], int i, int j);
// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
int optCost(int frequency[], int i, int j)
{
if (j < i)	
	return 0;
if (j == i)	
	return frequency[i];
//In this step, we have to get the sum of the i and i+1…… frequency j. 
int freqsum = sum(frequency, i, j);
// regularizing the minimal value or data.
int min = INT_MAX;
	// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
for (int r = i; r <= j; ++r)
{
	int cost = optCost(frequency, i, r-1) +
				optCost(frequency, r+1, j);
	if (cost < min)
		min = cost;
}
	// at this step, we have to return the minimal value.
return min + freqsum;
}
// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
int Opt_SearchTree(int kys[], int frequency[], int n)
{
	// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
	return optCost(frequency, 0, n-1);
}
// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
int sum(int frequency[], int i, int j)
{
	int s = 0;
	for (int k = i; k <=j; k++)
	s += frequency[k];
	return s;
}
// writing the main code.
int main()
{
	int kys[] = {10, 12, 20};
	int frequency[] = {34, 8, 50};
	int n = sizeof(kys)/sizeof(kys[0]);
	printf("Cost of Optimal BST is %d ",
			Opt_SearchTree(kys, frequency, n));
	return 0;
}

Output:

Optimal binary search tree using dynamic programming

Example 3)

// We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
public class TFG
{
	//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
	static int optCost(int frequency[], int i, int j)
	{
	if (j < i)	 
		return 0;
	if (j == i)
		return frequency[i];
	
// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
//In this step, we have to get the sum of the i and i+1…… frequency j. 
	int freqsum = sum(frequency, i, j);
// regularizing the minimal value or data.
	int min = Integer.MAX_VALUE;
// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for (int r = i; r <= j; ++r)
	{
		int cost = optCost(frequency, i, r-1) +
						optCost(frequency, r+1, j);
		if (cost < min)
			min = cost;
	}
	// at this step, we have to return the minimal value.
	return min + freqsum;
	}
// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
	static int Opt_SearchTree(int kys[], int frequency[], int n)
	{
			// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
		return optCost(frequency, 0, n-1);
	}
	// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
	static int sum(int frequency[], int i, int j)
	{
		int s = 0;
		for (int k = i; k <=j; k++)
		s += frequency[k];
		return s;
	}
// writing the main code.	
	public static void main(String[] args) {
		int kys[] = {10, 12, 20};
		int frequency[] = {34, 8, 50};
		int n = kys.length;
		System.out.println("Cost of Optimal BST is " +
						Opt_SearchTree(kys, frequency, n));
	}
}

Output:

Optimal binary search tree using dynamic programming

Example 4)

# We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
def optCost(frequency, i, j):
		if j < i:	
		return 0
	if j == i:	 
		return frequency[i]
//In this step, we have to get the sum of the i and i+1…… frequency j. 
	freqsum = Sum(frequency, i, j)
	
	# regularizing the minimal value or data.
	Min = 999999999999
	
	# We have to start initializing all the data or records one at a time and consider all the elements present in there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for r in range(i, j + 1):
		cost = (optCost(frequency, i, r - 1) +
				optCost(frequency, r + 1, j))
		if cost < Min:
			Min = cost
	
	# at this step, we have to return the minimal value.


	return Min + freqsum


# Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
def Opt_SearchTree(kys, frequency, n):
	
	# In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
	return optCost(frequency, 0, n - 1)


# We are creating a utility function to help us get the sum of the frequency of the elements present in that specific array. 
def Sum(frequency, i, j):
	s = 0
	for k in range(i, j + 1):
		s += frequency[k]
	return s


# writing the main code.
if __name__ == '__main__':
	kys = [10, 12, 20]
	frequency = [34, 8, 50]
	n = len(kys)
	print("Cost of Optimal BST is",
		Opt_SearchTree(kys, frequency, n))

Output:

Optimal binary search tree using dynamic programming

Example 5)

// We are creating a presentation where we will present a recursive method of the optimal binary search tree problem. 
using System;
class TFG
{
//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
	static int optCost(int []frequency, int i, int j)
	{
		
	if (j < i)	
		return 0;
	if (j == i)	
		return frequency[i];
// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
//In this step, we have to get the sum of the i and i+1…… frequency j. 
	int freqsum = sum(frequency, i, j);
// regularizing the minimal value or data.	
	int min = int.MaxValue;
	// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for (int r = i; r <= j; ++r)
	{
		int cost = optCost(frequency, i, r-1) +
						optCost(frequency, r+1, j);
		if (cost < min)
			min = cost;
	}
	// at this step, we have to return the minimal value.
	return min + fsum;
	}
// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
	static int Opt_SearchTree(int []kys, int []frequency, int n)
	{
	// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
		return optCost(frequency, 0, n-1);
	}
// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
	static int sum(int []frequency, int i, int j)
	{
		int s = 0;
		for (int k = i; k <=j; k++)
		s += frequency[k];
		return s;
	}
// writing the main code.	
	public static void Main()
	{
		int []kys = {10, 12, 20};
		int []frequency = {34, 8, 50};
		int n = kys.Length;
		Console.Write("Cost of Optimal BST is " +
						Opt_SearchTree(kys, frequency, n));
	}
}

Output:

Optimal binary search tree using dynamic programming

Example 6)

<script>
// We are creating a Javascript presentation where we will present a recursive method of the optimal binary search tree problem. 
function optCost(frequency, i, j)
{
	if (j < i) 
		return 0;
	if (j == i) 
		return frequency[i];
//creating a utility function that will help us extract the sum of the array elements containing the frequency i and j.  
// building a new function that will ultimately help us get out the cost of the optimal binary search tree. 
//In this step, we have to get the sum of the i and i+1…… frequency j. 
	var freqsum = sum(frequency, i, j);
// regularizing the minimal value or data.	
	var min = Number. MAX_SAFE_INTEGER;
	// We have to start initializing all the data or records one at a time and consider all the elements there as root. Then after this is done, we have to find the cost of the binary search tree, compare that cost with the minimal record, and make the changes consecutively if required.
	for (var r = i; r <= j; ++r)
	{
		var cost = optCost(frequency, i, r - 1) +
				optCost(frequency, r + 1, j);
		if (cost < min)
			min = cost;
	}
	// at this step, we have to return the minimal value.
	return min + fsum;
}
// Now, we are simply creating the main function that will help us calculate and adjust the minimal cost of a binary search tree. It will help us optimize the tree's optimal cost and locate it easily.
function Opt_SearchTree(kys, frequency, n)
{
	// In this step, it is presumed that the array keys should be arranged in increasing order. And if the keys present there are not set accordingly, we have to add some code and make the required changes. After this, we can also change the frequency of the same. 
	return optCost(frequency, 0, n - 1);
}
// We are creating a utility function that will help us to get the sum of the frequency of the elements present in that specific array. 
function sum(frequency, i, j)
{
	var s = 0;
	for (var k = i; k <= j; k++)
	s += frequency[k];
	return s;
}




// writing the main code.	
var kys = [10, 12, 20];
var frequency = [34, 8, 50];
var n = kys.length;
document.write("Cost of Optimal BST is " +
	Opt_SearchTree(kys, frequency, n));
	</script>

Output:

Optimal binary search tree using dynamic programming

Related Topics

Horizontal and Vertical Scaling

Being a software engineer, you would have designed a website or application and deployed it on any server. Imagine that the developed application starts getting popular, and many users engage...

6 minutes read.

Intersection Point in Y Shaped Linked Lists in Java

Intersection Point in Y Shaped Linked Lists in Java In this article, we are going to see how to find the intersection point in a Y-shaped linked list. Method 1: We need to...

4 minutes read.

Hashing

Hashing: Hashing is a process in which a large amount of data is mapped to a small table with the help of hashing function. It is a searching technique. Hash table We...

4 minutes read.

Serialize and Deserialize Binary Trees

In order to save a tree in a file that can later be restored, serialisation is used. The tree's structure must be preserved. Deserialization involves reading a tree from a...

4 minutes read.

Priority Queue in Data Structure

Priority Queue A priority queue is a special kind of queue, in priority queue we give some priority to an element and according to this priority an element can be served...

3 minutes read.

Inorder Successor in Binary Trees

The next node in the Inorder traversal of a binary tree is known as Inorder successor of that particular node. In a Binary Search Tree, the definition of Inorder successor can...

9 minutes read.

Queue Data Structure

Queue in DS: The queue is a non-primitive and linear data structure. It works on the principle of FIFO (First In First Out). That is, the element that is added...

4 minutes read.

What is a Height-Balanced Tree in Data Structure

A height-balanced tree is a type of binary tree. If the absolute difference between the heights of the left and right subtree is less than or equal to 1, then...

6 minutes read.

Merge Conflicts and ways to handle them

Merge Conflicts Whenever dealing with the Git merge operations, conflicts will be the frequently occurred. When more than two developers work on the same file on different systems using Git, they...

4 minutes read.

Recursion - Factorial and Fibonacci

In this article, we will learn how to find the factorial of a number and the Fibonacci series up to n using the recursion method. What is recursion? Defining anything in terms...

7 minutes read.

What is an AVL Tree in Data Structure?

AVL tree stands for (Adelson, Velskii, & Landis Tree) Data structure Data management is called database management. A data model is a system used to store, manage, and optimize computer resources. Data...

4 minutes read.

Trie data structure

Trie data structure The term “trie” comes from the word “retrieval” which means getting information. The trie data structure is a sorted extension of tree-based data structure. The trie data structure...

5 minutes read.

Stack Using Linked List

In the linked list implementation of the stack, we use a linked list as the primitive data structure to create the stack. It is called the dynamic implementation of the...

6 minutes read.

Linear vs Binary Search: Data Structure

Difference Between Linear and Binary Search What is Linear Search? A linear search also referred as a sequential search. It is a way to find an element within a list and it...

3 minutes read.

Boruvkas algorithm

This algorithm is used for finding minimum spanning tree from a weighted graph. Like prim’s and kruskal’s algorithm it is also a greedy algorithm. Note:What is the minimum spanning tree?We know...

4 minutes read.

Red Black Tree vs AVL Tree: Data Structure

Difference Between Red Black Tree vs AVL Tree Red Black Tree: A red-black tree is referred as self-balancing binary search tree. In red-black, each node stores an extra bit that determines...

4 minutes read.

Lowest common ancestor in a binary search tree

Suppose you have given two values of nodes in a binary search tree. You have to find out the lowest common ancestor between the nodes. Let’s take an example tree- For the...

4 minutes read.

Finding the Maximum Element in a Binary Tree

Implementation // Creating a C++ program to excavate the minimum and maximum in a given binary tree. #include <bits/stdc++.h> #include <iostream> using namespace std; // creating a new tree node. class __nod { public: int record; __nod *Lft, *Rt; /*...

4 minutes read.

Adding one to the number represented an array of digits

You have given one array, which consists of values which represent the different digits of a number. You have to add 1 to this number and store the result in...

3 minutes read.

Collision Resolution Techniques

Collision Resolution Techniques Collision in hashing In this, the hash function is used to compute the index of the array.The hash value is used to store the key in the hash table,...

2 minutes read.