Created
March 3, 2019 03:09
-
-
Save graphoarty/b6bde1309809d689de058c9fa3b53ad5 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment