CS 70

Phase 3: Specifying the Insertion Scheme

So far, our tree only supports a basic insertion scheme that doesn't ensure the tree is balanced. Our goal now is to enhance the tree to avoid the pathological behaviors that can easily be triggered with this approach.

At this stage, the tree won't do anything if anyone specifies something other than the basic LEAF scheme, but we'll have the pieces in place to add in the other schemes in subsequent steps.

Steps

Refer to the specification, and

  • LHS Cow speaking

    Remember, the enum is declared outside the class.

  • Add the enumeration type bst_style for specifying the insertion scheme.
  • Add a data member holding the bst_style for this tree.
  • Change the default constructor to set the scheme to LEAF by default.
  • Add a new (explicit) constructor where the insertion scheme is specified by passing a bst_style argument.
  • Change at least some of your tests to create a tree using the single-argument constructor, passing in LEAF.

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