Блог

Я наткнулся на проблему, выполняя домашнее задание по DSA (структуры данных и алгоритмы). Говорят, что я реализую B-дерево с алгоритмами вставки и поиска. Насколько я понимаю, поиск работает корректно, но у меня возникли проблемы с реализацией функции вставки. В частности, логика алгоритма разделения узлов B-дерева. Псевдокод / C-стиль, который я мог бы придумать, заключается в следующем:

     #define D 2
    #define DD 2*D

    typedef btreenode* btree;
    typedef struct node
    {
        int keys[DD];  //D == 2 and DD == 2*D;
        btree pointers[DD 1];
        int index; //used to iterate throught the "keys" array
    }btreenode;

    void splitNode(btree* parent, btree* child1, btree* child2)
    {
        //Copies the content from the splitted node to the children
        (*child1)->key[0] = (*parent)->key[0];
        (*child1)->key[1] = (*parent)->key[1];
        (*child2)->key[0] = (*parent)->key[2];
        (*child2)->key[1] = (*parent)->key[3];
        (*child1)->index = 1;
        (*child2)->index = 1;
        //"Clears" the parent node from any data
        for(int i = 0; i<DD; i  ) (*parent)->key[i] = -1;
        for(int i = 0; i<DD 1; i  ) (*parent)->pointers[i] = NULL
        //Fixed the pointers to the children
        (*parent)->index = 0;
        //the line bellow was taken out for creating a new node  that didn't have to be there.
        //(*parent)->key[(*parent)->index] = newNode(); // The newNode() function allocs and inserts a the new key that I need to insert.
        (*parent)->pointers[index] = (*child1);
        (*parent)->pointers[index 1] = (*child2);
    }
 

Я почти уверен, что я что-то напутал с указателями, но я не уверен, что именно. Любая помощь приветствуется. Может быть, мне нужно немного больше изучить тему B-дерева? Я должен добавить, что, хотя я могу использовать базовый ввод / вывод с C , мне нужно использовать структуры в стиле C.

Здесь вам не нужно создавать новый узел. Очевидно, вы уже создали два новых дочерних узла. Все, что вам нужно сделать здесь после заполнения дочерних элементов, это заставить родительский элемент указывать на двух дочерних элементов через копию первого ключа в каждом из них и настроить его количество ключей на два. Вам также не нужно устанавливать родительские ключи равными -1.