TreeSet<T> Specifications

This page describes the interface and encoding for TreeSet<T> and TreeSet<T>::const_iterator, and the encodings for their implementations, as the TreeSet<T> and TreeSet<T>::ConstIter classes.

Your implementation must support all the functionality described on this page, including meeting the specified complexity. You may not change the names of anything in the interfaces, nor may you change the encodings. However, you will find it useful (and necessary!) to write private helper member functions, but those functions are not part of the interface and are not described in this document.

Interface

enum bst_style { LEAF, ROOT, RANDOMIZED };

The TreeSet<T> Interface

Your tree class must be named TreeSet<T> and must support the following operations:

• A default constructor, which creates an empty LEAF tree.

• An explicit parameterized constructor that takes one argument: a bst_style (LEAF, ROOT, or RANDOMIZED)

  • You'll add this constructor in Phase 4.

• A parameterized constructor that takes two arguments: a bst_style (LEAF, ROOT, or RANDOMIZED) and an int64_t that will be used to seed a random-number generator.

  • You'll add this constructor in Phase 7.

• A destructor

• The copy constructor and assignment operator should be disabled.

• A clear member function that

  • Takes no arguments.
  • Removes all items from the TreeSet<T>.
  • Requires \(\Theta(n)\) time.
  • After calling myTreeSet.clear, any iterators that refer to myTreeSet are no longer valid.

• A swap member function that

  • Takes a reference to another TreeSet<T>.
  • Doesn’t return anything (but swaps the contents of the two trees).
  • Requires \(\Theta(1)\) time.
  • After calling swap, any iterators that refer to either tree are no longer valid.

• A size member function that

  • Takes no arguments.
  • Returns the number of values in the TreeSet<T>, as a size_t.
  • Requires \( \Theta(1) \) time.
  • Can be called on a read-only tree (i.e., const at the end)

• An insert member function that

  • Takes a T by constant reference
  • Doesn’t return anything (but inserts the item into the tree).
    • It is okay to call insert with a T value that is already in the tree. In that case the item is not inserted again.
  • How it inserts the given item depends on the tree's type (LEAF, ROOT, or RANDOMIZED), as described above.
  • Takes \( \mathrm{O}(\mathit{height}) \) time (and \( \mathrm{O}(\log n) \) expected time when the style is RANDOMIZED).
  • After calling insert, any iterators that refer to the tree are no longer valid.
  • You'll add support for ROOT insertion in Phase 5 and for RANDOMIZED insertion in Phase 7.

• An exists member function that

  • Takes a T by constant reference
  • Returns a bool indicating whether the item was found in the tree.
  • Takes \( \mathrm{O}(\mathit{height}) \) time (and \( \mathrm{O}(\log n) \) expected time when the style is RANDOMIZED).
  • Can be called on a read-only tree (i.e., const at the end)

• A lower_bound member function that

  • Takes a T by constant reference
  • Returns a const_iterator to the first element in the tree that is not less than the given value (i.e., the smallest element e such that !(e < value)). If all elements in the tree are less than the given value, returns an iterator equal to end.
  • Takes \( \mathrm{O}(\mathit{height}) \) time (and \( \mathrm{O}(\log n) \) expected time when the style is RANDOMIZED).
  • Can be called on a read-only tree (i.e., const at the end)
  • You'll add this function in Phase 3.

• A height member function that

  • Takes no arguments.
  • Returns an int representing the height of the tree
    • An empty tree has height -1 (not 0).
  • Requires \( \Theta(n) \) time.
  • Can be called on read-only trees (i.e., const at the end)

• An averageDepth member function

  • Takes no arguments.
  • Returns a double representing the average depth of the tree
    • An empty tree has average depth -1 (not 0.0/0).
  • Requires \( \Theta(n) \) time.
  • Can be called on a read-only tree (i.e., const at the end)

• An == and != member functions for tree equality.

  • Returns a bool with the result of the test
    • Two trees are equal if they contain the same values (no matter what tree shape!).
  • Requires \( \Theta(n) \) time.
  • Can be called on read-only trees (i.e., const at the end and on the argument)

• A printToStream member function that

  • Takes an ostream&.
  • Prints the tree out to that stream (the required format was described in the previous homework).
  • Returns the same ostream& it was passed.
  • Can be called on a read-only tree (i.e., const at the end)

• A printSizesToStream member function that

  • Takes an ostream&.
  • Prints the tree's node sizes out to that stream (the required format is described in Phase 5).
  • Returns the same ostream& it was passed.
  • Can be called on a read-only tree (i.e., const at the end)
  • You'll add this function in Phase 6.

• A showStatistics member function that

  • Takes an ostream&.
  • Prints statistics about the tree to that stream (the required format was described in the previous homework).
  • Returns the same ostream& it was passed.
  • Can be called on a read-only tree (i.e., const at the end)

• A begin member function that

  • Takes no arguments.
  • Returns a const_iterator that is set to the first (least) node of the tree.
  • Requires \( \mathrm{O}(\mathit{height}) \) time (and \( \mathrm{O}(\log n) \) expected time when the style is RANDOMIZED).
  • Can be called on a read-only tree (i.e., const at the end).

• A end member function that

  • Takes no arguments.
  • Returns a const_iterator that refers is set “past the end” of the tree (i.e., past the greatest element).
  • Requires \(\Theta(1)\) time.
  • Can be called on a read-only tree (i.e., const at the end).

You will likely want to define additional (static) private member functions (e.g., recursive helper functions that work on Node*s), but since those are not part of the interface, they are not included in this specification.

The TreeSet<T>::const_iterator Interface (and ConstIter Class)

The TreeSet<T> should provide a public const_iterator type that is an alias for a (private) class called ConstIter. This iterator traverses the tree in sorted order.

This ConstIter class should provide at least the following operations:

• A default constructor (either written or intentionally chosen as the synthesized default constructor).

• A copy constructor (either written or intentionally chosen as the synthesized copy constructor).

• An assignment operator (either written or intentionally chosen as the synthesized assignment operator).

• A destructor (either written or intentionally chosen as the synthesized destructor)

• A member function called operator* that returns a const T& that doesn't change the iterator itself (i.e., a const member function)

• A pre-increment operator (operator++) that advances to the next tree item in order (or goes past the end if we were on the last item) returns a reference to itself (i.e., a ConstIter&).

• An equality test (operator==) and an inequality test (operator!=) which each return a bool. When comparing two iterators, we will assume that the iterators refer to the same TreeSet<T> object. (If they don't, the behavior will be undefined). We therefore only need to check that the iterators are also at the same point in their traversal of the tree. It should work on const const_iterators.

Your TreeSet<T> will hold Ts, so your ConstIter should define the following values to interface nicely with iterator-related functions in the C++ standard library:

using value_type        = T;
using reference         = const value_type&;
using pointer           = const value_type*;
using difference_type   = ptrdiff_t;
using iterator_category = std::forward_iterator_tag;

You may want to define additional private member functions, but since those are not part of the interface, they are not included in this specification.

Top-Level Functions

You should also provide a top-level (not member) function operator<< that defines how to print a TreeSet<T>. It takes as arguments an ostream& and a const TreeSet<T>&; it returns an ostream&. That operator will call the public printToStream member function of the TreeSet<T> class.

Private Encoding

We will not test the private encoding of your TreeSet, but we recommend the following data members:

• A Node* that that points to the tree’s root Node.
• A bst_style that stores the type of insert used by your tree: LEAF, ROOT, or RANDOMIZED.
  • You will add this data member in Phase 4.
• A RandUInt32 that stores an instance of the Random Number Generator class we’re providing for you.
  • You will add this data member in Phase 7.

…where RandUInt32 is a class we’re providing to make it easier to work with random numbers in C++. It is available on the CS 70 server when you include <cs70/randuint32.hpp>.

The Private Node Struct

Inside your TreeSet<T> class, you will need to represent the nodes of the tree (a TreeSet<T> is not itself a tree node—it is the overarching object that contains tree nodes but also has other information, such as a count of the number of nodes).

Internally, our encoding for trees requires that each tree node stores exactly (and only) the following information:

• The value stored at that tree node (a T).
• The number of nodes in this subtree (including this node).
  • You will add this data member in Phase 6.
• A pointer to the root of the left subtree (i.e., another node) or nullptr if there is no left subtree.
• A pointer to the root of the right subtree (i.e., another node) or nullptr if there is no right subtree.

(As implied by these requirements, your tree nodes may not have any “parent” pointers going backwards up the tree.)

Nodes are “just data”. They are manipulated entirely by code in the TreeSet<T> class. You may not implement your nodes as a class.

(When logged in, completion status appears here.)