In JAVA.

Write a program containing the classes: TwoThreeTree, for a 2-3 tree data structure, Node, TreeN- ode, and LeafNode. Node is inherited by TreeNode and LeafNode. TreeNodes are the internal nodes of the 2-3 tree. They contain three references to Node, leftChild, middleChild, and rightChild. TreeNodes also contains two keys. The keys represent the smallest key in the middle subtree and the smallest key in the right subtree Each LeafNode contains one key.

class TreeNode { int keys[]; // keys for searching Node children[]; // references to the 2 or 3 children int degree = 0;

TreeNode() { keys = new int[2];//keys[0] = min key in middle subtree children = new Node[3];//references to children of leaves degree = 0;//for printing, overflow, and split operations }

void print() {

if(degree==1) System.out.print("(-,-)"); else if(degree==2)

System.out.print("(" + keys[1]+ ",-) ");

else System.out.print("(" + keys[1] + "," + keys[2] + ") ");

} }

Here is the interface for TwoThreeTree:

public interface TwoThreeTree {

boolean insert(int key); // returns false if the key already exists

boolean search(int key); // returns true if the key exists

boolean remove(int key); // returns true if the key found and deleted

void keyOrderList(); // prints all keys stored in order of increasing key values

void bfsList(); // prints all the keys in breadth first order

int numberOfNodes(); // returns the number of keys currently stored

int height(); // returns the number of links on any path from the root to a leaf

}

Your program will read commands as described below from the text file, P2data.txt and write to System.out. The test data will contain insert, search, delete, and various list commands. The insert, search and delete commands will provide numeric keys. keys are in [1,9999]. Your program will output the result of each command. Here are examples of the command formats:

I 12 //insert 12. Print the line, "Key 12 inserted" or the line, "Key 12 already exists"

D 13 //delete 13. Print the line, "Key 13 deleted" or the line, "Key 13 doesnt exist"

S 12 //search for 12. Print the line, "Key 12 found" or the line, "Key 12 doesnt exist"

K //print the word "Keys" then a newline, then print a space-separated list of all the keys in the tree on single line, in order of increasing key value

B //print the word "Tree" then a newline, then print the tree elements in breath first order, one line of text per tree level

H //print the word "Height" then a space, then print the tree height

M //print the word "Size" then a space, then print the total number of keys in the tree

E //end of input data

The last line of the test data is immediately followed by an End Of File marker. A B command for a 2-3 tree of height 2 containing keys 1-8 would look like this: Tree (4,7) (2,3) (5,6) (8,-) 12345678

A K command will print the above tree as follows: Keys 12345678 An H command will print: Height 2 An M command will print: Size 8

Insert: If an insert is attempted with a key that already exists in the tree, nothing is changed in the tree (no duplicates allowed.) If the parent of leaf nodes overflows, always split the parent and, if necessary, split its parent and so on, adding a new root if it overflows. Delete: If a delete is attempted with a key that doesnt exist in the tree, nothing is changed in the tree. If the parent, P, of a leaf node underflows (has only one child after a deletion), attempt the following remedies in the order given. G is the parent of P: 1. If one of Ps immediate siblings has three children: Borrow a leaf node from that sibling. Try the left sibling first, if it exists. 2. Else if Ps left and right siblings both have degree 2: If G has three children, donate the remaining leaf node of P to Ps left sibling, if it exists. If not, donates to Ps right sibling. Remove node P. 3. Else if G has 2 children: One is P and it has degree 1. The other is Ps only sibling and it has degree 2. Merge P and its sibling. Now G has 1 child. Remove G and pass the problem up to Gs parent.

Input

Output

I 12 B I6 I 12 I4 I2 I1 I3 I5 I8 I7 I 10 I 11 I 13 S5 S7 S 15 S3 K B H M D6 D7 D8 D 10 D 15 K B H M E

Key 12 inserted Tree (-,-) 12 Key 6 inserted Key 12 already exists Key 4 inserted Key 2 inserted Key 1 inserted Key 3 inserted Key 5 inserted Key 8 inserted Key 7 inserted Key 10 inserted Key 11 inserted Key 13 inserted Key 5 found Key 7 found Key 15 doesnt exist Key 3 found Keys 1 2 3 4 5 6 7 8 10 11 12 13 Tree (6,-) (3,-) (8,11) (2,-) (4,5) (7,-) (10,-) (12,13) 1 2 3 4 5 6 7 8 10 11 12 13 Height 3 Size 12 Key 6 deleted Key 7 deleted Key 8 deleted Key 10 deleted Key 15 doesnt exist Keys 1 2 3 4 5 11 12 13 Tree (3,11) (2,-) (4,5) (12,13) 1 2 3 4 5 11 12 13 Height 2 Size 8

Your program will only print the right-hand column, the sample output.