Overview

In the early 20th Century, before the days of online shopping websites, there were catalogues such as the Sears catalogue that innovated early mail-order of general goods to places, where it would be otherwise difficult to obtain such items. In such a system, there is a catalogue customers can order items from, and then any items available can be shipped out. For the simplicity of our assignment, it will be presume prices are not relevant (and hence, are not encoded or represented here).

Suppose we want to manage some products in a basic dictionary, but with a computer! We will do so in this assignment using a binary search tree (BST), specifically permitting it to be an AVL tree (using the appropriate functions). We want to learn some details at times, such as:

❼ What might be the product with the highest quantity?

❼ A log of all the items, in order by their product keys.

❼ The ability for a user (programmer) to search, add, change, and remove records.

1914 Sears Catalogue, p .24, https://www.historyonthenet.com/authentichistory/1898-1913/3-consume-leisure/6-Consumerism/1914_Sears_Housewares/index.html.

You will in C++:

❼ Implement an Ordered Dictionary using a BST.

❼ Implement the rotation-based operations of an AVL tree.

❼ Implement tree traversals to solve problems.

The specifications of the assignment start on Page 2.  You are provided several classes.  The functioning code will be used to partially grade your work.

Learning Objectives

❼ Implement a variant of an ordered dictionary, using a binary search tree.

❼ Translating the AVL-tree-based operations into C++.

❼ Implementing tree-based operations.

❼ Tree traversals being applied to solve problems on a BST.

Classes to Implement, Other Details

In this assignment you must implement the class AVLTree, your code will be contained in files you will create called AVLTree .cpp. You will be provided header files for all classes. You must write all remaining code yourself. Make sure to include all member functions in this file, and if you are unable to complete all the member functions, just make it so those functions match what is required (e.g. if it returns a pointer of a given type, return nullptr).

The program that uses all our classes is AVLTest .cpp, which has no code to be completed within

it.  It is highly encouraged to build your own trees using the code, and testing it carefully; draw what the trees might look like in your tests, to see if you understand what is happening with each operation of the tree. You will not be handing in any of this, only AVLTree .cpp.

I will expect you to know how to compile C++ programs and understand C++. Please compile your code using g++. Presume input data being fed to the program indeed matches the parameters of methods.

Please study the Product and the BSTNode classes. Both play an integral role in this assignment. The former represent products in the catalogue (our ordered dictionary), and the latter represent the nodes for our BST (whose data is a product).  The nodes are structured as per the Linked Binary Tree representation from class, and include an extra attribute for its height (that if updated appropriately, represent the height of a node). In this assignment, null refers to nullptr.

Class AVLTree (BST methods)

We are implementing a variant of an ordered dictionary, using a binary search tree.  We are rep- resenting the binary search tree as per the linked-based implementation shown on Page 107 of the notes.  Each node is of type BSTNode, where it has as data a pointer to a Product object, a left child, a right child, a parent node, and a height (which is represented, as per the AVL tree, which will not be relevant until later). Review the BSTNode class and Product class to better understand how the nodes and products relate. You will be implementing functions found in AVLTree .h.

The following are the instance variables of this class:

❼ BSTNode*  root: The root of the binary search tree. The BST is created, the root should be

a leaf node. There are few different constructors for a BSTNode, look for the most appropriate one here.  Do not set the root to be null, this is not how we are representing the BST (this is another way to represent the BST), as per lecture.

❼ int numRecords:  The number of records (Product objects) in the binary search tree.  Note

this does not count the leaf nodes (leaf nodes contain no data).

You must implement all the following private methods (these are a subset of all private methods in AVLTree .h):

1. BSTNode*  AVLTree::get(BSTNode*  r,  int  key): Implement the recursive get function from class.  Remember that the BST is ordered by the keys of Product objects; each node has a pointer to a Product object. This function is called by a public driver method (later in this section).

2. bool  AVLTree::put(BSTNode*  r,  Product* prod) :  Implement the recursive put function from class, make sure the number of records is incremented in the appropriate place.  Note that here we are passed a pointer to a Product object to insert into the ordered dictionary, should its key be unique. Remember that nodes have multiple attributes (their parent, left and right attributes), make sure to update all of these appropriately. This function is called by a public driver method (later in this section).

