Рубрики

Операция вставки в B-Tree

В предыдущем посте мы представили B-Tree. Мы также обсудили функции search () и traverse ().
В этом посте обсуждается операция insert (). Новый ключ всегда вставляется в конечный узел. Пусть ключ для вставки будет k. Как и BST, мы начинаем с корня и движемся вниз до конечного узла. Как только мы достигаем конечного узла, мы вставляем ключ в этот конечный узел. В отличие от BST, у нас есть предопределенный диапазон количества ключей, которые может содержать узел. Поэтому, прежде чем вставлять ключ в узел, мы должны убедиться, что на узле есть дополнительное пространство.
Как убедиться, что у узла есть место, доступное для ключа, до того, как ключ вставлен? Мы используем операцию под названием splitChild (), которая используется для разделения дочернего узла. Смотрите следующую диаграмму, чтобы понять разделение. На следующей диаграмме дочерний элемент y из x разбивается на два узла y и z. Обратите внимание, что операция splitChild перемещает ключ вверх, и это является причиной роста B-деревьев, в отличие от BST, которые уменьшаются.

Как уже говорилось выше, чтобы вставить новый ключ, мы переходим от корня к листу. Прежде чем перейти к узлу, мы сначала проверяем, заполнен ли узел. Если узел заполнен, мы разделяем его, чтобы создать пространство. Ниже приводится полный алгоритм.

вставка
1) Инициализируйте x как root.
2) Пока х не лист, сделайте следующее
.. а) Найдите потомка х, который будет проходить дальше. Пусть ребенок будет у.
.. б) Если у не полный, измените х, чтобы указать на у.
.. в) Если y заполнен, разделите его и измените x, чтобы указать на одну из двух частей y. Если k меньше середины ключа в y, тогда установите x в качестве первой части y. Еще вторая часть у. Когда мы разделяем y, мы перемещаем ключ от y к его родительскому x.
3) Цикл в шаге 2 останавливается, когда x является листом. У x должно быть место для 1 дополнительного ключа, так как мы предварительно разбили все узлы. Так что просто вставьте к х.

Обратите внимание, что алгоритм следует книге Кормена. На самом деле это проактивный алгоритм вставки, в котором перед тем, как перейти к узлу, мы разделяем его, если он заполнен. Преимущество разделения перед тем, что мы никогда не пересекаем узел дважды. Если мы не разделим узел перед тем, как перейти к нему, и разделим его только в том случае, если вставлен новый ключ (реактивный), мы можем в конечном итоге пересечь все узлы снова от листа к корню. Это происходит в тех случаях, когда все узлы на пути от корня до листа заполнены. Поэтому, когда мы подходим к конечному узлу, мы разделяем его и перемещаем ключ вверх. Перемещение ключа вверх вызовет разделение в родительском узле (потому что родительский уже был заполнен). Этот каскадный эффект никогда не происходит в этом проактивном алгоритме вставки. Недостаток этой упреждающей вставки, однако, может заключаться в ненужных разбиениях.

Давайте разберем алгоритм с примером дерева минимальной степени 't' как 3 и последовательностью целых чисел 10, 20, 30, 40, 50, 60, 70, 80 и 90 в первоначально пустом B-дереве.

Изначально root имеет значение NULL. Давайте сначала вставим 10.

Теперь давайте вставим 20, 30, 40 и 50. Все они будут вставлены в корень, потому что максимальное количество ключей, которое может вместить узел, равно 2 * t — 1, что равно 5.

Теперь давайте вставим 60. Поскольку корневой узел заполнен, он сначала разделится на два, а затем 60 будет вставлен в соответствующий дочерний узел.

Давайте теперь вставим 70 и 80. Эти новые ключи будут вставлены в соответствующий лист без разделения.

Давайте теперь вставим 90. Эта вставка вызовет разделение. Средний ключ перейдет к родителю.

Ниже приводится реализация вышеупомянутого проактивного алгоритма на C ++.

// C ++ программа для вставки B-Tree
#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 insertNonFull(int k);

  

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

    // дочерний массив C []. Child y должен быть заполнен при вызове этой функции

    void splitChild(int i, BTreeNode *y);

  

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

    void traverse();

  

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

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

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

friend class BTree;

};

  
// Bree

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);

};

  
// Конструктор для класса BTreeNode

BTreeNode::BTreeNode(int t1, bool leaf1)

{

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

    t = t1;

    leaf = leaf1;

  

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

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

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

    C = new BTreeNode *[2*t];

  

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

    n = 0;

}

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

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);

}

  
// Основная функция, которая вставляет новый ключ в это 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;

}

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

int main()

{

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

    t.insert(10);

    t.insert(20);

    t.insert(5);

    t.insert(6);

    t.insert(12);

    t.insert(30);

    t.insert(7);

    t.insert(17);

  

    cout << "Traversal of the constucted tree is ";

    t.traverse();

  

    int k = 6;

    (t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";

  

    k = 15;

    (t.search(k) != NULL)? cout << "\nPresent" : cout << "\nNot Present";

  

    return 0;

}

Выход:

Traversal of the constucted tree is  5 6 7 10 12 17 20 30
Present
Not Present

Ссылки:
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест
http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture17.html

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

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

Операция вставки в B-Tree

0.00 (0%) 0 votes