CS 70

Phase 4: Insert and Move to Root

In this step, you will extend your insert functionality to allow the ROOT scheme, which moves each inserted item to the root of the tree.

We'll follow the same process we've used for adding new functionality in previous assignments: Plan, Write Tests, Implement, Test & Fix.

Steps

  • RHS Cow speaking

    Read over what you need to do, but before you start coding, plan.

  • LHS Cow speaking

    And there's a good testing tip in the Helpful hints!

  • You'll need to submit a planning image for this phase Planning/Phase_4.jpg.

You can look back at the instructions for HW6 for a reminder of the 4 steps (planning, writing tests, implementing, test & fix) that you should go through, and of what we’re looking for in each.

Remember to git add your Planning/Phase_4.jpg file so that we can see it!

  • You've already written the helper function for the LEAF insertion scheme (that's the old behavior from Homework 6). Now, in the class declaration, add a new (static) node-based private helper function for inserting into the tree where the item is moved to the root as part of the process. Pick a suitable name for this (private) function.
  • Add a conditional to your insert function that will call the correct private helper member functions, depending on whether the tree's insertion scheme is LEAF or ROOT. (Don't worry about RANDOM yet.)
  • In the implementation of your new private helper function, implement the recursive insert-and-move-to-root behavior that we described in the lesson materials (in Week 10, Lesson 2).
  • You should create private helper functions for left- and right-rotations to support those behaviors. Note that we have provided code for one of the rotations in the lesson materials. You may copy this code and use it as a basis to write the other rotation. If you do copy it, be sure to give attribution (e.g., “adapted from code provided in CS 70, Week 10, Lesson 2”).

Testing Using a Useful Property of INSERT-AND-MOVE-TO-ROOT

A tree built by the insertion of values \( v_1, v_2, v_3, \ldots v_n \) with the regular INSERT operation is identical to a tree build by inserting \( v_n, v_{n-1}, v_{n-2}, \ldots, v_1 \) with INSERT-AND-MOVE-TO-ROOT.

This property can be very useful in testing. If you build a tree with LEAF insertion by inserting, say, F, J, A, E, I, B, D, G, H, C, and then build a tree with ROOT insertion, inserting the reversed sequence (i.e., C, H, G, D, B, I, E, A, J, F), both methods shoul build a tree with the exact same shape.

Thus you can test your ROOT insertion style by building both trees, printing both of them to std::stringstreams, and seeing if they show the same structure when printed (i.e, idential output including the parentheses).

(Don't rely on using == or your tree iterator, as these deal with the values in sorted order and so won't show whether the trees have the same shape.)

To Complete This Part of the Assignment…

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)