3. BSTNode*  AVLTree::remove(BSTNode*  r,  int  key) : Implement the recursive remove from class, where instead it returns the node where the deleted node used to be (in class, we gave the node you are returning a name, c′ in the pseudocode (Page 113)). If no record with key is found, throw  NoKeyException(). Delete the node and its data (the Product object).

Ensure the attributes of nodes involved appropriately are updated, or parts of the BST’s structure may be lost or incorrect.  Do not forget to decrement the size of the dictionary. Which of the two cases makes more sense to decrement the number of records?  This is for you to figure out.

4. BSTNode*  AVLTree::smallest(BSTNode*  r) :  Implement the smallest function from class. It returns the node containing the smallest key (if it exists, if not null is returned).  This function is called by a public method (later in this section).

5. void  AVLTree::sortRec(BSTNode*  r,  std::vector&  sortedList) :  A recur- sive inorder traversal of the tree, from the subtree of r .  In this method, a vector is passed around as the tree is visited.  Only apply the push back function for the vector on the data of the internal nodes, not the leaf nodes (which have null as their data).  The vector, if the BST is implemented properly, will contain all the records of the dictionary in sorted order, upon being called (by its driver method, given later) upon at the root of the BST.

6. Product*  AVLTree::highestQuantityRec(BSTNode*  r) :   A  recursive  function that  com- putes,  given a BSTNode r the product object with the highest quantity  (not its key,  nor its name) among the subtree of r . If r is a leaf return null .

7. void  AVLTree::deleteTree(BSTNode*  r) : Delete all the data in the tree, rooted at node r . Use a post-order traversal to visit every node and delete both the data (the actual Product object) and the node itself.  Remember that when using the delete keyword, calling it on a pointer variable will free the memory of the Product object.  Remember that the leaf nodes contain no record.

Next, you must implement the following public methods (these are a subset of all public methods in AVLTree .h):

1. AVLTree::AVLTree(): A constructor that creates an empty BST, with no records.

2. AVLTree::∼AVLTree(): It calls the function deleteTree. It must delete all the data in the tree, this includes the Product objects being pointed at.

3. Product*  AVLTree::get(int  key): The get operation, it returns a Product object with the key if it exists (and null otherwise).  Call the recursive get function at the root with the key.  Remember that if the search fails, it may return null, so do not get data from null immediately.

4. void  AVLTree::put(Product* prod):  A put operation specifically in a BST (not an AVL tree), that will insert the record (product) provided into the dictionary if there is no duplicate product key. Call the recursive put method at the root with prod. If there is a duplicate key, throw  DuplicateKeyException().

5. void  AVLTree::remove(int  key):   Removal/deletion  in  a  BST  specifically  (not  an AVL tree).  Remove the record with key.  Call the recursive function remove at the root with key.

6. Product*  AVLTree::smallest(): Return the product with the smallest key (and null, if it has no records). Call the method smallest from the root, and use its result.

7.  int  AVLTree::size(): Return the number of records in the dictionary (this is not the number of nodes).

8. bool  AVLTree::isEmpty(): Returns true if there are no records (products) in the dictionary.

9.  std::vector  AVLTree::treeSort() : Return a vector that contains all the prod- ucts in order of their keys (smallest to largest). Create a vector using std::vector myTreeElements, then call the recursive method that performs the in-order traversal at the root where myTreeElements is used.

10. Product*  AVLTree::highestQuantity() :  Returns the product with the highest quantity. Call the recursive function highestQuantityRec from the root.  If there are no records, it should return null .

11. void  AVLTree::updateProductName(int  key,  std::string newName) : Updates the name of a product with key to newName, if it exists.

ADD THE FOLLOWING FUNCTION TO YOUR CODE: Please include the following function in your AVLTree .cpp file, it prints the tree using a level-order traversal. It may be helpful for you to help debug the tree.  Note that it prints, in level order, the node’s data with square brackets surrounding each record; leaf nodes will print  [null].  This function is based on the one described in lecture (see Page 109 of the lecture notes). Try to use the level-order traversal to help you draw the tree or check your work. Make sure you #include, so this function can use the standard library queue (it uses some names that differ from our ADT from class).  Do not modify this code once written into your final submission of the assignment.

