Inserto B-Tree sin divisiones agresivas

B-Tree Insert sin división agresiva
Este algoritmo de inserción toma una entrada, encuentra el Node hoja al que pertenece y lo inserta allí. Insertamos recursivamente la entrada llamando al algoritmo de inserción en el Node secundario apropiado. Este procedimiento da como resultado bajar al Node de hoja al que pertenece la entrada, colocar la entrada allí y regresar al Node raíz. 
A veces, un Node está lleno, es decir, contiene 2*t – 1 entradas donde t es el grado mínimo. En tales casos, el Node debe dividirse. En tal caso, una clave se convierte en principal y se crea un nuevo Node. Primero insertamos la nueva clave, haciendo un total de claves como 2*t. Mantenemos las primeras t entradas en el Node original, transferimos las últimas (t-1) entradas al nuevo Node y establecemos el (t+1)-ésimo Node como padre de estos Nodes. Si el Node que se está dividiendo no es un Node secundario, también tenemos que dividir los punteros secundarios. Un Node que tiene claves 2*t tiene 2*t + 1 punteros secundarios. Los primeros punteros (t+1) se mantienen en el Node original y los t punteros restantes van al nuevo Node.
 

Este algoritmo divide un Node solo cuando es necesario. Primero llamamos recursivamente a insert para el hijo apropiado del Node (en el caso de un Node que no sea hoja) o lo insertamos en el Node (para el Node hoja). Si el Node está lleno, lo dividimos, almacenando la nueva entrada secundaria en newEntry y la nueva clave principal en val. Estos valores luego se insertan en el padre, que recursivamente se divide en caso de que también esté lleno.
Ejemplo:
Insertamos los números 1 – 5 en el árbol. El árbol se convierte en: 
 

Luego insertamos 6, el Node está lleno. Por lo tanto, se divide en dos Nodes haciendo 4 como padre. 
 

Insertamos los números 7 – 16, el árbol se convierte en:
 

Insertamos 22 – 30, el árbol se convierte en:
 

Tenga en cuenta que ahora la raíz está llena. Si insertamos 17 ahora, la raíz no se divide ya que el Node hoja en el que se insertó 17 no se dividió. Si estuviéramos siguiendo una división agresiva, la raíz se habría dividido antes de pasar al Node hoja.
 

Pero si insertamos 31, el Node hoja se divide, lo que recursivamente agrega una nueva entrada a la raíz. Pero como la raíz está llena, debe dividirse. El árbol ahora se convierte.
 

 

A continuación se muestra la implementación del enfoque anterior:
 

CPP

// C++ implementation of the approach
#include <iostream>
#include <vector>
using namespace std;
 
class BTreeNode {
 
    // Vector of keys
    vector<int> keys;
 
    // Minimum degree
    int t;
 
    // Vector of child pointers
    vector<BTreeNode*> C;
 
    // Is true when node is leaf, else false
    bool leaf;
 
public:
    // Constructor
    BTreeNode(int t, bool leaf);
 
    // Traversing the node and print its content
    // with tab number of tabs before
    void traverse(int tab);
 
    // Insert key into given node. If child is split, we
    // have to insert *val entry into keys vector and
    // newEntry pointer into C vector of this node
    void insert(int key, int* val,
                BTreeNode*& newEntry);
 
    // Split this node and store the new parent value in
    // *val and new node pointer in newEntry
    void split(int* val, BTreeNode*& newEntry);
 
    // Returns true if node is full
    bool isFull();
 
    // Makes new root, setting current root as its child
    BTreeNode* makeNewRoot(int val, BTreeNode* newEntry);
};
 
bool BTreeNode::isFull()
{
    // returns true if node is full
    return (this->keys.size() == 2 * t - 1);
}
 
BTreeNode::BTreeNode(int t, bool leaf)
{
    // Constructor to set value of t and leaf
    this->t = t;
    this->leaf = leaf;
}
 
// Function to print the nodes of B-Tree
void BTreeNode::traverse(int tab)
{
    int i;
    string s;
 
    // Print 'tab' number of tabs
    for (int j = 0; j < tab; j++) {
        s += '\t';
    }
    for (i = 0; i < keys.size(); i++) {
 
        // If this is not leaf, then before printing key[i]
        // traverse the subtree rooted with child C[i]
        if (leaf == false)
            C[i]->traverse(tab + 1);
        cout << s << keys[i] << endl;
    }
 
    // Print the subtree rooted with last child
    if (leaf == false) {
        C[i]->traverse(tab + 1);
    }
}
 
