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() Must 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}) \).

  • Rabbit speaking

    Whether a particular implementation approach makes a difference to practical execution times on a particular machine can only really be explored 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.

  • LHS Cow speaking

    In this class, we focus on 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 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 must 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.

  • Horse speaking

    Whoa! There's way less guidance here than the previous parts of the assignment!

  • LHS Cow speaking

    Yes, that's intentional. By now, you should be familiar enough with the development process that you can apply it on your own. Plan, write tests, implement, test & fix.

  • Goat speaking

    Meh. I always ignored half the instructions anyway.

  • Cat speaking

    Just to be clear, we only need to implement these two functions right now, right? Not the whole class?

  • LHS Cow speaking

    That's right. You only need to implement insert and exists at this point. The other functions will be implemented in later parts of the assignment.

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