. Write a method that traverses a B-tree. The traversal starts from the root. Fo

Question

. Write a method that traverses a B-tree. The traversal starts from the root. For every B-tree node, it processes every record/key in the node in order and then traverses each child of the node in order. (12 pts) Note: The method should be written based on the B-tree implementation presented in the lecture notes. Hint: Write a recursive method that processes the records and traverses the children of the current node based on the following order: datal0] datal11 data[count-11 - branchl0] branchll].. branchlcount]

Explanation / Answer

//B_Tree

#include<iostream>

using namespace std;

// node for btree

class Node

{

int *nodeKeys; // keys array

int t; // min degree

Node **C; // child pointer array

int n; // current number keys array

bool leaf; // to check weather leaf is empty of not

public:

Node(int _t, bool _leaf); // Constructor

//insert function for non full node

void insertNodeForNonFull(int k);

//function for split

void splitChildNode(int i, Node *y);

//function for traverse tree

void traverseTree();

friend class B_Tree;

};

class B_Tree

{

Node *root;

int t;

public:

// Constructor

B_Tree(int _t)

{ root = NULL; t = _t; }

// traverseTree the tree

void traverseTree()

{ if (root != NULL) root->traverseTree(); }

// TinsertNodes

void insertNode(int k);

};

// Constructor

Node::Node(int t1, bool leaf1)

{

// minimum degree=leaf property

t = t1;

leaf = leaf1;

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

C = new Node *[2*t];

// nodeKeys as 0

n = 0;

}

// Function to traverseTree

void Node::traverseTree()

{

  

int i;

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

{

if (leaf == false)

C[i]->traverseTree();

cout << " " << nodeKeys[i];

}

// Print the suB_Tree

if (leaf == false)

C[i]->traverseTree();

}

// function that insertNodes

void B_Tree::insertNode(int k)

{

if (root == NULL)

{

  

root = new Node(t, true);

root->nodeKeys[0] = k;  

root->n = 1;

}

else // If tree is not empty

{

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

{

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

  

s->C[0] = root;

  

s->splitChildNode(0, root);

int i = 0;

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

i++;

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

root = s;

}

else // If root is not full,

root->insertNodeForNonFull(k);

}

}

// insertNode non-full

void Node::insertNodeForNonFull(int k)

{

  

int i = n-1;

// If this is a leaf node

if (leaf == true)

{

while (i >= 0 && nodeKeys[i] > k)

{

nodeKeys[i+1] = nodeKeys[i];

i--;

}

  

nodeKeys[i+1] = k;

n = n+1;

}

else

{

while (i >= 0 && nodeKeys[i] > k)

i--;

  

if (C[i+1]->n == 2*t-1)

{

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

if (nodeKeys[i+1] < k)

i++;

}

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

}

}

void Node::splitChildNode(int i, Node *y)

{

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

z->n = t - 1;

// Copy the last

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

z->nodeKeys[j] = y->nodeKeys[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--)

nodeKeys[j+1] = nodeKeys[j];

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

n = n + 1;

}

// Driver program

int main()

{

B_Tree t(3); // A B_Tree with minium degree 3

t.insertNode(10);

t.insertNode(20);

t.insertNode(5);

t.insertNode(6);

t.insertNode(12);

t.insertNode(30);

t.insertNode(7);

t.insertNode(17);

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

t.traverseTree();

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.