// Function to split the current node and store the new
// parent value is *val and new child pointer in &newEntry
// called only for splitting non-leaf node
void BTreeNode::split(int* val, BTreeNode*& newEntry)
{
 
    // Create new non leaf node
    newEntry = new BTreeNode(t, false);
 
    //(t+1)th becomes parent
    *val = this->keys[t];
 
    // Last (t-1) entries will go to new node
    for (int i = t + 1; i < 2 * t; i++) {
        newEntry->keys.push_back(this->keys[i]);
    }
 
    // This node stores first t entries
    this->keys.resize(t);
 
    // Last t entries will go to new node
    for (int i = t + 1; i <= 2 * t; i++) {
        newEntry->C.push_back(this->C[i]);
    }
 
    // This node stores first (t+1) entries
    this->C.resize(t + 1);
}
 
// Function to insert a new key in given node.
// If child of this node is split, we have to insert *val
// into keys vector and newEntry pointer into C vector
void BTreeNode::insert(int new_key, int* val,
                       BTreeNode*& newEntry)
{
 
    // Non leaf node
    if (leaf == false) {
        int i = 0;
 
        // Find first key greater than new_key
        while (i < keys.size() && new_key > keys[i])
            i++;
 
        // We have to insert new_key into left child of
        // Node with index i
        C[i]->insert(new_key, val, newEntry);
 
        // No split was done
        if (newEntry == NULL)
            return;
        if (keys.size() < 2 * t - 1) {
 
            // This node can accommodate a new key
            // and child pointer entry
            // Insert *val into key vector
            keys.insert(keys.begin() + i, *val);
 
            // Insert newEntry into C vector
            C.insert(C.begin() + i + 1, newEntry);
 
            // As this node was not split, set newEntry
            // to NULL
            newEntry = NULL;
        }
        else {
 
            // Insert *val and newentry
            keys.insert(keys.begin() + i, *val);
            C.insert(C.begin() + i + 1, newEntry);
 
            // Current node has 2*t keys, so split it
            split(val, newEntry);
        }
    }
    else {
 
        // Insert new_key in this node
        vector<int>::iterator it;
 
        // Find correct position
        it = lower_bound(keys.begin(), keys.end(),
                         new_key);
 
        // Insert in correct position
        keys.insert(it, new_key);
 
        // If node is full
        if (keys.size() == 2 * t) {
 
            // Create new node
            newEntry = new BTreeNode(t, true);
 
            // Set (t+1)th key as parent
            *val = this->keys[t];
 
            // Insert last (t-1) keys into new node
            for (int i = t + 1; i < 2 * t; i++) {
                newEntry->keys.push_back(this->keys[i]);
            }
 
            // This node stores first t keys
            this->keys.resize(t);
        }
    }
}
 
// Function to create a new root
// setting current node as its child
BTreeNode* BTreeNode::makeNewRoot(int val, BTreeNode* newEntry)
{
    // Create new root
    BTreeNode* root = new BTreeNode(t, false);
 
    // Stores keys value
    root->keys.push_back(val);
 
    // Push child pointers
    root->C.push_back(this);
    root->C.push_back(newEntry);
    return root;
}
 
class BTree {
 
    // Root of B-Tree
    BTreeNode* root;
 
    // Minimum degree
    int t;
 
public:
    // Constructor
    BTree(int t);
 
    // Insert key
    void insert(int key);
 
    // Display the tree
    void display();
};
 
// Function to create a new BTree with
// minimum degree t
BTree::BTree(int t)
{
    root = new BTreeNode(t, true);
}
 
// Function to insert a node in the B-Tree
void BTree::insert(int key)
{
    BTreeNode* newEntry = NULL;
    int val = 0;
 
    // Insert in B-Tree
    root->insert(key, &val, newEntry);
 
    // If newEntry is not Null then root needs to be
    // split. Create new root
    if (newEntry != NULL) {
        root = root->makeNewRoot(val, newEntry);
    }
}
 
// Prints BTree
void BTree::display()
{
    root->traverse(0);
}
 
// Driver code
int main()
{
 
    // Create B-Tree
    BTree* tree = new BTree(3);
    cout << "After inserting 1 and 2" << endl;
    tree->insert(1);
    tree->insert(2);
    tree->display();
 
    cout << "After inserting 5 and 6" << endl;
    tree->insert(5);
    tree->insert(6);
    tree->display();
 
    cout << "After inserting 3 and 4" << endl;
    tree->insert(3);
    tree->insert(4);
    tree->display();
 
    return 0;
}
Producción: 

After inserting 1 and 2
1
2
After inserting 5 and 6
1
2
5
6
After inserting 3 and 4
    1
    2
    3
4
    5
    6

 

Publicación traducida automáticamente

Artículo escrito por ashveenbansal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *