⬅ Optimal Binary Search Tree | Code Tutorial

public class Main {

	static final int MAX = 6;
	static String words[];

	public static void main(String[] args) {
		float[] probabilityHit = new float[MAX];
		float[] probabilityFailure = new float[MAX];
		Node root = null;
		words = new String[MAX];
		// The number of words
		int noOfWords = 4;
		// The actual words
		words[1] = "do";
		words[2] = "if";
		words[3] = "read";
		words[4] = "while";
		// The P's
		probabilityHit[1] = 1;
		probabilityHit[2] = 3;
		probabilityHit[3] = 1;
		probabilityHit[4] = 3;
		// The Q's
		probabilityFailure[0] = 1;
		probabilityFailure[1] = 2;
		probabilityFailure[2] = 1;
		probabilityFailure[3] = 1;
		probabilityFailure[4] = 3;
		// Construct the OBST
		root = optimal(probabilityHit, probabilityFailure, noOfWords);
		preOrder(root);
	}

	public static void preOrder(Node temp) {
		if (temp != null) {
			System.out.print(temp.data + " ");
			preOrder(temp.left);
			preOrder(temp.right);
		}
	}

	public static Node optimal(float probabilityHit[],
			float probabilityFailure[], int noOfWords) {
		Node root = null;
		float c[][] = new float[MAX][MAX];
		float w[][] = new float[MAX][MAX];
		int r[][] = new int[MAX][MAX];
		for (int i = 0; i <= noOfWords; i++) {
			for (int j = 0; j <= noOfWords; j++) {
				c[i][j] = w[i][j] = r[i][j] = 0;
			}
		}
		for (int i = 1; i <= noOfWords; i++) {
			w[i][i] = probabilityFailure[i - 1] + probabilityFailure[i]
					+ probabilityHit[i];
			c[i][i] = w[i][i];
			r[i][i] = i;
		}
		// Find an optimal tree with n nodes starting with tree with 2 nodes and
		// then increasing it by 1 in each iteration
		for (int step = 2; step <= noOfWords; step++) {
			// find an optimal tree with step number of nodes
			for (int i = 1; i <= noOfWords - step + 1; i++) {
				int j = i + step - 1;
				w[i][j] = w[i][j - 1] + probabilityHit[j]
						+ probabilityFailure[j];
				// find c[i][j] by selecting the minimum
				int k = find(c, i, j);
				c[i][j] = w[i][j] + c[i][k - 1] + c[k][j];
				r[i][j] = k;
			}
		}
		root = construct(r, 1, noOfWords);
		return root;
	}

	public static int find(float[][] c, int i, int j) {
		float min = 9999.0f;
		int l = 0;
		// l will give the index of the minimum element
		for (int k = i; k <= j; k++) {
			if (c[i][k - 1] + c[k + 1][j] < min) {
				min = c[i][k - 1] + c[k + 1][j];
				l = k;
			}
		}
		return l;
	}

	public static Node construct(int[][] r, int i, int j) {
		Node node = null;
		if (r[i][j] == 0) {
			return null;
		} else {
			node = new Node(words[r[i][j]]);
			node.left = construct(r, i, r[i][j] - 1);
			node.right = construct(r, r[i][j] + 1, j);
			return node;
		}
	}
}

class Node {
	String data;
	Node right;
	Node left;

	Node(String data) {
		this.data = data;
	}
}