please complete the todo: ~~~~~~~~~~~~~~~~~~~ private Node put(Node n, int item)
ID: 3710527 • Letter: P
Question
please complete the todo:
~~~~~~~~~~~~~~~~~~~
private Node put(Node n, int item) {
/*
* First check if n contains item. If it does, there is nothing to do and we can
* return the root of this subtree unchanged
*/
int itemCount = n.nodeType - 1;
for (int i = 0; i < itemCount; i++) {
if (n.items[i] == item)
return n;
}
/*
* Because we always insert into a pre-existing leaf, the base case here is a
* tree with one node (the root is a leaf).
*/
if (n.isLeaf()) {
// If the node is a 2-node, insert the new item to its left or right.
if (n.nodeType == 2) {
if (item < n.items[0]) {
n.items[1] = n.items[0];
n.items[0] = item;
} else {
n.items[1] = item;
}
n.nodeType = 3;
}
else if (n.nodeType == 3) {
// TODO
// Turn this into a 4-node and return it since you are allowed
// to temporarily have a 4-node as a the root.
throw new RuntimeException("Implement me");
}
else
throw new RuntimeException("ERROR: " + n.nodeType + "-node found while inserting");
return n;
}
Explanation / Answer
private Node put(Node n, int item) { /* * First check if n contains item. If it does, there is nothing to do and we can * return the root of this subtree unchanged */ int itemCount = n.nodeType - 1; for (int i = 0; iRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.