В рамках задания я создал набор утилит для работы с деревьями бинарного поиска. Проблема в том, что моя функция вставки бинарного дерева, по словам Вальгринда, протекает.
Я действительно не понимаю, где может быть проблема, так как я сравнил свой алгоритм со многими, найденными в Интернете. Кажется, что все они делают то же самое.
struct rep_binary
{
info_t data;
rep_binary*izq;
rep_binary*der;
};
typedef rep_binary *binary_t ;
static binary_t newNode(info_t i)
{
binary_t b = new rep_binary;
b->dato = i;
b->der = b->izq = NULL;
return b;
}
binary_t insert_on_binary(info_t i, binario_t b)
{
assert(binary_empty(find_subtree(info(i), b)));
if (binary_empty(b))
{
b = newNode(i);
}
else
{
if (strcmp(info(b->data), info(i)) > 0)
b->left= insert_on_binary(i, b->left);
else
b->right= insert_on_binary(i, b->right);
}
return b;
}
Вывод функции правильный, то есть, когда я печатаю деревья результатов, я получаю именно то, что вы ожидаете после вставки x узлов. Тем не менее, Valgrind сообщает, что по какой-то причине я теряю 12 байт на вставку.
Например, есть метод, который создает BST из связанного списка, содержащего 39 элементов, и после вставки этих 39 элементов я теряю 468 байт (39 * 12).
То же самое происходит со всеми другими методами, которые полагаются на вставку в BST для работы.
В качестве дополнительного примечания, при сопоставлении моих результатов с результатами задания нет никаких различий. Так работает, но где-то течет?