Optimal Binary Search Trees

I have an assignment on optimal binary search trees and some questions came up while doing it. I have found many of the links online helpful (just from a Google search) but I was wondering...

W开发者_如何学Pythonhy must the keys must be initially sorted?

If I get a lower cost (for an optimal BST) when the keys are not sorted, does that mean there must be an error in my code?

Must an optimal BST be complete/perfect? (using the Wikipedia definitions of complete and perfect)

A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level. [1] (This is ambiguously also called a complete binary tree.)

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. [2]

For the last question, I would assume that an optimal tree must be complete/perfect, but some of the applets online lead me to believe otherwise. I cannot reason why though...

---

Why must the keys be initially sorted?

They don't. In fact, unless you're using a self-balancing tree, it's better if you add the keys to the tree in random order, because the tree will end up more balanced.

If I get a lower cost (for an optimal BST) when the keys are not sorted, does that mean there must be an error in my code?

Not unless you're coding up a self-balancing tree (your self-balancing algorithm is not working).

must an optimal BST be complete/perfect?

Yes. In order to get the fastest possible search for a given tree, all of the tree's nodes must be equally distributed; i.e. the tree must be as short as possible.

---

void OptimalBinsearchtree_output(float R[21][20],int i, int j, int r1, char  *dir)
{
          int t;
          if (i <= j)
          {
                         t =(int)R[i][j];
                         fprintf(wp,"%s is %s child of %s\n", name[t], dir, name[r1]);
                         OptimalBinsearchtree_output(R,i, t - 1, t, "left");
                         OptimalBinsearchtree_output(R,t + 1, j, t, "right");
          }
}

void OptimalBinarySearchTree(int n, const float p[],float *minavg)
{
          int i, j, k, diagonal,l,pos;
          float R[21][20];
          float min = 0;
          float A[21][20],sum=0;
          printf("\n");
          for (i = 1; i <=n; i++) 
          {
                         A[i][i - 1] = 0;
                         R[i][i - 1] = 0;
                         A[i][i] = p[i];
                         R[i][i] = i;
                         fprintf(wp,"A[%d][%d]=%4f\tA[%d][%d]=%4f\t",i,i-1,A[i][i-1],i,i,A[i][i]);
                         fprintf(wp,"R[%d][%d]=%4f\tR[%d][%d]=%4f\n", i, i - 1, R[i][i - 1], i, i, R[i][i]);
          }

          A[n+1][n] = 0;
          R[n+1][n] = 0;
          for (diagonal = 1; diagonal <= n - 1; diagonal++)
          {
                         for (i = 1; i <= n - diagonal; i++)
                         {
                                       min = 0;
                                       sum = 0;
                                       j = i + diagonal;
                                       for (l = i; l <=j; l++)
                                       {
                                                      sum = sum + p[l];
                                       }
                                       A[i][j] = sum;
                                       for (k = i; k <= j; k++)
                                       {
                                                      sum = A[i][k - 1] + A[k + 1][j];
                                                      if (min == 0)
                                                      {
                                                                    min = sum;
                                                                    pos = k;
                                                      }
                                                      else if (sum<min)
                                                      {
                                                                    min = sum;
                                                                    pos = k;
                                                      }
                                       }
                                       A[i][j] += min;
                                       R[i][j] = pos;
                         }
          }

          *minavg = A[1][n];
          printf("\n");
          for (i = 1; i <= n; i++)
          {
                         for (j = 0; j <= n; j++)
                         {
                                       printf("%0.3f ", R[i][j]);
                         }
                         printf("\n");
          }
          for (i = 1; i <= n; i++)
          {
                         for (j = 0; j <= n; j++)
                         {
                                       printf("%0.3f ", A[i][j]);
                         }
                         printf("\n");
          }
          fprintf(wp,"\n\n");
          fprintf(wp,"%s is the root of the tree\n",name[(int)R[1][n]]);
          int r1 = (int)R[1][n];
          OptimalBinsearchtree_output(R,1, r1 - 1, r1, "left");
          OptimalBinsearchtree_output(R,r1 + 1, n, r1, "right");

}


void removeall()
{
          nodeptr node,temp;
          node = head;
          while (node->next != NULL)
          {
                         temp = node;
                         node = node->next;
          }
          if (node == node->next)
          {
                         node->next = NULL;                     
                         temp->next = NULL;
                         free(node);
                         return;
          }
          node->next = NULL;
          temp->next = NULL;
          free(node);
}

void print()
{
          nodeptr curr = NULL, temp = NULL;
          curr = head;
          gl_index = 1;
          while (curr != NULL)
          {

                         curr->index = gl_index;
                         gl_p[gl_index] = curr->val;
                         strcpy(name[gl_index], curr->str);
                         gl_index++;
                         wp=fopen("Output.txt","w+");
                         fprintf(wp,"%s\t%f\t%d\n", curr->str, curr->val, curr->index);
                         curr = curr->next;
          }
}


void generatenode()
{


          int i, j;
          nodeptr temp = NULL;
          char a[20];

          while (!feof(fp))
          {
                         nodeptr curr = NULL, prev = NULL;
                         temp = (struct node*)malloc(sizeof(struct node));
                         fscanf(fp, "%s", &temp->str);
                         fgets(a, 20, fp);
                         temp->index = gl_index;
                         b = atof(a);
                         int flag = 0;
                         temp->val = b;
                         gl_p[gl_index] = temp->val;
                         gl_index++;
                         temp->next = NULL;
                         if (head == NULL)
                         {
                                       head = temp;
                                       curr = head;
                         }
                         else
                         {
                                       curr = head;
                                       while (!(strcmp(temp->str, curr->str) < 0))
                                       {
                                                      if(curr->next==NULL)
                                                      {
                                                                    curr->next = temp;
                                                                    curr = curr->next;
                                                                    temp->next = NULL;
                                                                    flag = 0;
                                                                    break;
                                                      }
                                                      else
                                                      {
                                                                    flag = 1;
                                                                    prev = curr;
                                                                    curr = curr->next;
                                                      }
                                       }
                                       if (curr == head)
                                       {
                                                      temp->next = curr;
                                                      head = temp;
                                       }
                                       else
                                       {
                                                      if (flag == 1)
                                                      {
                                                      prev->next = temp;
                                                      temp->next = curr;
                                                      }
                                       }
                                       flag = 0;
                         }
          }
}