CS 70

insert() and exists()

In this part of the assignment, your tree will become useful—you'll get to a point where you can put things into the tree, and then search to see if those things are there.

Hint

Remember that we discussed insert in detail in the BST lesson! It would probably benefit you to review that part of the lesson. The materials first give a high-level conceptual approach to insertion in a BST that you should know, but most important here is the part about writing insert in C++.

insert() Needs to Handle the Item Already Being in the Tree

Your insert function should only add data to the tree if it isn't already there.

  • Cat speaking

    The code in the lesson just calls exists at the start to see if the item is in the tree. Is that what we should do?

  • LHS Cow speaking

    Yes, that's a nice simple way to deal with the issue.

  • Duck speaking

    But it's so inefficient—we traverse the tree twice, once to check and once to insert. It's obviously faster to just traverse the tree once.

  • LHS Cow speaking

    Careful—remember that you need to be very cautious about making efficiency claims. Checking before inserting doesn't change the asymptotic performance, which is \( \mathrm{O}(\mathit{height}) \). Whether a particular implementation approach makes a difference to practical execution times on a particular machine can only really be answered by experiment, and the results of those kinds of experiments can often be surprising. Just because you think one way is “obviously faster” doesn't mean it actually is.

  • RHS Cow speaking

    In this class, we value writing clear, obviously correct code. But if you really don't like calling exists first, you can try to write a version of insert that doesn't do that. We do also discuss that approach in another part of the lesson materials about implementation choices you can make.

  • Goat speaking

    I actually looked at the code you gave us in the lesson and it looks good to me. Can I just copy it?

  • LHS Cow speaking

    In this case, yes. But if you do, you need to include attribution. You can do that by adding a comment in your code that says something like “This code is based on the code from the CS 70 lesson materials”.

Let's Go!

Following the four steps of our development process (Plan, Write Tests, Implement, Test & Fix), implement the following member functions from the TreeStringSet class:

  • insert()
  • exists()

These functions are described in the TreeStringSet Specification.

Required Implementation Approach

Your implementations of these functions must be written recursively, using a helper function that operates on Nodes. Specifically, you must follow the tree algorithms discussed in the lesson materials.

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