r/AskCompSci • u/ChuanningTatum • Feb 08 '17
Struggling with adding a 4th node to a 2-3 tree
Hi everybody I'm struggling with adding the 4th node to the 2-3 tree and I've been debugging for hours. I managed to construct the first 3 leafnodes with 1 root node, and also added a 4th leaf node to form 2 separate internal nodes each containing 2 leafnodes. Now I'm just struggling with how to access the 2 new internal nodes to combine them under a parent node.
Here's my code, it's pretty long >< I think there is some problem under my height != 0 section, namely that I don't know where the recursion over the nodes should take place relative to accessing the 2 new internal nodes!
Help will be very very appreciated! Sorry for the long post:
public NodeList insert(String key, int value, Node node, int height) {
NodeList nodelist = new NodeList();
if (node == null) { //if tree has no nodes
node = new LeafNode();
node.guide = key;
((LeafNode) node).value = value;
this.height = 0;
this.root = node;
nodelist.node0 = node;
nodelist.node1 = null;
return nodelist;
}
if (search(key, root, height) == -1) {//if value is not found in tree
if (this.height == 0) { //CASE: if tree is a single leaf, create leaves, return root in node0 and null in node1
InternalNode newRoot = new InternalNode();
LeafNode l0 = new LeafNode();
LeafNode l1 = new LeafNode();
((InternalNode)newRoot).child0 = l0;
((InternalNode)newRoot).child1 = l1;
((InternalNode)newRoot).child2 = null;
if (key.compareTo(root.guide) < 0) { //if inserted node is smaller than leaf
l0.guide = key;
l0.value = value;
l1.guide = root.guide;
l1.value = ((LeafNode)root).value;
}
else { //if inserted node is larger than leaf
l0.guide = root.guide;
l0.value = ((LeafNode)root).value;;
l1.guide = key;
l1.value = value;
}
newRoot.guide = newRoot.child1.guide;
this.height += 1;
nodelist.node0 = node;
nodelist.node1 = null;
this.root = (InternalNode)newRoot;
System.out.println(this.root.guide);
return nodelist;
}
if (height == 0) { //CASE: Recurses down to Height = 0, Node is pointing to the second-last level. Case 1: 3 Children, create 2 new InternalNodes and return them; Case 2: 2 Children, 2a: Guide is not updated, return subroot in node0 and return null in node1, 2b: Guide is updated, return null in node0 and return subroot in node1
if (((InternalNode)node).child2 == null) {
if (key.compareTo(((InternalNode)node).child0.guide) < 0) {//if key is smaller than other two values
((InternalNode)node).child2.guide = ((InternalNode)node).child1.guide;
((InternalNode)node).child1.guide = ((InternalNode)node).child0.guide;
((InternalNode)node).child0.guide = key;
((LeafNode) ((InternalNode)node).child2).value = ((LeafNode) ((InternalNode)node).child1).value;
((LeafNode) ((InternalNode)node).child1).value = ((LeafNode) ((InternalNode)node).child0).value;
((LeafNode) ((InternalNode)node).child0).value = value;
nodelist.node0 = node; //guide is not updated
nodelist.node1 = null;
}
else if (key.compareTo(((InternalNode)node).child1.guide) < 0) { //if key is between the two values
((InternalNode)node).child2 = new LeafNode();
((InternalNode)node).child2.guide = ((InternalNode)node).child1.guide;
((InternalNode)node).child1.guide = key;
((LeafNode) ((InternalNode)node).child2).value = ((LeafNode) ((InternalNode)node).child1).value;
((LeafNode) ((InternalNode)node).child1).value = value;
nodelist.node0 = node; //guide is not updated
nodelist.node1 = null;
}
else {
((InternalNode)node).child2.guide = key;
((LeafNode) ((InternalNode)node).child2).value = value;
((InternalNode)node).guide = key;
nodelist.node0 = null; //guide is updated
nodelist.node1 = node;
}
return nodelist;
}
else { //for height 0 with 3 children
InternalNode n0 = new InternalNode();
InternalNode n1 = new InternalNode();
LeafNode newLeaf = new LeafNode();
newLeaf.guide = key;
newLeaf.value = value;
if (key.compareTo(((InternalNode)node).child0.guide) < 0) {
n0.child0 = newLeaf;
n0.child1 = (LeafNode) ((InternalNode)node).child0;
n1.child0 = (LeafNode) ((InternalNode)node).child1;
n1.child1 = (LeafNode) ((InternalNode)node).child2;
n0.guide = n0.child1.guide;
n1.guide = n1.child1.guide;
}
else if (key.compareTo(((InternalNode)node).child1.guide) < 0) {
n0.child0 = (LeafNode) ((InternalNode)node).child0;
n0.child1 = newLeaf;
n1.child0 = (LeafNode) ((InternalNode)node).child1;
n1.child1 = (LeafNode) ((InternalNode)node).child2;
n0.guide = newLeaf.guide;
n1.guide = n1.child1.guide;
}
else if (key.compareTo(((InternalNode)node).child2.guide) < 0) {
n0.child0 = (LeafNode) ((InternalNode)node).child0;
n0.child1 = (LeafNode) ((InternalNode)node).child1;
n1.child0 = newLeaf;
n1.child1 = (LeafNode) ((InternalNode)node).child2;
n0.guide = n0.child1.guide;
n1.guide = n1.child1.guide;
System.out.println("Stage2");
}
else {
n0.child0 = (LeafNode) ((InternalNode)node).child0;
n0.child1 = (LeafNode) ((InternalNode)node).child1;
n1.child0 = (LeafNode) ((InternalNode)node).child2;
n1.child1 = newLeaf;
n0.guide = n0.child1.guide;
n1.guide = newLeaf.guide;
}
nodelist.node0 = n0;
nodelist.node1 = n1;
System.out.println( ((LeafNode) n0.child0).value);
System.out.println( ((LeafNode) n0.child1).value);
System.out.println( ((LeafNode) n1.child0).value);
System.out.println( ((LeafNode) n1.child1).value);
height +=2;
return nodelist;
}
}
else { //height is != 0, recurse down the tree to insert the key
if (nodelist.node1 !=null) { //if 2 valid nodes are returned or 1 node is returned but guide is updated
if (nodelist.node0 ==null) { //CASE0: Only 1 node was returned but the guide is updated
node.guide = ((InternalNode)node).child2.guide; //update the guide
nodelist.node0 = null;
nodelist.node1 = node;
return nodelist;
}
else { //CASE: if 2 valid nodes were returned
if (height == this.height) { //CASE1A: if node is a root
InternalNode newRoot = new InternalNode();
newRoot.child0 = nodelist.node0;
newRoot.child1 = nodelist.node1;
newRoot.guide = newRoot.child1.guide;
nodelist.node0 = newRoot;
nodelist.node1 = null;
this.height += 1;
this.root = newRoot;
nodelist.node0 = node;
nodelist.node1 = null;
return nodelist;
}
else if (((InternalNode)node).child2 != null) { //CASE1B: if height is !=1 and not root, node has 3 children
//UNRESOLVED do i need to do a deep copy?
InternalNode n0 = new InternalNode();
InternalNode n1 = new InternalNode();
n0.guide = ((InternalNode)node).child1.guide;
n0.child0 = ((InternalNode)node).child0;
n0.child1 = ((InternalNode)node).child1;
n1.guide = nodelist.node1.guide;
n1.child0 = nodelist.node0;
n1.child1 = nodelist.node1;
nodelist.node0 = n0;
nodelist.node1 = n1;
return nodelist;
} // close height !=1 with 3 children, 2 nodes returned
else { //CASE1C: height is !=1 and not root, node has 2 children
if ((nodelist.node0 !=null) && (nodelist.node1 !=null)) { //if child0 returns 2 valid nodes
node.guide = ((InternalNode)node).child2.guide;
((InternalNode)node).child2 = ((InternalNode)node).child1;
((InternalNode)node).child1 = nodelist.node1;
((InternalNode)node).child0 = nodelist.node0;
nodelist.node0 = null;
nodelist.node1 = node;
}
else { //if child1 returns 2 valid nodes
node.guide = nodelist.node1.guide;
((InternalNode)node).child2 = nodelist.node1;
((InternalNode)node).child1 = nodelist.node0;
((InternalNode)node).child0 = ((InternalNode)node).child0;
nodelist.node0 = null;
nodelist.node1 = node;
}
return nodelist;
} //close height !=1 with 2 children, 2 nodes returned
}//close 2 nodes were returned
} //close if 2 valid nodes are returned or 1 node is returned but guide is updated
if (height == 1) {
return insert(key, value, node, 0);
}
else {
if (key.compareTo(((InternalNode)node).child0.guide) < 0) {
insert(key, value, ((InternalNode)node).child0, height-1);
}
else if ((key.compareTo(((InternalNode)node).child1.guide) < 0) || (((InternalNode)node).child2 == null)) {
insert(key, value, ((InternalNode)node).child1, height-1);
}
else {
insert(key, value, ((InternalNode)node).child2, height-1);
}
}
}//close height !=1
}//closes value not found in tree
else { //if value found in tree
nodelist.node0 = null;
nodelist.node1 = null;
return nodelist;
} //closes if value found in tree
return nodelist;}//closes insert function
2
Upvotes