Рубрики

Операция удаления в B-Tree

Рекомендуется ссылаться на следующие посты в качестве предпосылки этого поста.

B-Tree | Комплект 1 (Введение)
B-Tree | Комплект 2 (Вставка)

B-Tree — это разновидность дерева многоцелевого поиска. Итак, если вы не знакомы с деревьями многоцелевого поиска в целом, лучше взглянуть на эту видео-лекцию из ИИТ-Дели , прежде чем продолжить. Как только вы разберетесь с основами дерева многоцелевого поиска, операции с B-Tree станут более понятными.

Источником следующего объяснения и алгоритма является Введение в алгоритмы, 3-е издание, Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест

Процесс удаления:
Удаление из B-дерева сложнее, чем вставка, потому что мы можем удалить ключ из любого узла, а не только из листа, и когда мы удаляем ключ из внутреннего узла, нам придется переставить дочерние узлы.

Как и во вставке, мы должны убедиться, что удаление не нарушает свойства B-дерева . Так же, как мы должны были убедиться, что узел не стал слишком большим из-за вставки, мы должны убедиться, что узел не становится слишком маленьким во время удаления (за исключением того, что корню разрешено иметь меньше минимального числа t-1 ключей). Точно так же, как простому алгоритму вставки может потребоваться выполнить резервное копирование, если узел на пути к месту вставки ключа заполнен, простой подход к удалению может потребовать резервного копирования, если узел (отличный от корня) вдоль пути где ключ должен быть удален, имеет минимальное количество ключей.

Процедура удаления удаляет ключ k из поддерева с корнем в x. Эта процедура гарантирует, что всякий раз, когда она рекурсивно вызывает себя на узле x, количество ключей в x по меньшей мере равно минимальной степени t. Обратите внимание, что для этого условия требуется на один ключ больше, чем минимум, требуемый обычными условиями B-дерева, поэтому иногда может потребоваться переместить ключ в дочерний узел, прежде чем рекурсия перейдет к этому дочернему узлу. Это усиленное условие позволяет нам удалять ключ из дерева за один проход вниз без необходимости выполнять «резервное копирование» (с одним исключением, которое мы объясним). Вы должны интерпретировать следующую спецификацию для удаления из B-дерева с пониманием, что если корневой узел x когда-либо станет внутренним узлом, не имеющим ключей (такая ситуация может возникнуть в случаях 2c и 3b, тогда мы удаляем x, а единственный дочерний элемент x x .c1 становится новым корнем дерева, уменьшая высоту дерева на единицу и сохраняя свойство того, что корень дерева содержит хотя бы один ключ (если дерево не пусто).

Мы зарисовываем, как удаление работает с различными случаями удаления ключей из B-дерева.

1. Если ключ k находится в узле x и x является листом, удалите ключ k из x.

2. Если ключ k находится в узле x, а x является внутренним узлом, выполните следующие действия.

a) Если дочерний элемент y, который предшествует k в узле x, имеет по крайней мере t ключей, то найдите предшественника k0 для k в поддереве с корнем в y. Рекурсивно удалите k0 и замените k на k0 в x. (Мы можем найти k0 и удалить его за один проход вниз.)

б) Если у y меньше, чем t ключей, то симметрично рассмотрим дочерний элемент z, следующий за k в узле x. Если z имеет хотя бы t ключей, то найдите преемника k0 для k в поддереве с корнем в z. Рекурсивно удалите k0 и замените k на k0 в x. (Мы можем найти k0 и удалить его за один проход вниз.)

c) В противном случае, если у y и z есть только ключи t-1, объедините k и все z в y, чтобы x потерял и k, и указатель на z, а y теперь содержит ключи 2t-1. Затем освободите z и рекурсивно удалите k из y.

3. Если ключ k отсутствует во внутреннем узле x, определите корень xc (i) соответствующего поддерева, которое должно содержать k, если k вообще есть в дереве. Если xc (i) имеет только t-1 ключи, выполните шаги 3a или 3b по мере необходимости, чтобы гарантировать, что мы спустимся к узлу, содержащему не менее t ключей. Затем закончите, вернувшись к соответствующему потомку x.

