Оптимальные деревья бинарного поиска

Question

У меня есть задание по оптимальным деревьям бинарного поиска, и при этом возникли вопросы. Многие ссылки в Интернете были полезными (только из поиска в Google), но мне было интересно ...

Почему ключи должны быть изначально отсортированы?

Если я получаю более низкую стоимость (для оптимального BST), когда ключи не отсортированы, означает ли это, что в моем коде должна быть ошибка?

Должен ли оптимальный BST быть полным / идеальным? (используя определения Википедии полных и совершенных)

Идеальное двоичное дерево - это полное двоичное дерево, в котором все листья находятся на одной глубине или на одном уровне. [1] (Это также неоднозначно называется полным двоичным деревом.)

Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, а все узлы расположены как можно левее. [2]

Что касается последнего вопроса, я бы предположил, что оптимальное дерево должно быть полным / совершенным, но некоторые онлайн-апплеты заставляют меня поверить в обратное. Я не могу объяснить, почему ...

Answer 1

Почему ключи должны быть изначально отсортированы?

Они не.На самом деле, если вы не используете самобалансирующееся дерево, лучше, если вы добавите ключи к дереву в случайном порядке, потому что дерево получит более сбалансированное.

Если я получуболее низкая стоимость (для оптимального BST), когда ключи не отсортированы, означает ли это, что в моем коде должна быть ошибка?

Нет, если вы не кодируете самобалансирующееся дерево (вашеАлгоритм самобалансировки не работает).

должен ли оптимальный BST быть полным / совершенным?

Да.Чтобы получить максимально быстрый поиск для данного дерева, все узлы дерева должны быть равномерно распределены;то есть дерево должно быть как можно короче.

Answer 2

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;
                         }
          }
}