Answer Happy

////////////////////////////////////BTree.java////////////////////////////////////////
class BTree<T extends Comparable<T>> {
BTreeNode<T> root; // Pointer to root
node
int m; // B-Tree of order 2m
// Constructor (Initializes B-Tree as empty)
BTree(int order)
{
root = null;
m = order;
}
// function to print this B-Tree
public void print()
{
if (root != null)
{

root.print();

System.out.println();
}
}

// function to insert the given key
in this B-Tree
public void insert(T key)
{
// If the tree
is empty
if (root ==
null)
{

root = new BTreeNode<T>(m, true); //
Create new root

root.keys[0] = key; // Insert key

root.keyTally = 1; // Update number of keys in
root
}
// If the tree is not empty
else
{

root = root.insert(key);
}
}
// function to search a key in this B-Tree
public BTreeNode<T> search(T
key)
{
if (root != null)
return
root.search(key);
else
return
null;
}
// function to traverse this B-Tree
public void traverse()
{
if (root != null)
{

root.traverse();

System.out.println();
}
}
}
BTreeNode.java
@SuppressWarnings("unchecked")
class BTreeNode<T extends Comparable<T>> {
boolean leaf;
int keyTally;
Comparable<T> keys[];
BTreeNode<T> references[];
int m;
static int level = 0;
// Constructor for BTreeNode class
public BTreeNode(int order, boolean leaf1)
{
// Copy the
given order and leaf property
m = order;
leaf =
leaf1;

// Allocate
memory for maximum number of possible keys
// and child
pointers
keys = new
Comparable[2*m-1];
references = new
BTreeNode[2*m];

// Initialize
the number of keys as 0
keyTally =
0;
}
// Function to print all nodes in a subtree rooted
with this node
public void print()
{
level++;
if (this != null) {

System.out.print("Level " + level + " ");

this.printKeys();

System.out.println();
// If this
node is not a leaf, then

// print all the subtrees rooted with this
node.

if (!this.leaf)

{

for (int j = 0; j < 2*m; j++)

{

if
(this.references[j] != null)


this.references[j].print();

}
}
}
level--;
}
// A utility function to print all the keys in this
node
private void printKeys()
{
System.out.print("[");
for (int i = 0;
i < this.keyTally; i++)
{

System.out.print(" " + this.keys);
}
System.out.print("]");
}
// A utility function to give a string
representation of this node
public String toString() {
String out = "[";
for (int i = 1; i <=
(this.keyTally-1); i++)
out += keys[i-1]
+ ",";
out += keys[keyTally-1] + "]
";
return out;
}
////// You may not change any code above this line
//////
////// Implement the functions below this line
//////
// Function to insert the given key in tree rooted
with this node
public BTreeNode<T> insert(T key)
{
// Your
code goes here
}
// Function to search a key in a subtree rooted
with this node
public BTreeNode<T> search(T
key)
{
// Your code goes here
}
// Function to traverse all nodes in a subtree
rooted with this node
public void traverse()
{
// Your code
goes here
}
}
B-Trees A B-Trees is a kind of balanced search tree. Like binary search trees it allows data to be kept sorted while allowing searches, insertions and deletions. Unlike a BST, it allows a node to have more than two children. Each node also contains a number of keys that contain pointers to the actual data. The B-Tree for this practical will have a maximum of k-1 keys and k child nodes where k is defined as follows: m <k < 2m. You are required to implement some of the B-Tree methods. Every time that a key is inserted, searching for the correct position should start at the root and propagate down to the correct location. Inserts are only performed on leaf nodes. Each full node encountered on the way down should be split. This is called the top-down pre-splitting insertion strategy, as mentioned on page 323 of the textbook. You have been given a functional B-Tree class and a partially implemented B-Tree node class to use. Your task is to implement the following methods in the B-Tree node class according to the given specification. Task 1: Insert Key (25] public BTreeNode<T> insert(T key) This function should insert the key key into the tree at the correct position. If this node is not a leaf node, then the correct child node needs to be determined. The root node of the changed tree should be returned. Task 2: Search Tree [5] public BTreeNode<T> search(T key)
This function should determine whether the key key is in the tree. If so, the function should return the node containing the given key. If the given key is not found in the tree, null should be returned. Task 3: Traverse Tree [5] public void traverse() This function should traverse all the nodes in a sub tree rooted in this node and print out all the keys in the correct order. You should use your own helper functions to assist in implementing these methods as per specification. However, you may not modify any of the given method signatures. 2