a) Если xc (i) имеет только ключи t-1, но имеет непосредственного брата по крайней мере с t ключами, дайте xc (i) дополнительную клавишу, переместив ключ из x вниз в xc (i), переместив ключ из xc (i) непосредственный левый или правый брат в x, и перемещение соответствующего дочернего указателя из сестры в xc (i).

б) Если xc (i) и оба ближайших брата xc (i) имеют ключи t-1, объедините xc (i) с одним братом, что включает перемещение ключа из x вниз в новый объединенный узел, чтобы стать медианой ключ для этого узла.

Поскольку большинство ключей в B-дереве находятся в листьях, операции удаления чаще всего используются для удаления ключей из листьев. Затем процедура рекурсивного удаления действует за один проход вниз по дереву без необходимости резервного копирования. Однако при удалении ключа во внутреннем узле процедура выполняет нисходящий проход по дереву, но может потребоваться вернуться к узлу, из которого был удален ключ, чтобы заменить ключ его предшественником или преемником (случаи 2a и 2b).

Следующие цифры объясняют процесс удаления.

Реализация:
Ниже приведена реализация процесса удаления на С ++.

/ * Следующая программа выполняет удаление на B-дереве. Содержит функции

   специально для удаления вместе со всеми другими функциями, предусмотренными в

   предыдущие статьи о B-деревьях. См. Https://www.geeksforgeeks.org/b-tree-set-1-introduction-2/.

   для предыдущей статьи.

  

   Функция удаления была разделена на 8 функций для простоты

   понимания и ясности

  

   Следующие функции являются исключительными для удаления

   В классе BTreeNode:

    1) удалить

    2) удалить из листа

    3) удалить из листа

    4) getPred

    5) getSucc

    6) loanFromPrev

    7) loanFromNext

    8) объединить

    9) findKey

  

   В классе BTree:

     1) удалить

  

  Удаление ключа из B-дерева - довольно сложный процесс. Программа обрабатывает

  все 6 разных случаев, которые могут возникнуть при удалении ключа.

  

  Тестирование: код был протестирован с использованием B-дерева, представленного в книге CLRS (в комплекте

  в основной функции) наряду с другими случаями.

  

  Ссылка: CLRS3 - Глава 18 - (499-502)

  Рекомендуется прочитать материал в CLRS, прежде чем взглянуть на код. * /

  
#include<iostream>

using namespace std;

  
// Узел BTree

class BTreeNode

{

    int *keys;  // Массив ключей

    int t;      // Минимальная степень (определяет диапазон для количества ключей)

    BTreeNode **C; // Массив дочерних указателей

    int n;     // Текущее количество ключей

    bool leaf; // Истинно, когда узел является листом. В противном случае ложь

  

public:

  

    BTreeNode(int _t, bool _leaf);   // Конструктор

  

    // Функция для прохождения всех узлов в поддереве с корнем из этого узла

    void traverse();

  

    // Функция для поиска ключа в поддереве с корнем из этого узла.

    BTreeNode *search(int k);   // возвращает NULL, если k отсутствует.

  

    // Функция, которая возвращает индекс первого ключа, который больше

    // или равно k

    int findKey(int k);

  

    // Полезная функция для вставки нового ключа в поддерево с корнем

    // этот узел Предполагается, что узел должен быть не заполнен, когда это

    // функция вызывается

    void insertNonFull(int k);

  

    // Вспомогательная функция для разделения дочернего элемента y этого узла. я индекс

    // из y в дочернем массиве C []. Ребенок должен быть полон, когда это

    // функция вызывается

    void splitChild(int i, BTreeNode *y);

  

    // Функция-обертка для удаления ключа k в поддереве с корнем

    // этот узел

    void remove(int k);

  

    // Функция для удаления ключа, присутствующего в idx-й позиции в

