Please help with the following Java requirement. Please meet requirements. Requirements-- Modify the tree234.java progra

[answerhappygod]

Please help with the following Java requirement. Please meet
requirements.
Requirements--
Modify the tree234.java program so that it creates
and works with 2-3 trees instead. It should display the tree and
allow searches. It should also allow items to be inserted. In
writing insert(), remember that no splits happen until the
appropriate leaf has been located. Then the leaf will be split if
it’s full. You’ll need to be able to split the root too. The
split() routine is recursive and can handle situations with a full
parent of a full child. This will allow insertion of an unlimited
number of items. Note that in the split() routine you’ll need to
split the parent before you can decide where the items go and where
to attach the children.
There are no restrictions on this project and you
can use any java library classes that you need.
//**If you intend to add an additional class please
identify it with (--------new class name------) in order for when I
attempt to compile I know where to add it**//
public class Tree {
private Node root;

public Tree(){
root = new Node();
}
public Node getNextChild(Node n, int id){
int numItems = n.getNumItems();
int i;
for(i = 0 ; i < numItems ;i++){
if(id < n.getStudent(i).id)
return n.getChild(i);
}
return n.getChild(i);
}
public int search(int id){
Node curr = root;
int childNo;
while(true){
childNo = curr.findStudent(id);
if(childNo != -1)
return childNo;
else if(curr.isLeaf())
return -1;
else
curr = getNextChild(curr,id);
}
}
public void insert(Student s){
Node curr = root;

while(true){
if(curr.isFull()){
split(curr); // split is done
curr = curr.getParent();//go up a level and restart search
}
else if(curr.isLeaf())
break;
else
curr = getNextChild(curr , s.id);
}
curr.insertStudent(s);
}

public void split(Node n){
Student B, C;
Node parent, child2, child3;
C = n.removeStudent();
B = n.removeStudent();
child2 = n.disconnectChild(2);
child3 = n.disconnectChild(3);

Node newNode = new Node();

if(n == root){
root = new Node();
parent = root;
root.connectChild(n, 0);
}
else{
parent = n.getParent();
}
//deal with parent
int index = parent.insertStudent(B);
int num = parent.getNumItems();

for(int i = num-1; i > index ; i--){
Node temp = parent.disconnectChild(i);
parent.connectChild(temp, i+1);
}
parent.connectChild(newNode, index+1);

//deal with newnode
newNode.insertStudent(C);
newNode.connectChild(child2, 0);
newNode.connectChild(child3, 1);
}
}
Thanks
Expert Answer
Was this answer helpful?
0
0
19 answers