Optimal Binary Search Tree in C++

main.cpp

#include <iostream>
#include "OptimalBST.h"

int main(){
    // three example sets of probabilities 
    float P1[] = {0.0f,0.1f,0.2f,0.4f,0.3f};
    float P2[] = {0.0f,0.1f,0.2f,0.2f,0.5f};
    float P3[] = {0.0f,0.4f,0.1f,0.2f,0.3f};

    OptimalBST optimalBSTArray[] = {OptimalBST(P1,4),OptimalBST(P2,4),OptimalBST(P3,4)};

    for(int i = 0; i < 3; i++) {
        optimalBSTArray[i].generateOptimalBST();

        optimalBSTArray[i].printCostTable();
        std::cout << std::endl;
        optimalBSTArray[i].printRootTable();
        std::cout << std::endl;
    }

    return 0;
}

OptimalBST.cpp

#include "OptimalBST.h"

template<class T>
void clearTable(T **table, int, int, float);
bool greaterThan(float a, float b);

// constructor
OptimalBST::OptimalBST(float* _probabilities, int size)
    :numColumns(size+1), numRows(size+2), numberOfProbabilities(size)
{
    probabilities = new float[size+1];
    for(int i = 0; i < size+1; i++)
        this->probabilities[i] = _probabilities[i];

    costTable = new float*[numColumns];
    rootTable = new int*[numColumns];
    for(int i = 0; i < numRows; i++){
        costTable[i] = new float[numColumns];
        rootTable[i] = new int[numColumns];
    }

    clearTable(costTable,numRows,numColumns,0.0f);
    clearTable(rootTable,numRows,numColumns,0.0f);
}

OptimalBST::~OptimalBST(){
    for(int i = 0; i < numRows; i++){
        delete costTable[i];
        delete rootTable[i];
    }
    delete[] costTable;
    delete[] rootTable;
}

// generates an optimal BST by computing the cost of
// subtrees using dynamic programming technique
void OptimalBST::generateOptimalBST(){
    for(int i = 1; i <= numberOfProbabilities; i++){
        costTable[i][i-1] = 0;
        costTable[i][i] = probabilities[i];
        rootTable[i][i] = i;
    }

    for(int d = 1; d < numberOfProbabilities; d++){
        //std::cout << "d value: " << d << std::endl;
        for(int i = 1; i <= (numberOfProbabilities - d);i++){
            int j = i + d;
            int kmin = 0; float minVal =  std::numeric_limits<float>::infinity();
            for(int  k = i; k <= j; k++){
                float cost1 = costTable[i][k-1];
                float cost2 = costTable[k+1][j];
                if( !greaterThan(cost1 + cost2 , minVal)){
                    minVal = cost1 + cost2;
                    kmin = k;
                }
            }
            rootTable[i][j] = kmin;
            float sum = probabilities[i];
            for(int s = i+1; s <= j; s++){
                sum += probabilities[s];
            }
            costTable[i][j] = minVal + sum;
        }
    }

    //std::cout << "root node has: "<< costTable[1][numberOfProbabilities] << std::endl;
}

// prints the cost table
void OptimalBST::printCostTable() const{
    std::cout << "C Table ----------" << std::endl;
    std::cout.width(-2);
    for(int i = 0; i < numRows;i++){
        if(i <= 0)
            std::cout <<"\t\t";
        else
            std::cout << "\t" << i << "\t";
        for (int j = 0; j < numColumns; j++) {
            std::cout.width(4);
            if(i != 0)
                std::cout << std::right << costTable[i][j] << "\t";
            else
                std::cout << j << "\t";
        }
        std::cout << std::endl;
    }
}

// Prints the root Table
void OptimalBST::printRootTable() const{
    std::cout << "R Table ----------" << std::endl;
    std::cout.width(-2);
    for(int i = 0; i < numRows;i++){
        if(i <= 0)
            std::cout <<"\t\t";
        else
            std::cout << "\t" << i << "\t";
        for (int j = 0; j < numColumns; j++) {
            std::cout.width(4);
            if(i != 0)
                std::cout << std::right << rootTable[i][j] << "\t";
            else
                std::cout << j << "\t";
        }
        std::cout << std::endl;
    }
}

// compares a and b, if a is greater return true else return false
bool greaterThan(float a, float b) {
    return (a - b) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a))
                       * (float)std::numeric_limits<float>::epsilon());
}

// clears a table to with some value
// default is -1.0f
template<class T>
void clearTable(T **table, int rows, int cols, float clearValue = -1.0f){
    int c = 0;
	for(int i = 0; i < rows; i++){
        for(int j = 0; j < cols; j++,c++){
            table[i][j] = (T) clearValue;
        }
	}
}

OptimalBST.h

#ifndef _OPTIMAL_BST_H
#define _OPTIMAL_BST_H

#include <iostream>
#include <climits>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <iomanip>
#include <limits>

class OptimalBST{
private:
    const int numColumns;
    const int numRows;
    const int numberOfProbabilities;
	float** costTable;
	int** rootTable;
    float* probabilities;

public:
    OptimalBST(float* probabilities, int size);
	~OptimalBST();
	void printCostTable() const;
	void printRootTable() const;
	void generateOptimalBST();
};

#endif