Удалить операцию в B-дереве
Рекомендуется ссылаться на следующие сообщения как на предварительные условия этого сообщения.
B-Tree | Набор 1 (Введение)
B-Tree | Набор 2 (Вставка)
B-Tree - это разновидность многостороннего дерева поиска. Итак, если вы в целом не знакомы с многосторонними деревьями поиска, лучше взгляните на эту видеолекцию из IIT-Delhi, прежде чем продолжить. Как только вы разберетесь с основами многостороннего дерева поиска, операции B-дерева станут проще для понимания.
Источником следующего объяснения и алгоритма является Введение в алгоритмы 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).
Следующие рисунки поясняют процесс удаления.
Реализация:
Ниже приводится реализация процесса удаления на C ++.
/* The following program performs deletion on a B-Tree. It contains functions specific for deletion along with all the other functions provided in the previous articles on B-Trees. See https://www.geeksforgeeks.org/b-tree-set-1-introduction-2/ for previous article. The deletion function has been compartmentalized into 8 functions for ease of understanding and clarity The following functions are exclusive for deletion In class BTreeNode: 1) remove 2) removeFromLeaf 3) removeFromNonLeaf 4) getPred 5) getSucc 6) borrowFromPrev 7) borrowFromNext 8) merge 9) findKey In class BTree: 1) remove The removal of a key from a B-Tree is a fairly complicated process. The program handles all the 6 different cases that might arise while removing a key. Testing: The code has been tested using the B-Tree provided in the CLRS book( included in the main function ) along with other cases. Reference: CLRS3 - Chapter 18 - (499-502) It is advised to read the material in CLRS before taking a look at the code. */ #include<iostream>using namespace std; // A BTree nodeclass BTreeNode{ int *keys; // An array of keys int t; // Minimum degree (defines the range for number of keys) BTreeNode **C; // An array of child pointers int n; // Current number of keys bool leaf; // Is true when node is leaf. Otherwise false public : BTreeNode( int _t, bool _leaf); // Constructor // A function to traverse all nodes in a subtree rooted with this node void traverse(); // A function to search a key in subtree rooted with this node. BTreeNode *search( int k); // returns NULL if k is not present. // A function that returns the index of the first key that is greater // or equal to k int findKey( int k); // A utility function to insert a new key in the subtree rooted with // this node. The assumption is, the node must be non-full when this // function is called void insertNonFull( int k); // A utility function to split the child y of this node. i is index // of y in child array C[]. The Child y must be full when this // function is called void splitChild( int i, BTreeNode *y); // A wrapper function to remove the key k in subtree rooted with // this node. void remove ( int k); // A function to remove the key present in idx-th position in // this node which is a leaf void removeFromLeaf( int idx); // A function to remove the key present in idx-th position in // this node which is a non-leaf node void removeFromNonLeaf( int idx); // A function to get the predecessor of the key- where the key // is present in the idx-th position in the node int getPred( int idx); // A function to get the successor of the key- where the key // is present in the idx-th position in the node int getSucc( int idx); // A function to fill up the child node present in the idx-th // position in the C[] array if that child has less than t-1 keys fill( void int idx); // A function to borrow a key from the C[idx-1]-th node and place // it in C[idx]th node void borrowFromPrev( int idx); // A function to borrow a key from the C[idx+1]-th node and place it // in C[idx]th node void borrowFromNext( int idx); // A function to merge idx-th child of the node with (idx+1)th child of // the node void merge( int idx); // Make BTree friend of this so that we can access private members of // this class in BTree functions friend class BTree;}; class BTree{ BTreeNode *root; // Pointer to root node int t; // Minimum degreepublic : // Constructor (Initializes tree as empty) BTree( int _t) { root = NULL; t = _t; } void traverse() { if (root != NULL) root->traverse(); } // function to search a key in this tree BTreeNode* search( int k) { return (root == NULL)? NULL : root->search(k); } // The main function that inserts a new key in this B-Tree void insert( int k); // The main function that removes a new key in thie B-Tree void remove ( int k); }; BTreeNode::BTreeNode( int t1, bool leaf1){ // Copy the given minimum degree and leaf property t = t1; leaf = leaf1; // Allocate memory for maximum number of possible keys // and child pointers keys = new int [2*t-1]; C = new BTreeNode *[2*t]; // Initialize the number of keys as 0 n = 0;} // A utility function that returns the index of the first key that is// greater than or equal to kint BTreeNode::findKey( int k){ int idx=0; while (idx<n && keys[idx] < k) ++idx; return idx;} // A function to remove the key k from the sub-tree rooted with this nodevoid BTreeNode:: remove ( int k){ int idx = findKey(k); // The key to be removed is present in this node if (idx < n && keys[idx] == k) { // If the node is a leaf node - removeFromLeaf is called // Otherwise, removeFromNonLeaf function is called if (leaf) removeFromLeaf(idx); else removeFromNonLeaf(idx); } else { // If this node is a leaf node, then the key is not present in tree if (leaf) { cout << "The key " << k << " is does not exist in the tree
" ; return ; } // The key to be removed is present in the sub-tree rooted with this node // The flag indicates whether the key is present in the sub-tree rooted // with the last child of this node bool flag = ( (idx==n)? true : false ); // If the child where the key is supposed to exist has less that t keys, // we fill that child if (C[idx]->n < t) fill(idx); // If the last child has been merged, it must have merged with the previous // child and so we recurse on the (idx-1)th child. Else, we recurse on the // (idx)th child which now has atleast t keys if (flag && idx > n) C[idx-1]-> remove (k); else C[idx]-> remove (k); } return ;} // A function to remove the idx-th key from this node - which is a leaf nodevoid BTreeNode::removeFromLeaf ( int idx){ // Move all the keys after the idx-th pos one place backward for ( int i=idx+1; i<n; ++i) keys[i-1] = keys[i]; // Reduce the count of keys n--; return ;} // A function to remove the idx-th key from this node - which is a non-leaf nodevoid BTreeNode::removeFromNonLeaf( int idx){ int k = keys[idx]; // If the child that precedes k (C[idx]) has atleast t keys, // find the predecessor 'pred' of k in the subtree rooted at // C[idx]. Replace k by pred. Recursively delete pred // in C[idx] if (C[idx]->n >= t) { int pred = getPred(idx); keys[idx] = pred; C[idx]-> remove (pred); } // If the child C[idx] has less that t keys, examine C[idx+1]. // If C[idx+1] has atleast t keys, find the successor 'succ' of k in // the subtree rooted at C[idx+1] // Replace k by succ // Recursively delete succ in C[idx+1] else if (C[idx+1]->n >= t) { int succ = getSucc(idx); keys[idx] = succ; C[idx+1]-> remove (succ); } // If both C[idx] and C[idx+1] has less that t keys,merge k and all of C[idx+1] // into C[idx] // Now C[idx] contains 2t-1 keys // Free C[idx+1] and recursively delete k from C[idx] else { merge(idx); C[idx]-> remove (k); } return ;} // A function to get predecessor of keys[idx]int BTreeNode::getPred( int idx){ // Keep moving to the right most node until we reach a leaf BTreeNode *cur=C[idx]; while (!cur->leaf) cur = cur->C[cur->n]; // Return the last key of the leaf return cur->keys[cur->n-1];} int BTreeNode::getSucc( int idx){ // Keep moving the left most node starting from C[idx+1] until we reach a leaf BTreeNode *cur = C[idx+1]; while (!cur->leaf) cur = cur->C[0]; // Return the first key of the leaf return cur->keys[0];} // A function to fill child C[idx] which has less than t-1 keysvoid BTreeNode::fill( int idx){ // If the previous child(C[idx-1]) has more than t-1 keys, borrow a key // from that child if (idx!=0 && C[idx-1]->n>=t) borrowFromPrev(idx); // If the next child(C[idx+1]) has more than t-1 keys, borrow a key // from that child else if (idx!=n && C[idx+1]->n>=t) borrowFromNext(idx); // Merge C[idx] with its sibling // If C[idx] is the last child, merge it with with its previous sibling // Otherwise merge it with its next sibling else { if (idx != n) merge(idx); else merge(idx-1); } return ;} // A function to borrow a key from C[idx-1] and insert it// into C[idx]void BTreeNode::borrowFromPrev( int idx){ BTreeNode *child=C[idx]; BTreeNode *sibling=C[idx-1]; // The last key from C[idx-1] goes up to the parent and key[idx-1] // from parent is inserted as the first key in C[idx]. Thus, the loses // sibling one key and child gains one key // Moving all key in C[idx] one step ahead for ( int i=child->n-1; i>=0; --i) child->keys[i+1] = child->keys[i]; // If C[idx] is not a leaf, move all its child pointers one step ahead if (!child->leaf) { for ( int i=child->n; i>=0; --i) child->C[i+1] = child->C[i]; } // Setting child's first key equal to keys[idx-1] from the current node child->keys[0] = keys[idx-1]; // Moving sibling's last child as C[idx]'s first child if (!child->leaf) child->C[0] = sibling->C[sibling->n]; // Moving the key from the sibling to the parent // This reduces the number of keys in the sibling keys[idx-1] = sibling->keys[sibling->n-1]; child->n += 1; sibling->n -= 1; return ;} // A function to borrow a key from the C[idx+1] and place// it in C[idx]void BTreeNode::borrowFromNext( int idx){ BTreeNode *child=C[idx]; BTreeNode *sibling=C[idx+1]; // keys[idx] is inserted as the last key in C[idx] child->keys[(child->n)] = keys[idx]; // Sibling's first child is inserted as the last child // into C[idx] if (!(child->leaf)) child->C[(child->n)+1] = sibling->C[0]; //The first key from sibling is inserted into keys[idx] keys[idx] = sibling->keys[0]; // Moving all keys in sibling one step behind for ( int i=1; i<sibling->n; ++i) sibling->keys[i-1] = sibling->keys[i]; // Moving the child pointers one step behind if (!sibling->leaf) { for ( int i=1; i<=sibling->n; ++i)РЕКОМЕНДУЕМЫЕ СТАТЬИ |