In this assignment, you will be implementing a 2-3 tree to handle the database for a provider of streaming movies. Nodes will store the titles of the movies. The title will be stored as a string and titles may consist of multiple words. Include AT LEAST the following functions for your 2-3 tree. For each operation I have included the function prototype that you must use so that your tree will interface with the main test file. This is by no means an exhaustive list of the functions that you will be writing.

Required Functions

Print the tree in the following manners. When printing a value, print the string followed by a , and 1 space. You must follow these guidelines exactly! For example: Aliens, The Lord of the Rings, Kill Bill,

• void preOrder( ) const: Traverse and print the tree in preorder notation.

• void inOrder( ) const: Traverse and print the tree in inorder notation

• void postOrder( ) const: Traverse and print the tree in postorder notation

• void insert(const string &): Insert an item into the 2-3 tree. Be sure to maintain the 2-3 tree properties.

• void remove(const string &): Remove a specified item from the tree. Be sure to maintain the 2-3 tree properties. Some removes can be resolved in multiple ways. To make sure that your output matches mine exactly, follow the examples listed in the notes below. If an ambiguous case arises that I have not specified, ask me and I will make the specification.

• bool search(const string &) const: Search for a specified item in the tree. Return true if the item exists in the tree. Return false if the item does not exist.

Provided files

All files and notes listed below can be accessed within my CS 14 c9 files: https://ide.c9.io/krism/cs14 They are now also in a google drive: 23Tree Files

The following skeleton code has been provided. You will need to add your own member functions and variables to the classes.

• Node.h: contains the Node class definition. You may add additional variables and functions to this class but you MAY NOT add another Node * or another string variable. You will lose points if you add either of these types of variables.
• Tree.h: You may add additional variables and functions to this class but you MAY NOT add another Node * or another string variable. You will lose points if you add either of these types of variables.
• tests_all.cpp: A main function used for testing all of the different insert and remove scenarios.
• tests_simple.cpp: A main funtion used for some of the simple tests. These tests will help you with the checkpoint turnin.

Provided notes

For the majority of the main testing cases, I have provided notes that illustrate what the tree is doing exactly. These notes will show you how to perform inserts and removes that can be resolved in multiple ways. You must follow the illustrations in these notes exactly or else your output will not match the zyBook expected output. Notice that I did not write out the complete titles for each movie in the tree. Instead, each movie has been assigned a letter to represent that movie. You can look at the top of testsall.cpp or testssimple.cpp files for letter-to-movie substitutions.

• Notes for tests 1 through 7: Page 1 (page1.jpg)
• Notes for tests 8 through 15: Page 1b (page1b.jpg), Page 2b (page2b.jpg)
• Notes for tests 16 through 21: Page 1 (page1.jpg), Page 2 (page2.jpg), Page 3 (page3.jpg), Page 4 (page4.jpg)
• Notes for tests 22 through 25: Page 1c (page1c.jpg)

Suggestions to follow while coding

• It is very important for you to follow a modular programming style for this assignment. Write functions for anything and everything that can be easily and logically grouped into a function. You should have many private helper functions.

• Make sure you have at least tests 1 - 15 working before moving on to the more difficult inserts and removals. You will get the majority of points for completing tests 1 - 15.