8D.cpp

#include <iostream>
using namespace std;
#define SIZE 10

class OBST
{
    int p[SIZE];       // Probabilities with which we search for an element
    int q[SIZE];       // Probabilities that an element is not found
    int a[SIZE];       // Elements from which OBST is to be built
    int w[SIZE][SIZE]; // Weight 'w[i][j]' of a tree having root 'r[i][j]'
    int c[SIZE][SIZE]; // Cost 'c[i][j]' of a tree having root 'r[i][j]
    int r[SIZE][SIZE]; // Represents root
    int n;             // number of nodes

public:
    /* This function accepts the input data */
    void get_data()
    {
        int i;
        cout << "\n Optimal Binary Search Tree \n";
        cout << "\n Enter the number of nodes: ";
        cin >> n;
        cout << "\n Enter the data as...\n";
        for (i = 1; i <= n; i++)
        {
            cout << "\n a[" << i << "]: ";
            cin >> a[i];
        }
        for (i = 1; i <= n; i++)
        {
            cout << "\n p[" << i << "]: ";
            cin >> p[i];
        }
        for (i = 0; i <= n; i++)
        {
            cout << "\n q[" << i << "]: ";
            cin >> q[i];
        }
    }

    /* This function returns a value in the range 'r[i][j-1]' to 'r[i+1][j]' so that the cost 'c[i][k-1]+c[k][j]' is minimum */
    int Min_Value(int i, int j)
    {
        int m, k;
        int minimum = 32000;
        for (m = r[i][j - 1]; m <= r[i + 1][j]; m++)
        {
            if ((c[i][m - 1] + c[m][j]) < minimum)
            {
                minimum = c[i][m - 1] + c[m][j];
                k = m;
            }
        }
        return k;
    }

    /* This function builds the table from all the given probabilities. It basically computes C, r, W values */
    void build_OBST()
    {
        int i, j, k, m;
        for (i = 0; i < n; i++)
        {
            w[i][i] = q[i];
            r[i][i] = c[i][i] = 0;
            w[i][i + 1] = q[i] + q[i + 1] + p[i + 1];
            r[i][i + 1] = i + 1;
            c[i][i + 1] = q[i] + q[i + 1] + p[i + 1];
        }
        w[n][n] = q[n];
        r[n][n] = c[n][n] = 0;
        for (m = 2; m <= n; m++)
        {
            for (i = 0; i <= n - m; i++)
            {
                j = i + m;
                w[i][j] = w[i][j - 1] + p[j] + q[j];
                k = Min_Value(i, j);
                c[i][j] = w[i][j] + c[i][k - 1] + c[k][j];
                r[i][j] = k;
            }
        }
    }

    void build_tree()
    {
        int i, j, k;
        int queue[20], front = -1, rear = -1;
        cout << "The Optimal Binary Search Tree For the Given Node Is...\n";
        cout << "\n The Root of this OBST is: " << r[0][n];
        cout << "\nThe Cost of this OBST is: " << c[0][n];
        cout << "\n\n\t NODE \t LEFT CHILD \t RIGHT CHILD ";
        cout << "\n";
        queue[++rear] = 0;
        queue[++rear] = n;
        while (front != rear)
        {
            i = queue[++front];
            j = queue[++front];
            k = r[i][j];
            cout << "\n\t" << k;
            if (r[i][k - 1] != 0)
            {
                cout << "\t\t" << r[i][k - 1];
                queue[++rear] = i;
                queue[++rear] = k - 1;
            }
            else
            {
                cout << "\t\t";
            }
            if (r[k][j] != 0)
            {
                cout << "\t" << r[k][j];
                queue[++rear] = k;
                queue[++rear] = j;
            }
            else
            {
                cout << "\t";
            }
        }
        cout << "\n";
    }
};

int main()
{
    OBST obj;
    obj.get_data();
    obj.build_OBST();
    obj.build_tree();
    return 0;
}