CS 70

Phase 5: Move size_ to Node

In this step, you will prepare to implement randomized insert by moving information about the size of the tree from the TreeSet class template to the nested node class.

We'll adopt our usual process: Plan, Write Tests, Implement, Test & Fix.

  • RHS Cow speaking

    Check out the hints and tips on the side!

  • LHS Cow speaking

    And in this phase, it really helps to draw a diagram.

Steps

You will need to submit a planning image for this phase, as Planning/Phase_5.jpg.

Moving size_

In order to make randomized insert work, you will need to know the size of each subtree. For Homework 6, you probably stored size_ as a data member of the TreeStringSet class. But that doesn't give you an easy way to find the size of a subtree!

Remember that a subtree is represented by the node that is the root of the subtree. If you want to know the size of every subtree, you need to move size_ into the Node class. Then the size of any (sub)tree is stored in its root's size_ data member!

In this step you will update your encoding so that size_ is a part of the Node struct (and no longer directly stored in the enclosing TreeSet class) and then adjust your implementation as necessary.

Suggested Helper: nodeSize

Given a subtree, we might want to say subtree->size_ to find its size. However, empty trees are represented by a nullptr value, so this code won't work in that case. Rather than scatter nullptr checks into your code every time you want to know the size of a subtree, it helps to write a helper function that takes a Node* pointer and

  • If the pointer is nullptr, returns 0.
  • Otherwise, returns the Node's size_.

Then you can use nodeSize(subtree) whenever you need the size of the subtree and have it “just work” even if the subtree is empty. (It's your private helper function, so you don't have to call it nodeSize.)

Required Function: printSizesToStream

  • Goat speaking

    What use is this function?

  • LHS Cow speaking

    It'll be a huge help in testing to make sure your subtree sizes are correct!

Use Your printSizesToStream Function in Testing

Remember that 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 built by inserting \(v_n, v_{n-1}, v_{n-2}, \ldots, v_1 \) with INSERT-AND-MOVE-TO-ROOT, and that regular INSERT performs no rotations, and INSERT-AND-MOVE-TO-ROOT performs lots of rotations.

Thus, you can test whether your rotation code updates sizes correctly by building the same shaped tree two ways, one with LEAF insertion and one with ROOT insertion (with the reversed sequence of inserts) and seeing if you're messing up the sizes anywhere.

You should implement the public printSizesToStream function. It behaves just like the printToStream function, except instead of printing the item for each node it prints the size of the subtree rooted at each node.

Specifically, your printSizesToStream function should write your tree to the provided ostream (output stream) using the following algorithm, which is almost identical to the one you implemented for printToStream:

DISPLAY-SIZES(subtree):
    if the subtree is empty,
        PRINT 0
    otherwise:
        PRINT "("
        DISPLAY-SIZES(left subtree)
        PRINT ", "
        PRINT the size of this (sub)tree
        PRINT ", "
        DISPLAY-SIZES(right subtree)
        PRINT ")"


Maintaining Sizes

You'll need to change your insert function and its associated helpers to make sure that the subtree size stored in each node is correct after each insert operation. Thus you will have to update your rotate functions so they properly update size_ in the subtrees involved in the rotation. It is very easy not to think this part through properly and make a mistake.

Think Through Maintaining Sizes with Rotations Concretely

Human beings are much better at concrete thinking than abstract thinking, and excellent at going from concrete to abstract, so the easiest way to figure out what you need to do to update the sizes when rotating the tree is to work through a concrete example of updating an example tree with real sizes. When you do, you'll be able to see the pattern and generalize.

  • Plan before you code. Understand how node sizes need to be updated when you rotate the tree. (See the Helpful Hints below.)
  • The amount of code you need to write is quite small, but understanding what that code needs to be requires some thinking. Just as a rotation can be performed locally in constant time by just reassigning pointers in the relevant nodes, we can update the sizes in constant time using the sizes in the relevant nodes.

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.)