    // этот узел, который является листом

    void removeFromLeaf(int idx);

  

    // Функция для удаления ключа, присутствующего в idx-й позиции в

    // этот узел, который не является листовым узлом

    void removeFromNonLeaf(int idx);

  

    // Функция для получения предшественника ключа, где ключ

    // присутствует в idx-й позиции в узле

    int getPred(int idx);

  

    // Функция для получения преемника ключа, где ключ

    // присутствует в idx-й позиции в узле

    int getSucc(int idx);

  

    // Функция для заполнения дочернего узла, присутствующего в idx-ом

    // позиция в массиве C [], если у этого потомка меньше t-1 ключей

    void fill(int idx);

  

    // Функция для заимствования ключа из C [idx-1] -го узла и размещения

    // это в C [idx] -ом узле

    void borrowFromPrev(int idx);

  

    // Функция для заимствования ключа из C [idx + 1] -го узла и его помещения

    // в C [idx] -ом узле

    void borrowFromNext(int idx);

  

    // Функция для слияния idx-го потомка узла с (idx + 1) -ым потомком

    // узел

    void merge(int idx);

  

    // Подружитесь с BTree, чтобы мы могли получить доступ к закрытым членам

    // этот класс в функциях BTree

    friend class BTree;

};

  

class BTree

{

    BTreeNode *root; // Указатель на корневой узел

    int t;  // Минимальная степень

public:

  

    // Конструктор (Инициализирует дерево как пустое)

    BTree(int _t)

    {

        root = NULL;

        t = _t;

    }

  

    void traverse()

    {

        if (root != NULL) root->traverse();

    }

  

    // функция для поиска ключа в этом дереве

    BTreeNode* search(int k)

    {

        return (root == NULL)? NULL : root->search(k);

    }

  

    // Основная функция, которая вставляет новый ключ в это B-дерево

    void insert(int k);

  

    // Основная функция, которая удаляет новый ключ в B-Tree

    void remove(int k);

  
};

  

BTreeNode::BTreeNode(int t1, bool leaf1)

{

    // Копируем заданную минимальную степень и свойство листа

    t = t1;

    leaf = leaf1;

  

    // Распределяем память на максимальное количество возможных ключей

    // и дочерние указатели

    keys = new int[2*t-1];

    C = new BTreeNode *[2*t];

  

    // Инициализируем количество ключей как 0

    n = 0;

}

  
// Вспомогательная функция, которая возвращает индекс первого ключа, который
// больше или равно k

int BTreeNode::findKey(int k)

{

    int idx=0;

    while (idx<n && keys[idx] < k)

        ++idx;

    return idx;

}

  
// Функция для удаления ключа k из поддерева, укорененного в этом узле

void BTreeNode::remove(int k)

{

    int idx = findKey(k);

  

    // Ключ для удаления присутствует в этом узле

    if (idx < n && keys[idx] == k)

    {

  

        // Если узел является листовым узлом - вызывается removeFromLeaf

        // В противном случае вызывается функция removeFromNonLeaf

        if (leaf)

            removeFromLeaf(idx);

        else

            removeFromNonLeaf(idx);

    }

    else

    {

  

        // Если этот узел является листовым, то ключ отсутствует в дереве

        if (leaf)

        {

            cout << "The key "<< k <<" is does not exist in the tree\n";

            return;

        }

  

        // Ключ для удаления присутствует в поддереве с корнем этого узла

        // Флаг указывает, присутствует ли ключ в корне поддерева

        // с последним потомком этого узла

        bool flag = ( (idx==n)? true : false );

  

        // Если у дочернего элемента, где должен существовать ключ, меньше t ключей,

        // мы заполняем этого ребенка

        if (C[idx]->n < t)

            fill(idx);

  

        // Если последний дочерний элемент был объединен, он должен быть объединен с предыдущим

        // дочерний элемент и поэтому мы возвращаемся к (idx-1) -ому дочернему элементу. Остальное мы рекурсируем на

        // (idx) th потомок, который теперь имеет как минимум t ключей

        if (flag && idx > n)

            C[idx-1]->remove(k);

        else

            C[idx]->remove(k);

    }

    return;

}

  
// Функция для удаления ключа idx из этого узла, который является листовым узлом

