Дерево поиска m-Way | Комплект-2 | Вставка и удаление

Опубликовано: 23 Января, 2022

Вставка в дерево поиска m-Way:


Вставка в дерево поиска m-Way аналогична бинарным деревьям, но в узле должно быть не более m-1 элементов. Если узел заполнен, будет создан дочерний узел для вставки дополнительных элементов.
Давайте посмотрим на приведенный ниже пример вставки элемента в дерево поиска m-Way.

Пример:

  • Чтобы вставить новый элемент в дерево поиска m-Way, мы действуем так же, как и при поиске элемента.
  • Чтобы вставить 6 в 5-стороннее дерево поиска, показанное на рисунке, мы переходим к поиску 6 и обнаруживаем, что мы выпадаем из дерева в узле [7, 12] с первым дочерним узлом, показывающим нулевой указатель.
  • Поскольку узел имеет только два ключа, а 5-стороннее дерево поиска может вместить до 4 ключей в узле, 6 вставляются в узел, как [6, 7, 12]
  • Но для вставки 146 узел [148, 151, 172, 186] уже заполнен, поэтому мы открываем новый дочерний узел и вставляем в него 146. Обе эти вставки показаны ниже.

// Inserts a value in the m-Way tree
struct node* insert(int val,
                    struct node* root)
{
    int i;
    struct node *c, *n;
    int flag;
  
    // Function setval() is called which
    // returns a value 0 if the new value
    // is inserted in the tree, otherwise
    // it returns a value 1
    flag = setval(val, root, &i, &c);
  
    if (flag) {
        n = (struct node*)malloc(sizeof(struct node));
        n->count = 1;
        n->value[1] = i;
        n->child[0] = root;
        n->child[1] = c;
        return n;
    }
    return root;
}

вставлять():

  • Функция insert () получает два параметра - адрес нового узла и значение, которое вставлено.
  • Эта функция вызывает функцию setval (), которая возвращает значение 0, если новое значение вставлено в дерево, в противном случае возвращает значение 1
  • Если он возвращает 1, тогда для нового узла выделяется память, переменной count присваивается значение 1, и новое значение вставляется в узел.
  • Затем адреса дочерних узлов сохраняются в дочерних указателях и, наконец, возвращается адрес узла.
// Sets the value in the node
int setval(int val,
           struct node* n,
           int* p,
           struct node** c)
{
    int k;
  
    // if node is null
    if (n == NULL) {
        *p = val;
        *c = NULL;
        return 1;
    }
    else {
  
        // Checks whether the value to be
        // inserted is present or not
        if (searchnode(val, n, &k))
            printf("Key value already exists ");
  
        // The if-else condition checks whether
        // the number of nodes is greater or less
        // than the maximum number. If it is less
        // then it inserts the new value in the
        // same level node, otherwise, it splits the
        // node and then inserts the value
        if (setval(val, n->child[k], p, c)) {
  
            // if the count is less than the max
            if (n->count < MAX) {
                fillnode(*p, *c, n, k);
                return 0;
            }
            else {
  
                // Insert by splitting
                split(*p, *c, n, k, p, c);
                return 1;
            }
        }
        return 0;
    }
}

setval():

  • The function setval() receives four parameters
    • The first argument is the value that is to be inserted
    • The second argument is the address of the node
    • The third argument is an integer pointer that points to a local flag variable defined in the function insert()
    • The last argument is a pointer to pointer to the child node that will be set in a function called from this function
  • The function setval() returns a flag value that indicates whether the value is inserted or not
  • If the node is empty then this function calls a function searchnode() that checks whether the value already exists in the tree
  • If the value already exists then a suitable message is displayed
  • Then a recursive call is made to the function setval() for the child of the node
  • If this time the function returns a value 1 it means the value is not inserted
  • Then a condition is checked whether the node is full or not
  • If the node is not full then a function fillnode() is called that fills the value in the node hence at this point a value 0 is returned
  • If the node is full then a function split() called that splits the existing node. At this point, a value 1 is returned to add the current value to the new node
// Adjusts the value of the node
void fillnode(int val,
              struct node* c,
              struct node* n,
              int k)
{
    int i;
  
    // Shifting the node by one position
    for (i = n->count; i > k; i--) {
        n->value[i + 1] = n->value[i];
        n->child[i + 1] = n->child[i];
    }
    n->value[k + 1] = val;
    n->child[k + 1] = c;
    n->count++;
}

fillnode():

  • The function fillnode() receives four parameters
    • The first is the value that is to be inserted
    • The second is the address of the child node of the new value that is to be inserted
    • The third is the address of the node in which the new value is to be inserted
    • The last parameter is the position of the node where the new value is to be inserted
// Splits the node
void split(int val,
           struct node* c,
           struct node* n,
           int k, int* y,
           struct node** newnode)
{
    int i, mid;
    if (k <= MIN)
        mid = MIN;
    else
        mid = MIN + 1;
  
