Requirements:

In this sub-project, you will modify the class:

1. Lazy-deletion binary search tree: Lazy_deletion_tree.
2. Lazy-deletion binary search node: Lazy_deletion_node.

A lazy-deletion binary search tree is a binary search tree where erased objects are simply tagged as erased while the nodes themselves remain in the tree. Occasionally, a member function may be called to clean up (delete) all erased nodes at once. Almost all functions will be implemented by calling the corresponding function on the root node.

Runtime:

The run time of each member function is specified in parentheses at the end of the description. The variable n is the number of nodes in the tree while the variable h is the height of the tree. Because this is not a balanced tree, a sequence of poor insertions may result in a tree of height O(n).

Class Specifications:

---

Lazy_deletion_tree

Description

A class which implements a lazy-deletion tree. Types which are erased from the tree are simply tagged as being erased.

Member Variables

This class two member variables:

• A pointer to the root node, and
• A variable storing the number of non-erased objects in the tree.

Accessors

This class has seven accessors:

bool empty() const

Return true if the tree is empty (the size is 0). (O(1))

int size() const

Returns the number of nodes in the tree not including nodes tagged as erased. (O(1))

int height() const

Returns the height of the tree including nodes tagged as erased. (O(n))

bool member( Type const &obj ) const

Return true if the argument is in the tree and not tagged as erased and false otherwise. (O(h))

Type front() const

Return the minimum non-erased object of this tree by calling front on the root node. The object will be the first argument of a pair (*, true) returned by the node member function, and will throw an exception underflow if the second for (*, false) (the tree has size zero). Hint: What type of traversal will you need? Under what conditions do you continue searching, and under what conditions do you return? (O(n))

Type back() const

Return the maximum non-erased object of this tree by calling back on the root node. The object returned will be a pair of the form (*, true); return the first object. This member function may throw an underflow exception if the tree has zero size. (O(n))

void breadth_first_traversal() const

Perform a breadh-first traversal which prints the objects in the order in which they are visited in a single line (no end-of-line character). If an object is marked as erased, the string "x " is printed immediately following the object, otherwise a string containing a single space " " is printed after the object. You may use the Standard Template Library (STL) std::queue for the queue required for the traversal. For example, valid (ignoring the quotation marks) output may be "3 7x 4x 9 5x " (O(n))

Mutators

This class has four mutators:

bool insert( Type const & )

Insert the new object into the tree: If the object is already in the tree and not tagged as erased, return false and do nothing; if the object is already in the tree but tagged as erased, untag it and return true; if the object is not in the tree, create a new leaf node in the appropriate location and return true. If the root node is nullptr, this requires the creation of a new root node; otherwise, the corresponding function is called on the root node. (O(h))

bool erase( Type const & )

Removes the object from the tree: If the object is not already in the tree, return false; if the object is in the tree but tagged as erased, return false; if the object is in the tree and not tagged as erased, tag it as erased and return true. If the root node is nullptr, all that is done is that false is returned; otherwise, the corresponding function is called on the root node. (O(h))

void clear()

Delete all the nodes in the tree. (O(n))

void clean()

Delete all nodes tagged as deleted within the tree following the description found in the lazy-deletion node class. (O(n) if the height is Θ(ln(n)) but O(n²) in general)

Development and Testing

Before you begin coding, consider the lazy-deletion trees in Figure 1 where some nodes have already been marked as deleted (grayed out). Your most difficult task will be to write the clean() member function. Make sure that you know conceptually what you would do before you start coding. If you don't understand what you're doing, you won't be able to code it either.

Figure 1. Various examples of lazy-deletion trees.

These are not meant to be exhaustive in enumerating all possible situations or cases.