void BTreeNode::removeFromLeaf (int idx)

{

  

    // Переместить все клавиши после idx-го на одно место назад

    for (int i=idx+1; i<n; ++i)

        keys[i-1] = keys[i];

  

    // Уменьшаем количество ключей

    n--;

  

    return;

}

  
// Функция для удаления ключа idx из этого узла, который является неконечным узлом

void BTreeNode::removeFromNonLeaf(int idx)

{

  

    int k = keys[idx];

  

    // Если дочерний элемент, предшествующий k (C [idx]), имеет по крайней мере t ключей,

    // найти предшественника 'pred' из k в поддереве с корнем в

    // C [idx]. Заменить k на пред. Рекурсивно удалить пред

    // в C [idx]

    if (C[idx]->n >= t)

    {

        int pred = getPred(idx);

        keys[idx] = pred;

        C[idx]->remove(pred);

    }

  

    // Если у дочернего элемента C [idx] меньше t ключей, исследуем C [idx + 1].

    // Если C [idx + 1] имеет по крайней мере t ключей, найдите преемника 'succ' из k в

    // поддерево с корнем в C [idx + 1]

    // Заменим k на succ

    // Рекурсивно удаляем succ в C [idx + 1]

    else if  (C[idx+1]->n >= t)

    {

        int succ = getSucc(idx);

        keys[idx] = succ;

        C[idx+1]->remove(succ);

    }

  

    // Если у обоих C [idx] и C [idx + 1] меньше t ключей, объединяем k и все из C [idx + 1]

    // в C [idx]

    // Теперь C [idx] содержит ключи 2t-1

    // Освободить C [idx + 1] и рекурсивно удалить k из C [idx]

    else

    {

        merge(idx);

        C[idx]->remove(k);

    }

    return;

}

  
// Функция для получения предшественника ключей [idx]

int BTreeNode::getPred(int idx)

{

    // Продолжаем двигаться к самому правому узлу, пока не достигнем листа

    BTreeNode *cur=C[idx];

    while (!cur->leaf)

        cur = cur->C[cur->n];

  

    // Возвращаем последний ключ листа

    return cur->keys[cur->n-1];

}

  

int BTreeNode::getSucc(int idx)

{

  

    // Продолжаем перемещать самый левый узел, начиная с C [idx + 1], пока не достигнем листа

    BTreeNode *cur = C[idx+1];

    while (!cur->leaf)

        cur = cur->C[0];

  

    // Возвращаем первый ключ листа

    return cur->keys[0];

}

  
// Функция для заполнения дочернего C [idx], которая имеет менее чем t-1 ключей

void BTreeNode::fill(int idx)

{

  

    // Если предыдущий дочерний элемент (C [idx-1]) имеет более чем t-1 ключей, заимствуйте ключ

    // от этого ребенка

    if (idx!=0 && C[idx-1]->n>=t)

        borrowFromPrev(idx);

  

    // Если следующий дочерний элемент (C [idx + 1]) имеет более чем t-1 ключей, заимствуйте ключ

    // от этого ребенка

    else if (idx!=n && C[idx+1]->n>=t)

        borrowFromNext(idx);

  

    // Слияние C [idx] с его родным братом

    // Если C [idx] является последним потомком, объединяем его с предыдущим братом

    // В противном случае объединить его со своим следующим братом

    else

    {

        if (idx != n)

            merge(idx);

        else

            merge(idx-1);

    }

    return;

}

  
// Функция для заимствования ключа из C [idx-1] и вставки его
// в C [idx]

void BTreeNode::borrowFromPrev(int idx)

