OptimalBSTree.java

//Optimalno binarno iskalno drevo
 
public class OptimalBSTree extends BSTree {
  public OptimalBSTree() {
    super() ;
  }
  public double computeOptimalBSTree(double p[], double q[], Comparable keys[], int n) {
    int r[][] = new int[n+1][n+1] ;
    double t[][] = new double[n+1][n+1] ;
    double w[][] = new double[n+1][n+1] ;
    int i,j ; // stevca,  spodnji in zgornji indeks drevesa
    int h ; // stevilo elementov trenutnega drevesa
    int m ; // indeks korena za optimalno poddrevo
    double mint ; // minimalni iskalni cas za optimalno drevo
    int l ; // stevec za minimizacijo casa
    for (i= 0 ; i<= n ; i++) { // izracun tez w vseh poddreves
       w[i][i] = q[i];
       for (j = i+1 ; j <= n ; j++)
         w[i][j] = w[i][j-1] + p[j] + q[j] ;
    }
    for (i = 0 ; i <= n ; i++) t[i][i] = 0;     // casi praznih poddreves
    for (i = 0 ; i <= n-1 ; i++) { // casi poddreves z enim elementom
       j = i+1;
       t[i][j] = w[i][j]; // t[i,i] + t[j,j]  = 0
       r[i][j] = j;  // koren poddrevesa z enim elementom
    }
    // poddrevesa z 2, 3, ..., n elementi
    for (h = 2 ; h <=n ; h++)
       for (i = 0 ; i <= n-h ; i++) { // spodnji index
           j = i+h; // zgornji index
           m = r[i][j-1] ;
           mint = t[i][m-1] + t[m][j];
           // iskanje optimalnega korena m
           for (l = m+1 ; l <= r[i+1][j] ; l++) {
             if (t[i][l-1] + t[l][j] < mint) {
               m = l;
               mint = t[i][l - 1] + t[l][j];
             }
           } // for l
           t[i][j] = mint + w[i][j];  // optimalni cas
           r[i][j] = m  ; // optimalni koren
       }//  for h
     rootNode = buildOSTree(r, keys, 0, n) ;
     return t[0][n] ;
  }
 
  private BSTreeNode buildOSTree(int r[][], Comparable keys[], int i, int j) {
    // zgradi (pod)drevo, ki vsebuje elemente keys[i+1] .. keys[j] *
    BSTreeNode p;
    if (i == j)
      return null;
    else {
      p = new BSTreeNode(keys[r[i][j]]);
      p.right = buildOSTree(r, keys, r[i][j], j);
      p.left = buildOSTree(r, keys, i, r[i][j] - 1);
      return p;
    }
  }
 
  public static void main(String[] args) {
    OptimalBSTree tree = new OptimalBSTree();
 
    double p[] = {0.0, 0.1, 0.2, 0.3, 0.1} ;
    double q[] = {0.05, 0.05, 0.05, 0.05, 0.1} ;
    String keys[] = {"","droben", "majhen", "srednji", "velik"} ;
 
    double optTime = tree.computeOptimalBSTree(p,q,keys,4) ;
    System.out.println("Optimal access time: "+optTime);
    tree.printTree() ;
  }
}