com.mhhe.clrs2e
Class OptimalBinarySearchTree

java.lang.Object
  |
  +--com.mhhe.clrs2e.OptimalBinarySearchTree

public class OptimalBinarySearchTree

extends java.lang.Object

Implements the dynamic-programming algorithm to determine the structure of an optimal binary search tree, as described in Section 15.5 of Introduction to Algorithms, Second edition. No method to print an optimal solution is provided, since that would give away the solution to Exercise 15.5-1.

Field Summary

private int	n How many keys are in the binary search tree.
private int[][]	root The root of an optimal binary search tree for subproblem.

Constructor Summary

OptimalBinarySearchTree(double[] p, double[] q)
Determines the structure of an optimal binary search tree, given an array of probabilities of successful searches for keys and an array of probabilities of unsuccessful searches.

Method Summary

int	getNumberOfKeys() Returns the value of n.
int[][]	getRootTable() Returns the table of roots of subtrees.
void	optimalBST(double[] p, double[] q, int n) Determines the structure of an optimal binary search tree, given an array of probabilities of successful searches for keys and an array of probabilities of unsuccessful searches.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

n

private int n

How many keys are in the binary search tree.

root

private int[][] root

The root of an optimal binary search tree for subproblem. root[i][j] is the root of g an optimal binary search tree containing the keys k_i, ..., k_j, for 1 ≤ i ≤ j ≤ n. Other positions of root are unused.

Constructor Detail

OptimalBinarySearchTree

public OptimalBinarySearchTree(double[] p,
                               double[] q)

Determines the structure of an optimal binary search tree, given an array of probabilities of successful searches for keys and an array of probabilities of unsuccessful searches. Allocates the instance variable root and stores the subproblem roots in it. Keys are numbered 1 to n.

Parameters:

p - The array of probabilities of successful searches. p[i] is the probability that a search is for k_i. Entry p[0] is unused.

q - The array of probabilities of unsuccessful searches. q[i] is the probability that a search falls between keys k_i and k_i+1. q[0] is the probability that a search falls to the left of k₁, and q[n] is the probability that a search falls to the right of k_n.

Method Detail

optimalBST

public void optimalBST(double[] p,
                       double[] q,
                       int n)

Determines the structure of an optimal binary search tree, given an array of probabilities of successful searches for keys and an array of probabilities of unsuccessful searches. The instance variable root is assumed to be already allocated. Keys are numbered 1 to n. Implements the Optimal-BST procedure on page 361.

Parameters:

p - The array of probabilities of successful searches. p[i] is the probability that a search is for k_i. Entry p[0] is unused.

q - The array of probabilities of unsuccessful searches. q[i] is the probability that a search falls between keys k_i and k_i+1. q[0] is the probability that a search falls to the left of k₁, and q[n] is the probability that a search falls to the right of k_n.

getNumberOfKeys

public int getNumberOfKeys()

Returns the value of n.

getRootTable

public int[][] getRootTable()

Returns the table of roots of subtrees.