{

  

    BTreeNode *child=C[idx];

    BTreeNode *sibling=C[idx-1];

  

    // Последний ключ из C [idx-1] переходит к родителю и ключу [idx-1]

    // из родительского элемента вставляется в качестве первого ключа в C [idx]. Таким образом, потери

    // брат одного ключа и ребенок получает один ключ

  

    // Перемещаем все ключи в C [idx] на шаг впереди

    for (int i=child->n-1; i>=0; --i)

        child->keys[i+1] = child->keys[i];

  

    // Если C [idx] не является листом, переместить все его дочерние указатели на один шаг вперед

    if (!child->leaf)

    {

        for(int i=child->n; i>=0; --i)

            child->C[i+1] = child->C[i];

    }

  

    // Установка первого ключа ребенка равным ключам [idx-1] от текущего узла

    child->keys[0] = keys[idx-1];

  

    // Перемещение последнего потомка брата как первого потомка C [idx]

    if(!child->leaf)

        child->C[0] = sibling->C[sibling->n];

  

    // Перемещение ключа от родного брата к родителю

    // Это уменьшает количество ключей в брате

    keys[idx-1] = sibling->keys[sibling->n-1];

  

    child->n += 1;

    sibling->n -= 1;

  

    return;

}

  
// Функция для заимствования ключа из C [idx + 1] и размещения
// это в C [idx]

void BTreeNode::borrowFromNext(int idx)

{

  

    BTreeNode *child=C[idx];

    BTreeNode *sibling=C[idx+1];

  

    // ключи [idx] вставляются как последний ключ в C [idx]

    child->keys[(child->n)] = keys[idx];

  

    // Первый дочерний элемент брата вставляется как последний дочерний элемент

    // в C [idx]

    if (!(child->leaf))

        child->C[(child->n)+1] = sibling->C[0];

  

    // Первый ключ от брата вставлен в keys [idx]

    keys[idx] = sibling->keys[0];

  

    // Перемещение всех ключей на одного брата на один шаг позади

    for (int i=1; i<sibling->n; ++i)

        sibling->keys[i-1] = sibling->keys[i];

  

    // Перемещение дочерних указателей на один шаг позади

    if (!sibling->leaf)

    {

        for(int i=1; i<=sibling->n; ++i)

            sibling->C[i-1] = sibling->C[i];

    }

  

    // Увеличиваем и уменьшаем количество ключей C [idx] и C [idx + 1]

    // соответственно

    child->n += 1;

    sibling->n -= 1;

  

    return;

}

  
// Функция для объединения C [idx] с C [idx + 1]
// C [idx + 1] освобождается после слияния

void BTreeNode::merge(int idx)

{

    BTreeNode *child = C[idx];

    BTreeNode *sibling = C[idx+1];

  

    // Вытащить ключ из текущего узла и вставить его в (t-1) -й

    // позиция C [idx]

    child->keys[t-1] = keys[idx];

  

    // Копирование ключей из C [idx + 1] в C [idx] в конце

    for (int i=0; i<sibling->n; ++i)

        child->keys[i+t] = sibling->keys[i];

  

    // Копируем дочерние указатели из C [idx + 1] в C [idx]

    if (!child->leaf)

    {

        for(int i=0; i<=sibling->n; ++i)

            child->C[i+t] = sibling->C[i];

    }

  

    // Перемещаем все ключи после idx в текущем узле на один шаг раньше -

    // чтобы заполнить пробел, созданный перемещением клавиш [idx] в C [idx]

    for (int i=idx+1; i<n; ++i)

        keys[i-1] = keys[i];

  

    // Перемещаем дочерние указатели после (idx + 1) в текущем узле

    // шаг перед

    for (int i=idx+2; i<=n; ++i)

        C[i-1] = C[i];

  

    // Обновление счетчика ключей дочернего и текущего узла

    child->n += sibling->n+1;

    n--;

  

    // Освобождаем память, занятую родным братом

    delete(sibling);

    return;

}

  
// Основная функция, которая вставляет новый ключ в это B-дерево

