COMP 212 Lab 13: 2-3-4 Trees

In class, we introduced the idea of 2-3-4 trees. Structurally, these are simply trees where each node can have 2, 3, or 4 children. But what makes them interesting is that they are traditionally used with insert and remove methods that will maintain the trees in balanced form.

Exercises:

Copy the provided partial implementation of 2-3-4 trees from ~comp212/public_html/01-spring/notes/lecture-36/t234/ into your own directory.

  1. Write a method bool find(Integer n) for 2-3-4 trees. This method only needs to follow the structure of the trees, and does not need to alter the tree.

  2. Change the code so that it works not with int data, but for the more general IOrdered class.