Question: please complete the TODO. It is asking for the case: If not a leaf node, we will need to insert in one of our subtrees.?
please complete the TODO. It is asking for the case: If not a leaf node, we will need to insert in one of our subtrees.?
~~~~~~~
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) {
if (item < n.items[0]) {
n.items[2] = n.items[1];
n.items[1] = n.items[0];
n.items[0] = item;
} else if(item > n.items[0] && item < n.items[1]){
n.items[2] = n.items[1];
n.items[1] = item;
} else if(item > n.items[1]) {
n.items[2] = item;
}
n.nodeType = 4;
}
else
return n;
}
// If not a leaf node, we will need to insert in one of our subtrees.
else {
if (n.nodeType == 2) {
if (item < n.items[0]) {
Node result = put(n.subtrees[0], item);
// if the resulting root is not a 4-node, we can insert it as our new left.
if (result.nodeType != 4) {
n.subtrees[0] = result;
}
// otherwise, we need to fix it by splitting it
else {
Node newLeft = new Node(result.items[0], result.subtrees[0], result.subtrees[1]);
Node newMiddle = new Node(result.items[2], result.subtrees[2], result.subtrees[3]);
n.items[1] = n.items[0];
n.items[0] = result.items[1];
n.subtrees[2] = n.subtrees[1];
n.subtrees[1] = newMiddle;
n.subtrees[0] = newLeft;
n.nodeType = 3;
}
} else {
Node result = put(n.subtrees[1], item);
// if the resulting root is not a 4-node, we can insert it as our new right.
if (result.nodeType != 4) {
n.subtrees[1] = result;
}
// otherwise, we need to fix it by splitting it
else {
Node newMiddle = new Node(result.items[0], result.subtrees[0], result.subtrees[1]);
Node newRight = new Node(result.items[2], result.subtrees[2], result.subtrees[3]);
n.items[1] = result.items[1];
n.subtrees[2] = newRight;
n.subtrees[1] = newMiddle;
n.nodeType = 3;
}
}
return n;
} else if (n.nodeType == 3) {
// TODO
throw new RuntimeException("Implement me!");
} else
throw new RuntimeException("ERROR: " + n.nodeType + "-node found while inserting");
}
return n;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help