void BTree::insert(int k)

{

    // Если дерево пусто

    if (root == NULL)

    {

        // Выделим память для root

        root = new BTreeNode(t, true);

        root->keys[0] = k;  // Вставить ключ

        root->n = 1;  // Обновляем количество ключей в корне

    }

    else // Если дерево не пустое

    {

        // Если root полон, то дерево растет в высоту

        if (root->n == 2*t-1)

        {

            // Выделим память для нового корня

            BTreeNode *s = new BTreeNode(t, false);

  

            // Сделать старый корень дочерним для нового корня

            s->C[0] = root;

  

            // Разделить старый корень и переместить 1 ключ в новый корень

            s->splitChild(0, root);

  

            // Новый корень имеет двоих детей. Решите, какой из

            // у двух детей будет новый ключ

            int i = 0;

            if (s->keys[0] < k)

                i++;

            s->C[i]->insertNonFull(k);

  

            // Изменить корень

            root = s;

        }

        else  // Если root не заполнен, вызывать insertNonFull для root

            root->insertNonFull(k);

    }

}

  
// Вспомогательная функция для вставки нового ключа в этот узел
// Предполагается, что узел должен быть не полным
// функция вызывается

void BTreeNode::insertNonFull(int k)

{

    // Инициализировать индекс как индекс самого правого элемента

    int i = n-1;

  

    // Если это листовой узел

    if (leaf == true)

    {

        // Следующий цикл выполняет две вещи

        // а) Находит местоположение нового ключа для вставки

        // б) Перемещает все большие клавиши на одно место вперед

        while (i >= 0 && keys[i] > k)

        {

            keys[i+1] = keys[i];

            i--;

        }

  

        // Вставляем новый ключ в найденное место

        keys[i+1] = k;

        n = n+1;

    }

    else // Если этот узел не лист

    {

        // Найти ребенка, у которого будет новый ключ

        while (i >= 0 && keys[i] > k)

            i--;

  

        // Посмотрим, заполнен ли найденный ребенок

        if (C[i+1]->n == 2*t-1)

        {

            // Если ребенок полон, то разделить его

            splitChild(i+1, C[i+1]);

  

            // После разделения средняя клавиша C [i] поднимается и

            // C [i] разбивается на две части. Посмотрите, какой из двух

            // будет иметь новый ключ

            if (keys[i+1] < k)

                i++;

        }

        C[i+1]->insertNonFull(k);

    }

}

  
// Вспомогательная функция для разделения потомка y этого узла
// Обратите внимание, что y должен быть заполнен при вызове этой функции

void BTreeNode::splitChild(int i, BTreeNode *y)

{

    // Создать новый узел, который будет хранить (t-1) ключи

    // из у

    BTreeNode *z = new BTreeNode(y->t, y->leaf);

    z->n = t - 1;

  

    // Копируем последние (t-1) ключи y в z

    for (int j = 0; j < t-1; j++)

        z->keys[j] = y->keys[j+t];

  

    // Копируем последние t потомков y в z

    if (y->leaf == false)

    {

        for (int j = 0; j < t; j++)

            z->C[j] = y->C[j+t];

    }

  

    // Уменьшаем количество ключей в y

    y->n = t - 1;

  

    // Поскольку у этого узла будет новый дочерний элемент,

    // создаем пространство нового ребенка

    for (int j = n; j >= i+1; j--)

        C[j+1] = C[j];

  

    // Ссылка нового дочернего элемента на этот узел

    C[i+1] = z;

  

    // Ключ y переместится в этот узел. Найти местоположение

    // новый ключ и переместить все большие ключи на один пробел вперед

    for (int j = n-1; j >= i; j--)

        keys[j+1] = keys[j];

  

    // Копируем среднюю клавишу y в этот узел

    keys[i] = y->keys[t-1];

  

    // Увеличиваем количество ключей в этом узле

    n = n + 1;

}

  
// Функция для прохождения всех узлов в поддереве с корнем из этого узла

