#data-structures #binary-search-tree
#структуры данных #binary-search-tree
Вопрос:
У меня есть задание для оптимальных деревьев двоичного поиска, и при его выполнении возникли некоторые вопросы. Я нашел многие ссылки в Интернете полезными (только из поиска в Google), но мне было интересно…
Почему ключи должны быть отсортированы изначально?
Если я получить более низкую стоимость (за оптимальную по британскому летнему времени), когда ключи не сортируются, значит, там должна быть ошибка в моем коде?
Оптимальный по британскому летнему времени будет полный/совершенный? (используя определения Википедии complete и perfect)
Идеальное двоичное дерево — это полное двоичное дерево, в котором все листья имеют одинаковую глубину или одинаковый уровень. [1] (Это неоднозначно также называется полным двоичным деревом.)
Полное двоичное дерево — это двоичное дерево, в котором все уровни, кроме, возможно, последнего, полностью заполнены, а все узлы расположены как можно дальше слева. [2]
Что касается последнего вопроса, я бы предположил, что оптимальное дерево должно быть полным / совершенным, но некоторые онлайн-апплеты заставляют меня думать иначе. Я не могу объяснить, почему…
Ответ №1:
Почему ключи должны быть отсортированы изначально?
Они этого не делают. На самом деле, если вы не используете самобалансирующееся дерево, будет лучше, если вы добавите ключи в дерево в случайном порядке, потому что дерево в конечном итоге будет более сбалансированным.
Если я получить более низкую стоимость (за оптимальную по британскому летнему времени), когда ключи не сортируются, значит, там должна быть ошибка в моем коде?
Нет, если вы не кодируете самобалансирующееся дерево (ваш алгоритм самобалансировки не работает).
оптимальный по британскому летнему времени будет полный/совершенный?
ДА. Чтобы получить максимально быстрый поиск для данного дерева, все узлы дерева должны быть равномерно распределены; т. Е. Дерево должно быть как можно короче.
Комментарии:
1. Я не использую самобалансирующееся дерево. Означает ли это, что либо оптимальное дерево не является уникальным (при условии уникальных ключей), либо что дерево (упомянутое ранее сгенерированное с отсортированными ключами) не является оптимальным?
2. Несбалансированное двоичное дерево, в которое ключи вставлены в отсортированном порядке, не является оптимальным, поскольку ключи не будут распределяться равномерно. Вместо этого вы получите связанный список, потому что все ключи будут вставлены с одной стороны дерева. jaltiere.com/blogImages/redblacktree/binarysearchtree.png
3. ОК. Я понимаю все, что вы мне сказали, и теперь я точно определил свою проблему. Хотя не похоже, что большинство онлайн-апплетов вообще генерируют оптимальные деревья ( linneus20.ethz.ch:8080/4_7_2.html ) Например, использование 2,9 и 11 в качестве ключей должно оптимально создавать дерево с 11 в качестве корня, но я получаю это как оптимальный результат (9 — корень). postimage.org/image/fm8qsgkk Я не такойтем не менее, уверен, как я это исправлю. Если только у меня где-то нет недостатка в моей логике.
4. Неважно. Справа большие числа, слева меньшие.
Ответ №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 %sn", 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]=OtA[%d][%d]=Ot",i,i-1,A[i][i-1],i,i,A[i][i]);
fprintf(wp,"R[%d][%d]=OtR[%d][%d]=On", 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,"nn");
fprintf(wp,"%s is the root of the treen",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,"%st%ft%dn", 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", amp;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;
}
}
}