//prints the  level ❂order traversal by its  keys

void AVLTree::printLevelOrderKeys(){

std ::queue treeQueue;

treeQueue.push(root);

std ::cout<<”[”;

while(!treeQueue.empty()){

BSTNode✯ node = treeQueue.front();//get the element at the front of queue

if (node❂>getData()==nullptr){

std ::cout<<”[null]”;

}

else{

std ::cout<<”[”< string(node ❂>getData()❂>getKey())<<”]”;

}

treeQueue.pop();//removes first element (in a queue)

if (node❂>getLeft()!=nullptr){

treeQueue.push(node ❂>getLeft());//enqueue left

}

if (node❂>getRight()!=nullptr){

treeQueue.push(node ❂>getRight());//enqueue right

}

}//while there is   still  a node

std ::cout<<”]”<

}

Ensure to #include all header files necessary for compilation, including AVLTree .h, DuplicateKeyException .h, and NoKeyException .h.

Class AVLTree (AVL tree methods)

The next part of the assignment is implementing methods that complete the remainder of the AVLTree class.  These functions are specifically those related to an AVL tree.  For simplicity, both the BST methods and AVL tree methods are together under one class.  If one uses only the put and remove operations for inserting and removing data, it behaves (only) like a BST; we need to implement the AVL tree specific versions of these that maintain the heights at the nodes and ensure the height of the tree remains logarithmic.

There are some private methods that have been provided to simplify the implementation of the AVL tree.  If you choose to not use any of them, just include the functions in the AVL .cpp

file regardless, but leave them empty (and return nullptr for any).  There are three specifically provided to you in the class that fall into this category:

❼ BSTNode*  AVLTree::taller(BSTNode*  x,bool  onLeft) :  Checks the children of a node x

and returns the one that is taller.  That is, return the left or right child of x that has the larger height.

On a tie (both the left and right child have the same height), it must select the direction (left/right) that is the same as from its parent. If onLeft is true, then x was the left (taller) child of its parent, and if false it was the right (taller) child of its parent.

❼ BSTNode*  AVLTree::rotate(BSTNode*  x) : This is a simple rotation (a left rotation or right

rotation) as discussed in class, i.e. rotate(x).  Recall that this operation promotes x and demotes its parent.  Return x.  You should recompute the heights of nodes affected by the rotation appropriately here.  Note that this process may change what the root of the entire BST is, so make sure to make the appropriate update if necessary.

❼ BSTNode*  AVLTree::rotation(BSTNode*  z,  BSTNode*  y,  BSTNode*  x) : Given three nodes

(similar to our examples in class), z is the node where the imbalance occurs, y is the taller of the two children of z, and x is the taller of the two children of y, perform the appropriate rotation.  There exactly two cases, either a single rotation (LL or RR) or a double rotation (LR or RL). Return the root of the resulting subtree the rotation is applied to.

Below are the following private methods that need to be implemented (leave these empty if you do not implement them):

1. void  AVLTree::recomputeHeight(BSTNode* p) :  Recomputes the height of a node, as per the algorithm given in class.

2. void  AVLTree::rebalanceAVL(BSTNode*  v) : This method rebalances the tree and updates the heights of nodes as the method moves up to the root of the tree. This algorithm was given in class.  To implement this method, I strongly suggest making use of the above optional private methods to make implementation here less tedious.  Be careful how you reassign the pointers and data for attributes of nodes.   Also make sure the heights of adjusted nodes are recomputed so that the heights of nodes are maintained, it must not recompute the heights of the entire tree.

Implement the following public methods (if you only implement the BST methods, you may leave these empty):

1. void  AVLTree::putAVL(Product* prod):  Insert a new record (product) prod into the or- dered dictionary as per an AVL tree  (it is not the same as put in the previous section). The algorithm is based on the one presented in class (that uses the appropriate put and get functions), except throw the DuplicateKeyException if a duplicate key is attempted to be inserted into the dictionary. Rebalance, if necessary by calling rebalanceAVL.