I was trying to figure out how to do an insertion into a 2-3 trees when there ar

Question

I was trying to figure out how to do an insertion into a 2-3 trees when there are already 3 kids and we need to insert a 4th i know we have to split the kids into 2 seperate groups but i cannot implement it.

Explanation / Answer

class TwoThreeTree{ TwoThreeNode root; // the root node of the tree int n; // the # of elements being maintained in the tree. class TwoThreeNode { boolean isLeaf; Object elements[4]; // elements[1] is the first element of the node, elements[2] is the second element of the node, etc. TwoThreeNode children[4]; // children[1] is the leftmost child of the node, children[2] is the middle child, and children[3] is the rightmost child. TwoThreeNode parent; // pointer the the parent of this node... int numElements; // indicates the # of elements stored in this node. If the node is not a leaf, numElements + 1 is the # of children... // IMPORTANT!!! // - There can only be 1 or 2 elements if the current node is an internal node, and only 2 or 3 elements if the current node is a leaf // - We'll assume array indices are counted from 1 rather than 0 for simplicity. The change to making indices count from 0 is a minor one though. // - Whether the current node is a leaf or not, elements[1] is the leftmost element, elements[2] is the next element, etc. // - All entries of the children array are NULL if the current node is a leaf. // - When the current node in an internal node, the entries of the children[1] subtree are all elements[1] but elements[2]. // - Although one can argue that for 2-3 trees, we need at most 3 children and 3 elements in any node, we make // children array and elements array allow for 4 elements instead of 3 so to avoid needing to create extra // data structures during the insertion process. (The alternate implementation is to have children array and // elements array be of 3 elements, but create temporary extra data strctures to accomodate the insertion process.) } // creates a brand new empty 2-3 tree... TwoThreeTree() { root = new TwoThreeNode(); n = 0; root.isLeaf = true; root.numElements = 0; root.parent = null; } // Returns the element in our 2-3 tree matching k, or null if the element doesn't exist Object search(Object k) { TwoThreeNode leafNode = searchSubtreeForLeaf(this.root, k); // this gives us the leaf node that's supposed to have k in it. We check the elements one by one in leafNode for k. If we find k, return it, otherwise we return null; } // This subroutine recursively searches ttn's subtree for the leafnode containing k. // If k is in ttn's subtree, we return the leaf node with k in it. // If k is not in ttn's subtree, we return the leaf node where k should be inserted into... TwoThreeNode searchSubtreeForLeaf(TwoThreeNode ttn, Object k) { if (ttn.isLeaf) { return ttn; } else { if (ttn.elements[1] = i+1, shift p.children[ip] one spot to the right in p's children array; And for all ip >= i, shift p.elements[ip] one spot to the right in p's elements array; We then point p.children[i] to ttn, and p.children[i+1] to sibling; if (ttn.isLeaf) { p.elements[i] = copy(k); } else { p.elements[i] = k; } p.numElements++; sibling.parent = p; if (p.numElements >= 3) { splitNode(p); // if p ends up with three elements or more, we've got to split that too! } } } void borrowToLeaf(TwoThreeNode ttn) { if ((ttn.numElements = 2 shift ttnRight.elements[ip] one spot to the left in the elements array of ttnRight; delete the entry in p.elements[i]; p.elements[i] = copy(k); ttn.numElements++; ttnRight.numElements--; } else if ((ttnLeft != null) && (ttnLeft.numElements == 3)) { Let k denote ttnLeft.elements[2]; Let l denote ttnLeft.elements[3]; ttn.elements[2] = ttn.elements[1]; ttn.elements[1] = l; delete the entry in p.elements[i-1]; p.elements[i-1] = copy(k); ttn.numElements++; ttnLeft.numElements--; } else if (ttnRight != null) { mergeLeafNodes(ttn, ttnRight); } else { mergeLeafNodes(ttnLeft, ttn); } } } void borrowToInternalNode(TwoThreeNode ttn) { if (ttn.numElements = 2 shift ttnRight.children[ip] one spot to the left in ttnRight's children array; for each ip >= 2 shift ttnRight.elements[ip] one spot to the left in ttnRight's elements array; ttn.numElements++; ttnRight.numElements--; } else if ((ttnLeft != null) && (ttnLeft.numElements == 2)) { Let k denote ttnLeft.elements[2]; Let l denote p.elements[i-1]; ttn.children[2] = ttn.children[1]; ttn.elements[1] = l; ttn.children[1] = ttnLeft.children[3]; p.elements[i-1] = k; ttnLeft.elements[2] = null; ttnLeft.children[3] = null; ttn.numElements++; ttnLeft.numElements--; } else if (ttnRight != null) { mergeInternalNodes(ttn, ttnRight); } else { mergeInternalNodes(ttnLeft, ttn); } } else if (ttn.parent == null) { // if we have a root node with no elements and one child, we delete it and make its only child the new root node... this.root = ttn.children[1]; delete(ttn); } } } // When we merge two adjacent sibling nodes ttn1 and ttn2 that are leaves, we assume that one of them has 1 element, and the other has 2 elements... void mergeLeafNodes(TwoThreeNode ttn1, TwoThreeNode ttn2) { TwoThreeNode p = ttn1.parent; // we assume p is also ttn2's parent, and that ttn1 and ttn2 are adjacent siblings... Let i denote the value such that p.children[i]==ttn1 (and hence by our assumption, p.children[i+1]==ttn2...); Object k = p.elements[i]; if (ttn1.numElements == 1) { ttn1.elements[2] = ttn2.elements[1]; ttn1.elements[3] = ttn2.elements[2]; } else { ttn1.elements[3] = ttn2.elements[1]; } delete(ttn2); // remove the object forever... ttn1.numElements = 3; p.children[i+1] = null; delete(p.elements[i]); For all ip >= i+1, shift p.elements[ip] one spot to the left in p's elements array; Then, for all ip >= i+2, shift p.children[ip] one spot to the left in p's children array; p.numElements--; if (p.numElements = i+2, shift p.children[ip] one spot to the left in p's children array; p.numElements--; if (p.numElements

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.