    // Allocating the memory for a new node
    *newnode = (struct node*)
malloc(sizeof(struct node));
  
    for (i = mid + 1; i <= MAX; i++) {
        (*newnode)->value[i - mid] = n->value[i];
        (*newnode)->child[i - mid] = n->child[i];
    }
  
    (*newnode)->count = MAX - mid;
    n->count = mid;
  
    // it checks whether the new value
    // that is to be inserted is inserted
    // at a position less than or equal
    // to minimum values required in a node
    if (k <= MIN)
        fillnode(val, c, n, k);
    else
        fillnode(val, c, *newnode, k - mid);
  
    *y = n->value[n->count];
    (*newnode)->child[0] = n->child[n->count];
    n->count--;
}

расколоть():

  • Функция split () получает шесть параметров
    • Первые четыре параметра точно такие же, как и в случае функции fillnode ()
    • Пятый параметр - это указатель на переменную, которая содержит значение, из которого разделен узел.
    • Последний параметр - указатель на указатель нового узла, созданного во время разделения.
  • В этой функции сначала проверяется, вставлено ли новое значение, которое должно быть вставлено, в позицию, меньшую или равную минимальным значениям, требуемым в узле.
  • Если условие выполнено, узел разбивается в позиции MIN.
  • В противном случае узел разбивается на одну позицию больше MIN.
  • Затем динамически выделяется память для нового узла
  • Затем выполняется цикл for, который копирует в новый узел значения и дочерние элементы, которые появляются справа от значения, из которого узел разделен.

Удаление в дереве поиска m-Way:


Пусть K будет ключом, который нужно удалить из дерева поиска m-Way. Для удаления ключа действуем так же, как при поиске ключа. Пусть узел, в котором находится ключ, будет таким, как показано ниже.

Подход:
Есть несколько случаев удаления

  • Если (A i = A j = NULL), удалить K
  • Если (A i ! = NULL, A j = NULL), тогда выберите самый большой из ключевых элементов K ' в дочернем узле, на который указывает A i , удалите ключ K' и замените K на K '
  • Очевидно, что удаление K ' может потребовать последующих замен и, следовательно, удалений аналогичным образом, чтобы позволить ключу K' двигаться вверх по дереву.
  • Если (A i = NULL, A j ! = NULL), тогда выберите наименьший из ключевых элементов K » из поддерева, на которое указывает A j , удалите K» и замените K на K »
  • Опять же, удаление K ” может вызвать последующие замены и удаления, чтобы позволить K” продвинуться вверх по дереву.
  • Если (A i ! = NULL, A j ! = NULL), тогда выберите либо наибольший из ключевых элементов K ' в поддереве, на которое указывает A i , либо наименьший из ключевых элементов K ” из поддерева на который указывает A j, чтобы заменить K
  • Как упоминалось ранее, для перемещения K ' или K ” вверх по дереву может потребоваться последующая замена и удаление.

Example:

  • To delete 151, we search for 151 and observe that in the leaf node [148, 151, 172, 186] where it is present, both its left sub-tree pointer and right sub-tree pointer are such that (Ai = Aj = NULL)
  • We therefore simply delete 151 and the node becomes [148, 172, 186]. Deletion of 92 also follows a similar process
  • To delete 262, we find its left and right sub-tree pointers Ai</sub and Aj respectively, are such that (Ai = Aj = NULL)
  • Hence we choose the smallest element 272 from the child node [272, 286, 350], delete 272 and replace 262 with 272. Note that, to delete 272 the deletion procedure needs to be observed again

    This deletion is illustrated below



  • To delete 12, we find the node [7, 12] accommodates 12 and the key satisfies (Ai != NULL, Aj = NULL)
  • Hence we choose the largest of the keys from the node pointed to by Ai, viz., 10 and replace 12 with 10. This deletion is illustrated below

// Deletes value from the node
struct node* del(int val,
                 struct node* root)
{
    struct node* temp;
    if (!delhelp(val, root)) {
        printf(" ");
        printf("value %d not found. ", val);
    }
    else {
        if (root->count == 0) {
            temp = root;
            root = root->child[0];
            free(temp);
        }
    }
    return root;
}

del():

  • The function del() receives two parameters. First is the value that is to be deleted second is the address of the root node
  • This function calls another helper function delhelp() which returns value 0 if the deletion of the value is unsuccessful, 1 otherwise
  • Otherwise, a condition is checked whether the count is 0
  • If it is, then it indicates that the node from which the value is deleted is the last value
  • Hence, the first child of the node is itself made the node and the original node is deleted. Finally, the address of the new root node is returned
