Question

The records are insSerted Hl 6. A B tree: You are given a series of records whose keys are letters. the following order: C,S,D,T.A,M,PI,B,W,N,G,U,R,K,E,H. Show the B+ tree of order 4 that results from inserting these records. Assume that the leaf nodes are capable of storing up to 3 records.

write the c++ code.

Answer 1

Ans the following binary tree is the solution for the given records

N

D

H

K

S

                                                       

T

U

W

P

R

M

I

E

G

A

B

C

#include<iostream>

using namespace std;

class BTNode

{

    int *keys; // An array of keys

    int t;      // Minimum degree (defines the range for number of keys)

    BTNode **C; // An array of child pointers

    int n;     // Current number of keys

    bool leaf; // Is true when node is leaf. Otherwise false

public:

    BTNode(int _t, bool _leaf);  

  void insNonFull(int k);

  void split(int i, BTNode *y);

void trav();

BTNode *srch(int k);  

friend class BTree;

};

  

class BTree

{

    BTNode *root; // Pointer to root node

    int t; // Minimum degree

public:

    BTree(int _t)

    {

root = NULL; t = _t;

}

    void trav()

    {

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

}

    BTNode* srch(int k)

    {

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

}

  

void ins(int k);

};

  

BTNode::BTNode(int t1, bool leaf1)

{

    t = t1;

    leaf = leaf1;

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

    C = new BTNode *[2*t];

    n = 0;

}

void BTNode::trav()

{

    int i;

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

    {

        if (leaf == false)

            C[i]->trav();

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

    }

  

    if (leaf == false)

        C[i]->trav();

}

BTNode *BTNode::srch(int k)

{

    int i = 0;

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

        i++;

  

    if (keys[i] == k)

        return this;

  

    if (leaf == true)

        return NULL;

  

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

}

  

void BTree::ins(int k)

{

    if (root == NULL)

    {

        root = new BTNode(t, true);

        root->keys[0] = k; // Ins key

        root->n = 1; // Update number of keys in root

    }

    else // If tree is not empty

    {

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

        {

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

  

            s->C[0] = root;

            s->split(0, root);

            int i = 0;

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

                i++;

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

  

            // Change root

            root = s;

        }

        else

            root->insNonFull(k);

    }

}

void BTNode::insNonFull(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)

        {

            // If the child is full, then split it

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

if (keys[i+1] < k)

                i++;

        }

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

    }

}

void BTNode::split(int i, BTNode *y)

{

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

    z->n = t - 1;

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

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

    if (y->leaf == false)

    {

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

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

    }

  

    y->n = t - 1;

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

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

    C[i+1] = z;

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

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

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

    n = n + 1;

}                  

  

int main()

{

    BTree t(4); // A B-Tree with minium degree 4

    t.ins(10);

    t.ins(20);

    t.ins(5);

    t.ins(6);

    t.ins(12);

    t.ins(30);

    t.ins(7);

    t.ins(17);

  

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

    t.trav();

  

    int k = 6;

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

  

    k = 15;

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

  

    return 0;

}

t.ins(7);

    t.ins(17);

  

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

    t.trav();

  

    int k = 6;

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

  

    k = 15;

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

  

    return 0;

}