void BTreeNode::traverse()

{

    // есть n ключей и n + 1 потомков, обходы через n ключей

    // и первые n детей

    int i;

    for (i = 0; i < n; i++)

    {

        // Если это не лист, то перед печатью ключ [i],

        // пройти поддерево с корнем дочернего C [i].

        if (leaf == false)

            C[i]->traverse();

        cout << " " << keys[i];

    }

  

    // Распечатать поддерево с корнем из последнего потомка

    if (leaf == false)

        C[i]->traverse();

}

  
// Функция для поиска ключа k в поддереве с этим узлом

BTreeNode *BTreeNode::search(int k)

{

    // Находим первый ключ больше или равный k

    int i = 0;

    while (i < n && k > keys[i])

        i++;

  

    // Если найденный ключ равен k, вернуть этот узел

    if (keys[i] == k)

        return this;

  

    // Если ключ не найден здесь и это листовой узел

    if (leaf == true)

        return NULL;

  

    // Перейти к соответствующему ребенку

    return C[i]->search(k);

}

  

void BTree::remove(int k)

{

    if (!root)

    {

        cout << "The tree is empty\n";

        return;

    }

  

    // Вызываем функцию удаления для root

    root->remove(k);

  

    // Если корневой узел имеет 0 ключей, сделать его первым дочерним узлом новым корнем

    // если у него есть дочерний элемент, в противном случае установите корень как NULL

    if (root->n==0)

    {

        BTreeNode *tmp = root;

        if (root->leaf)

            root = NULL;

        else

            root = root->C[0];

  

        // Освободить старый корень

        delete tmp;

    }

    return;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    BTree t(3); // B-дерево с минимальной степенью 3

  

    t.insert(1);

    t.insert(3);

    t.insert(7);

    t.insert(10);

    t.insert(11);

    t.insert(13);

    t.insert(14);

    t.insert(15);

    t.insert(18);

    t.insert(16);

    t.insert(19);

    t.insert(24);

    t.insert(25);

    t.insert(26);

    t.insert(21);

    t.insert(4);

    t.insert(5);

    t.insert(20);

    t.insert(22);

    t.insert(2);

    t.insert(17);

    t.insert(12);

    t.insert(6);

  

    cout << "Traversal of tree constructed is\n";

    t.traverse();

    cout << endl;

  

    t.remove(6);

    cout << "Traversal of tree after removing 6\n";

    t.traverse();

    cout << endl;

  

    t.remove(13);

    cout << "Traversal of tree after removing 13\n";

    t.traverse();

    cout << endl;

  

    t.remove(7);

    cout << "Traversal of tree after removing 7\n";

    t.traverse();

    cout << endl;

  

    t.remove(4);

    cout << "Traversal of tree after removing 4\n";

    t.traverse();

    cout << endl;

  

    t.remove(2);

    cout << "Traversal of tree after removing 2\n";

    t.traverse();

    cout << endl;

  

    t.remove(16);

    cout << "Traversal of tree after removing 16\n";

    t.traverse();

    cout << endl;

  

    return 0;

}

Выход:

Traversal of tree constructed is
 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26
Traversal of tree after removing 6
 1 2 3 4 5 7 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26
Traversal of tree after removing 13
 1 2 3 4 5 7 10 11 12 14 15 16 17 18 19 20 21 22 24 25 26
Traversal of tree after removing 7
 1 2 3 4 5 10 11 12 14 15 16 17 18 19 20 21 22 24 25 26
Traversal of tree after removing 4
 1 2 3 5 10 11 12 14 15 16 17 18 19 20 21 22 24 25 26
Traversal of tree after removing 2
 1 3 5 10 11 12 14 15 16 17 18 19 20 21 22 24 25 26
Traversal of tree after removing 16
 1 3 5 10 11 12 14 15 17 18 19 20 21 22 24 25 26

Эта статья предоставлена Balasubramanian.N . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Операция удаления в B-Tree

0.00 (0%) 0 votes