Вставка в дерево B +
Предпосылка: Введение деревьев B +
В этой статье мы обсудим, как вставить узел в B + Tree. При вставке необходимо соблюдать следующие свойства B + Tree:
- Каждый узел, кроме корневого, может иметь не более M дочерних узлов и не менее ceil (M / 2) дочерних узлов.
- Каждый узел может содержать максимум M - 1 ключей и минимум ceil (M / 2) - 1 ключей.
- У корня есть как минимум два потомка и как минимум один ключ поиска.
- При вставке переполнение узла происходит, когда он содержит более M - 1 значений ключа поиска.
Здесь M - порядок дерева B +.
Шаги для вставки в B + Tree
- Каждый элемент вставляется в листовой узел. Итак, переходим к соответствующему листу узла.
- Вставьте ключ в листовой узел в порядке возрастания, только если нет переполнения. В случае переполнения выполните следующие шаги, упомянутые ниже, чтобы справиться с переполнением при сохранении свойств B + Tree.
Свойства для вставки B + Tree
Случай 1: переполнение в листовом узле
- Разделите листовой узел на два узла.
- Первый узел содержит значения ceil ((m-1) / 2) .
- Второй узел содержит остальные значения.
- Скопируйте наименьшее значение ключа поиска со второго узла в родительский узел (со смещением вправо)
Ниже приведена иллюстрация вставки 8 в B + Tree порядка 5:
Случай 2: переполнение в нелистовом узле
- Разделите нелистовой узел на два узла.
- Первый узел содержит значения ceil (m / 2) -1.
- Переместите наименьшее из оставшихся к родителю.
- Второй узел содержит оставшиеся ключи.
Ниже приведена иллюстрация вставки 15 в дерево B + порядка 5:
Пример для иллюстрации вставки в дерево B +
Проблема: вставьте следующие ключевые значения 6, 16, 26, 36, 46 в дерево B + с порядком = 3.
Решение:
Шаг 1. Порядок равен 3, то есть максимум в узле, поэтому может быть только 2 значения ключа поиска. Поскольку вставка происходит на листовом узле только в дереве B +, вставляйте значения ключа поиска 6 и 16 в узел в порядке возрастания. Ниже приведена иллюстрация того же:
Шаг 2: Мы не можем вставить 26 в тот же узел, так как это вызывает переполнение в листовом узле. Мы должны разделить листовой узел в соответствии с правилами. Первая часть содержит значения ceil ((3-1) / 2), т.е. только 6 . Второй узел содержит оставшиеся значения, то есть 16 и 26 . Затем также скопируйте наименьшее значение ключа поиска из второго узла в родительский узел, т. Е. 16, в родительский узел. Ниже приведена иллюстрация того же:
Шаг 3: Теперь следующее значение - 36 , которое должно быть вставлено после 26, но в этом узле это снова вызывает переполнение в этом листовом узле. Снова выполните описанные выше шаги, чтобы разделить узел. Первая часть содержит значения ceil ((3-1) / 2), т.е. только 16 . Второй узел содержит оставшиеся значения, то есть 26 и 36 . Затем также скопируйте наименьшее значение ключа поиска из второго узла в родительский узел, т. Е. 26, в родительский узел. Ниже приведена иллюстрация того же:
Иллюстрация представлена на схеме ниже.
Шаг 4: Теперь нам нужно вставить 46, который должен быть вставлен после 36, но это вызывает переполнение в листовом узле. Итак, мы разбиваем узел по правилам. Первая часть содержит 26, а вторая часть содержит 36 и 46, но теперь мы также должны скопировать 36 в родительский узел, но это вызывает переполнение, поскольку в узле могут быть размещены только два значения ключа поиска. Теперь выполните шаги, чтобы справиться с переполнением в нелистовом узле.
Первый узел содержит значения ceil (3/2) -1, то есть «16».
Переместите наименьший из оставшихся к родительскому узлу, т.е. «26» будет новым родительским узлом.
Второй узел содержит оставшиеся ключи, т.е. «36», а остальные листовые узлы остаются прежними. Ниже приведена иллюстрация того же:
Below is the implementation of insertion in the B+ tree:
C++
// C++ program for implementing B+ Tree #include <climits> #include <fstream> #include <iostream> #include <sstream> using namespace std; int MAX = 3; // BP node class Node { bool IS_LEAF; int *key, size; Node** ptr; friend class BPTree; public : Node(); }; // BP tree class BPTree { Node* root; void insertInternal( int , Node*, Node*); Node* findParent(Node*, Node*); public : BPTree(); void search( int ); void insert( int ); void display(Node*); Node* getRoot(); }; // Constructor of Node Node::Node() { key = new int [MAX]; ptr = new Node*[MAX + 1]; } // Initialise the BPTree Node BPTree::BPTree() { root = NULL; } // Function to find any element // in B+ Tree void BPTree::search( int x) { // If tree is empty if (root == NULL) { cout << "Tree is empty
" ; } // Traverse to find the value else { Node* cursor = root; // Till we reach leaf node while (cursor->IS_LEAF == false ) { for ( int i = 0; i < cursor->size; i++) { // If the element to be // found is not present if (x < cursor->key[i]) { cursor = cursor->ptr[i]; break ; } // If reaches end of the // cursor node if (i == cursor->size - 1) { cursor = cursor->ptr[i + 1]; break ; } } } // Traverse the cursor and find // the node with value x for ( int i = 0; i < cursor->size; i++) { // If found then return if (cursor->key[i] == x) { cout << "Found
" ; return ; } } // Else element is not present cout << "Not found
" ; } } // Function to implement the Insert // Operation in B+ Tree void BPTree::insert( int x) { // If root is null then return // newly created node if (root == NULL) { root = new Node; root->key[0] = x; root->IS_LEAF = true ; root->size = 1; } // Traverse the B+ Tree else { Node* cursor = root; Node* parent; // Till cursor reaches the // leaf node while (cursor->IS_LEAF == false ) { parent = cursor; for ( int i = 0; i < cursor->size; i++) { // If found the position // where we have to insert // node if (x < cursor->key[i]) { cursor = cursor->ptr[i]; break ; } // If reaches the end if (i == cursor->size - 1) { cursor = cursor->ptr[i + 1]; break ; } } } if (cursor->size < MAX) { int i = 0; while (x > cursor->key[i] && i < cursor->size) { i++; } for ( int j = cursor->size; j > i; j--) { cursor->key[j] = cursor->key[j - 1]; } cursor->key[i] = x; cursor->size++; cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1]; cursor->ptr[cursor->size - 1] = NULL; } else { // Create a newLeaf node Node* newLeaf = new Node; int virtualNode[MAX + 1]; // Update cursor to virtual // node created for ( int i = 0; i < MAX; i++) { virtualNode[i] = cursor->key[i]; } int i = 0, j; // Traverse to find where the new // node is to be inserted while (x > virtualNode[i] && i < MAX) { i++; } // Update the current virtual // Node to its previous for ( int j = MAX + 1; j > i; j--) { virtualNode[j] = virtualNode[j - 1]; } virtualNode[i] = x; newLeaf->IS_LEAF = true ; cursor->size = (MAX + 1) / 2; newLeaf->size = MAX + 1 - (MAX + 1) / 2; cursor->ptr[cursor->size] = newLeaf; newLeaf->ptr[newLeaf->size] = cursor->ptr[MAX]; cursor->ptr[MAX] = NULL; // Update the current virtual // Node"s key to its previous for (i = 0; i < cursor->size; i++) { cursor->key[i] = virtualNode[i]; } // Update the newLeaf key to // virtual Node for (i = 0, j = cursor->size; i < newLeaf->size; i++, j++) { newLeaf->key[i] = virtualNode[j]; } // If cursor is the root node if (cursor == root) { // Create a new Node Node* newRoot = new Node; // Update rest field of // B+ Tree Node newRoot->key[0] = newLeaf->key[0]; newRoot->ptr[0] = cursor; newRoot->ptr[1] = newLeaf; newRoot->IS_LEAF = false ; newRoot->size = 1; root = newRoot; } else { // Recursive Call for // insert in internal insertInternal(newLeaf->key[0], parent, newLeaf); } } } } // Function to implement the Insert // Internal Operation in B+ Tree void BPTree::insertInternal( int x, Node* cursor, Node* child) { // If we doesn"t have overflow if (cursor->size < MAX) { int i = 0; // Traverse the child node // for current cursor node while (x > cursor->key[i] && i < cursor->size) { i++; } // Traverse the cursor node // and update the current key // to its previous node key for ( int j = cursor->size; j > i; j--) { cursor->key[j] = cursor->key[j - 1]; } // Traverse the cursor node // and update the current ptr // to its previous node ptr for ( int j = cursor->size + 1; j > i + 1; j--) { cursor->ptr[j] = cursor->ptr[j - 1]; } cursor->key[i] = x; cursor->size++; cursor->ptr[i + 1] = child; } // For overflow, break the node else { // For new Interval Node* newInternal = new Node; int virtualKey[MAX + 1]; Node* virtualPtr[MAX + 2]; // Insert the current list key // of cursor node to virtualKey for ( int i = 0; i < MAX; i++) { virtualKey[i] = cursor->key[i]; } // Insert the current list ptr // of cursor node to virtualPtr for ( int i = 0; i < MAX + 1; i++) { virtualPtr[i] = cursor->ptr[i]; РЕКОМЕНДУЕМЫЕ СТАТЬИ |