// Helper function for del()
int delhelp(int val,
            struct node* root)
{
    int i;
    int flag;
    if (root == NULL)
        return 0;
    else {
  
        // Again searches for the node
        flag = searchnode(val,
                          root,
                          &i);
  
        // if flag is true
        if (flag) {
            if (root->child[i - 1]) {
                copysucc(root, i);
                // delhelp() is called recursively
                flag = delhelp(root->value[i],
                                root->child[i]) 
                 if (!flag)
                {
                    printf(" ");
                    printf("value %d not found. ", val);
                }
            }
            else
                clear(root, i);
        }
        else {
            // Recursion
            flag = delhelp(val, root->child[i]);
        }
  
        if (root->child[i] != NULL) {
            if (root->child[i]->count < MIN)
                restore(root, i);
        }
        return flag;
    }
}

delhelp():

  • The function delhelp() receives two parameters. First is the value to be deleted and the second is the address of the node from which it is to be deleted
  • Initially it is checked whether the node is NULL
  • If it is, then a value 0 is returned
  • Otherwise, a call to function searchnode() is made
  • If the value is found then another condition is checked to see whether there is any child to the value that is to be deleted
  • If so, the function copysucc() is called which copies the successor of the value to be deleted and then a recursive call is made to the function delhelp() for the value that is to be deleted and its child
  • If the child is empty then a call to function clear() is made which deletes the value
  • If the searchnode() function fails then a recursive call is made to function delhelp() by passing the address of the child
  • If the child of the node is not empty, then a function restore() is called to merge the child with its siblings
  • Finally the value of the flag is returned which is set as a returned value of the function searchnode()
// Removes the value from the
// node and adjusts the values
void clear(struct node* m, int k)
{
    int i;
    for (i = k + 1; i <= m->count; i++) {
        m->value[i - 1] = m->value[i];
        m->child[i - 1] = m->child[i];
    }
    m->count--;
}

clear():

  • The function clear() receives two parameters. First is the address of the node from which the value is to be deleted and second is the position of the value that is to be deleted
  • This function simply shifts the values one place to the left from the position where the value is to be deleted is present
// Copies the successor of the
// value that is to be deleted
void copysucc(struct node* m, int i)
{
    struct node* temp;
    temp = p->child[i];
    while (temp->child[0])
        temp = temp->child[0];
    p->value[i] = temp->value[i];
}

copysucc()

  • The function copysucc() receives two parameters. First is the address of the node where the successor is to be copied and second is the position of the value that is to be overwritten with its successor
// Adjusts the node
void restore(struct node* m, int i)
{
    if (i == 0) {
        if (m->child[1]->count > MIN)
            leftshift(m, 1);
        else
            merge(m, 1);
    }
    else {
        if (i == m->count) {
            if (m->child[i - 1]->count > MIN)
                rightshift(m, i);
            else
                merge(m, i);
        }
        else {
            if (m->child[i - 1]->count > MIN)
                rightshift(m, i);
            else {
                if (m->child[i + 1]->count > MIN)
                    leftshift(m, i + 1);
                else
                    merge(m, i);
            }
        }
    }
}

restore():

  • The function restore() receives two parameters. First is the node that is to be restored and second is the position of the value from where the values are restored
  • If the second parameter is 0, then another condition is checked to find out whether the values present at the first child are more than the required minimum number of values
  • If so, then a function leftshift() is called by passing the address of the node and a value 1 signifying that the value of this node is to be shifted from the first value
  • If the condition is not satisfied then a funcition merge() is called for merging the two children of the node
// Adjusts the values and children
// while shifting the value from
// parent to right child
void rightshift(struct node* m, int k)
{
    int i;
    struct node* temp;
  
    temp = m->child[k];
  
    // Copying the nodes
    for (i = temp->count; i > 0; i--) {
        temp->value[i + 1] = temp->value[i];
        temp->child[i + 1] = temp->child[i];
    }
    temp->child[1] = temp->child[0];
    temp->count++;
    temp->value[1] = m->value[k];
  
    temp = m->child[k - 1];
    m->value[k] = temp->value[temp->count];
    m->child[k]->child[0] 
                = temp->child[temp->count];
    temp->count--;
}
  
// Adjusts the values and children
// while shifting the value from
// parent to left child
void leftshift(struct node* m, int k)
{
    int i;
    struct node* temp;
  
    temp = m->child[k - 1];
    temp->count++;
    temp->value[temp->count] = m->value[k];
    temp->child[temp->count] 
                   = m->child[k]->child[0];
  
    temp = m->child[k];
    m->value[k] = temp->value[1];
    temp->child[0] = temp->child[1];
    temp->count--;
  
    for (i = 1; i <= temp->count; i++) {
        temp->value[i] = temp->value[i + 1];
        temp->child[i] = temp->child[i + 1];
    }
}

rightshift() and leftshift()

  • The function rightshift() receives two parameters
  • First is the address of the node from where the value is shifted to its child and second is the position k of the value that is to be shifted
  • The function leftshift() are exactly same as that of function rightshift()
  • The function merge() receives two parameters. First is the address of
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022