1  import java.util.ArrayList;
  2  
  3  public class Tree24<E extends Comparable<E>> implements Tree<E> {
  4    private Tree24Node<E> root;
  5    private int size;
  6   
  7    /** Create a default 2-4 tree */
  8    public Tree24() {
  9    }
 10  
 11    /** Create a 2-4 tree from an array of objects */
 12    public Tree24(E[] elements) {
 13      for (int i = 0; i < elements.length; i++)
 14        insert(elements[i]);     
 15    }
 16  
 17    @Override /** Search an element in the tree */
 18    public boolean search(E e) {
 19      Tree24Node<E> current = root; // Start from the root
 20  
 21      while (current != null) {
 22        if (matched(e, current)) { // Element is in the node
 23          return true; // Element found
 24        }
 25        else {
 26          current = getChildNode(e, current); // Search in a subtree
 27        }
 28      }
 29  
 30      return false; // Element is not in the tree
 31    }
 32  
 33    /** Return true if the element is found in this node */
 34    private boolean matched(E e, Tree24Node<E> node) {
 35      for (int i = 0; i < node.elements.size(); i++)
 36        if (node.elements.get(i).equals(e))
 37          return true; // Element found
 38  
 39      return false; // No match in this node
 40    }
 41  
 42    /** Locate a child node to search element e */
 43    private Tree24Node<E> getChildNode(E e, Tree24Node<E> node) {
 44      if (node.child.size() == 0)
 45        return null; // node is a leaf
 46  
 47      int i = locate(e, node); // Locate the insertion point for e
 48      return node.child.get(i); // Return the child node
 49    }
 50  
 51    @Override /** Insert element e into the tree
 52     *  Return true if the element is inserted successfully
 53     */
 54    public boolean insert(E e) {
 55      if (root == null)
 56        root = new Tree24Node<E>(e); // Create a new root for element
 57      else {
 58        // Locate the leaf node for inserting e
 59        Tree24Node<E> leafNode = null;
 60        Tree24Node<E> current = root;
 61        while (current != null)
 62          if (matched(e, current)) {
 63            return false; // Duplicate element found, nothing inserted
 64          }
 65          else {
 66            leafNode = current;
 67            current = getChildNode(e, current);
 68          }
 69  
 70        // Insert the element e into the leaf node
 71        insert(e, null, leafNode); // The right child of e is null
 72      }
 73  
 74      size++; // Increase size
 75      return true; // Element inserted
 76    }
 77  
 78    /** Insert element e into node u */
 79    private void insert(E e, Tree24Node<E> rightChildOfe,
 80        Tree24Node<E> u) {
 81      // Get the search path that leads to element e
 82      ArrayList<Tree24Node<E>> path = path(e);
 83  
 84      for (int i = path.size() - 1; i >= 0; i--) {
 85        if (u.elements.size() < 3) { // u is a 2-node or 3-node
 86          insert23(e, rightChildOfe, u); // Insert e to node u
 87          break; // No further insertion to u's parent needed
 88        }
 89        else {
 90          Tree24Node<E> v = new Tree24Node<E>(); // Create a new node
 91          E median = split(e, rightChildOfe, u, v); // Split u
 92  
 93          if (u == root) {
 94            root = new Tree24Node<E>(median); // New root
 95            root.child.add(u); // u is the left child of median
 96            root.child.add(v); // v is the right child of median
 97            break; // No further insertion to u's parent needed
 98          }
 99          else {
100            // Use new values for the next iteration in the for loop
101            e = median; // Element to be inserted to parent
102            rightChildOfe = v; // Right child of the element
103            u = path.get(i - 1); // New node to insert element
104          } 
105        }
106      } 
107    }
108  
109    /** Insert element to a 2- or 3- and return the insertion point */
110    private void insert23(E e, Tree24Node<E> rightChildOfe,
111        Tree24Node<E> node) {
112      int i = this.locate(e, node); // Locate where to insert
113      node.elements.add(i, e); // Insert the element into the node
114      if (rightChildOfe != null)
115        node.child.add(i + 1, rightChildOfe); // Insert the child link
116    }
117  
118    /** Split a 4-node u into u and v and insert e to u or v */
119    private E split(E e, Tree24Node<E> rightChildOfe,
120        Tree24Node<E> u, Tree24Node<E> v) {
121      // Move the last element in node u to node v
122      v.elements.add(u.elements.remove(2));
123      E median = u.elements.remove(1);
124  
125      // Split children for a non-leaf node
126      // Move the last two children in node u to node v
127      if (u.child.size() > 0) {
128        v.child.add(u.child.remove(2));
129        v.child.add(u.child.remove(2));
130      }
131  
132      // Insert e into a 2- or 3- node u or v.
133      if (e.compareTo(median) < 0)
134        insert23(e, rightChildOfe, u);
135      else
136        insert23(e, rightChildOfe, v);
137  
138      return median; // Return the median element
139    }
140  
141    /** Return a search path that leads to element e */
142    private ArrayList<Tree24Node<E>> path(E e) {
143      ArrayList<Tree24Node<E>> list = new ArrayList<Tree24Node<E>>();
144      Tree24Node<E> current = root; // Start from the root
145  
146      while (current != null) {
147        list.add(current); // Add the node to the list
148        if (matched(e, current)) {
149          break; // Element found
150        }
151        else {
152          current = getChildNode(e, current);
153        }
154      }
155  
156      return list; // Return an array of nodes
157    }
158  
159    @Override /** Delete the specified element from the tree */
160    public boolean delete(E e) {
161      // Locate the node that contains the element e
162      Tree24Node<E> node = root;
163      while (node != null)
164        if (matched(e, node)) {
165          delete(e, node); // Delete element e from node
166          size--; // After one element deleted
167          return true; // Element deleted successfully
168        }
169        else {
170          node = getChildNode(e, node); 
171        }
172  
173      return false; // Element not in the tree
174    }
175  
176    /** Delete the specified element from the node */
177    private void delete(E e, Tree24Node<E> node) {
178      if (node.child.size() == 0) { // e is in a leaf node
179        // Get the path that leads to e from the root
180        ArrayList<Tree24Node<E>> path = path(e);
181  
182        node.elements.remove(e); // Remove element e
183  
184        if (node == root) { // Special case
185          if (node.elements.size() == 0) 
186            root = null; // Empty tree
187          return; // Done
188        }
189  
190        validate(e, node, path); // Check underflow node
191      }
192      else { // e is in an internal node
193        // Locate the rightmost node in the left subtree of the node 
194        int index = locate(e, node); // Index of e in node
195        Tree24Node<E> current = node.child.get(index);
196        while (current.child.size() > 0) {
197          current = current.child.get(current.child.size() - 1);
198        }
199        E rightmostElement =
200          current.elements.get(current.elements.size() - 1);
201        
202        // Get the path that leads to e from the root
203        ArrayList<Tree24Node<E>> path = path(rightmostElement);
204  
205        // Replace the deleted element with the rightmost element
206        node.elements.set(index, current.elements.remove(
207          current.elements.size() - 1));
208  
209        validate(rightmostElement, current, path); // Check underflow
210      }
211    }
212  
213    /** Perform transfer and confusion operations if necessary */
214    private void validate(E e, Tree24Node<E> u,
215        ArrayList<Tree24Node<E>> path) {
216      for (int i = path.size() - 1; u.elements.size() == 0; i--) {
217        Tree24Node<E> parentOfu = path.get(i - 1); // Get parent of u
218        int k = locate(e, parentOfu); // Index of e in the parent node
219  
220        // Check two siblings
221        if (k > 0 && parentOfu.child.get(k - 1).elements.size() > 1) {
222          leftSiblingTransfer(k, u, parentOfu);
223        }
224        else if (k + 1 < parentOfu.child.size() &&
225            parentOfu.child.get(k + 1).elements.size() > 1) {          
226          rightSiblingTransfer(k, u, parentOfu);
227        }
228        else if (k - 1 >= 0) { // Fusion with a left sibling
229          // Get left sibling of node u 
230          Tree24Node<E> leftNode = parentOfu.child.get(k - 1);
231      
232          // Perform a fusion with left sibling on node u
233          leftSiblingFusion(k, leftNode, u, parentOfu);  
234  
235          // Done when root becomes empty
236          if (parentOfu == root && parentOfu.elements.size() == 0) {
237            root = leftNode;
238            break;
239          }
240  
241          u = parentOfu; // Back to the loop to check the parent node
242        }
243        else { // Fusion with right sibling (right sibling must exist)
244          // Get left sibling of node u 
245          Tree24Node<E> rightNode = parentOfu.child.get(k + 1);
246  
247          // Perform a fusion with right sibling on node u
248          rightSiblingFusion(k, rightNode, u, parentOfu);  
249  
250          // Done when root becomes empty
251          if (parentOfu == root && parentOfu.elements.size() == 0) {
252            root = rightNode;
253            break;
254          }
255  
256          u = parentOfu; // Back to the loop to check the parent node
257        }
258      }
259    }
260  
261    /** Locate the insertion point of the element in the node */
262    private int locate(E o, Tree24Node<E> node) {
263      for (int i = 0; i < node.elements.size(); i++) {
264        if (o.compareTo(node.elements.get(i)) <= 0) {
265          return i;
266        }
267      }
268  
269      return node.elements.size();
270    }
271  
272    /** Perform a transfer with a left sibling */
273    private void leftSiblingTransfer(int k, 
274        Tree24Node<E> u, Tree24Node<E> parentOfu) {
275      // Move an element from the parent to u
276      u.elements.add(0, parentOfu.elements.get(k - 1));
277      
278      // Move an element from the left node to the parent
279      Tree24Node<E> leftNode = parentOfu.child.get(k - 1);
280      parentOfu.elements.set(k - 1,
281        leftNode.elements.remove(leftNode.elements.size() - 1));
282  
283      // Move the child link from left sibling to the node
284      if (leftNode.child.size() > 0)
285        u.child.add(0, leftNode.child.remove(
286          leftNode.child.size() - 1));
287    }
288  
289    /** Perform a transfer with a right sibling */
290    private void rightSiblingTransfer(int k, 
291        Tree24Node<E> u, Tree24Node<E> parentOfu) {
292      // Transfer an element from the parent to u
293      u.elements.add(parentOfu.elements.get(k));
294      
295      // Transfer an element from the right node to the parent
296      Tree24Node<E> rightNode = parentOfu.child.get(k + 1);
297      parentOfu.elements.set(k, rightNode.elements.remove(0));
298  
299      // Move the child link from right sibling to the node
300      if (rightNode.child.size() > 0)
301        u.child.add(rightNode.child.remove(0));
302    }
303  
304    /** Perform a fusion with a left sibling */
305    private void leftSiblingFusion(int k, Tree24Node<E> leftNode,
306        Tree24Node<E> u, Tree24Node<E> parentOfu) {
307      // Transfer an element from the parent to the left sibling    
308      leftNode.elements.add(parentOfu.elements.remove(k - 1));
309  
310      // Remove the link to the empty node
311      parentOfu.child.remove(k);
312  
313      // Adjust child links for non-leaf node
314      if (u.child.size() > 0)
315        leftNode.child.add(u.child.remove(0));
316    }
317    
318    /** Perform a fusion with a right sibling */
319    private void rightSiblingFusion(int k, Tree24Node<E> rightNode,
320        Tree24Node<E> u, Tree24Node<E> parentOfu) {
321      // Transfer an element from the parent to the right sibling
322      rightNode.elements.add(0, parentOfu.elements.remove(k));
323  
324      // Remove the link to the empty node
325      parentOfu.child.remove(k);
326  
327      // Adjust child links for non-leaf node
328      if (u.child.size() > 0)
329        rightNode.child.add(0, u.child.remove(0));
330    }
331  
332    @Override /** Get the number of nodes in the tree */
333    public int getSize() {
334      return size;
335    }
336  
337    @Override /** Preorder traversal from the root */
338    public void preorder() {
339      preorder(root);
340    }
341  
342    /** Preorder traversal from a subtree */
343    private void preorder(Tree24Node<E> root) {
344      if (root == null)return;
345      for (int i = 0; i < root.elements.size(); i++)
346        System.out.print(root.elements.get(i) + " ");
347  
348      for (int i = 0; i < root.child.size(); i++)
349        preorder(root.child.get(i));
350    }
351  
352    @Override /** Inorder traversal from the root*/
353    public void inorder() {
354      // Left as exercise
355    }
356  
357    /** Postorder traversal from the root */
358    public void postorder() {
359      // Left as exercise
360    }
361  
362    @Override /** Return true if the tree is empty */
363    public boolean isEmpty() {
364      return root == null;
365    }
366    
367    @Override /** Remove all elements from the tree */
368    public void clear() {
369      root = null;
370      size = 0;
371    }
372    
373    @Override /** Return an iterator to traverse elements in the tree */
374    public java.util.Iterator<E> iterator() {
375      // Left as exercise
376      return null;
377    }
378    
379    /** Define a 2-4 tree node */
380    protected static class Tree24Node<E extends Comparable<E>> {
381      // elements has maximum three values
382      ArrayList<E> elements = new ArrayList<E>(3);
383      // Each has maximum four childres
384      ArrayList<Tree24Node<E>> child 
385        = new ArrayList<Tree24Node<E>>(4);
386  
387      /** Create an empty Tree24 node */
388      Tree24Node() {
389      }
390  
391      /** Create a Tree24 node with an initial element */
392      Tree24Node(E o) {
393        elements.add(o);
394      }
395    }
396  }