CS300  -  Homework #2 - Notebook - Solved

In this homework, you will implement two “Notebooks” by using the AVL Search Tree and the Binary Search Tree (BST). Additionally, you will display the speed of some of the operations on these tree data structures that are used for the implementation. Each “Notebook” will have a nested tree structure, which will be explained in more detail in the rest of the documentation.

 

Although each Notebook tree will have a separate implementation, they will store the same data and will perform the same operations. Basically, the only difference between the Notebooks will be the data structures that are going to be used for the implementation. Each Notebook will contain multiple sections and each section will have multiple items which will store the information inside.

 

A notebook will have a nested structure as follows:

 

❏  Notebook 

May have one or many section/s.

❏     Section

Will have a title.

May have one or many item/s.

❏     Item

Will have a title.

Will have information.

 

Example Notebook:

 



Movies

The Holy Mountain-7.9

I Lost My Body-7.6

Phonebook

Gulsen-09990000099

Alp-09998765432

Furkan-09876543210

Serra-09898989898

 

 

As seen in the example above, a notebook is a tree of sections. Each section has got a title string and a tree of items. Each item has a title string and an information string.

There cannot be two sections with the same title inside the same notebook. Also, there cannot be two items with the same title inside the same section.

 

 

BST and AVL Tree

 

You are going to implement a BST class and an AVL Tree class. Which will get used separately to implement two different notebooks that will perform the same operations over the same data. You CANNOT USE VECTOR OR ARRAY to implement the notebooks. Also, you cannot use a BST inside an AVL Tree and vice versa. In other words, there will be two notebooks, one of them will be implemented by using nested AVL Trees and the other will get implemented by using the nested BSTs only.

 

Both the BST and the AVL Tree classes should be reusable for different types, classes, etc. Thus, both the BST and AVL Tree classes MUST be template-based classes.

 

Use the “title” properties of the section and the item to compare the nodes inside the trees.

 

 

Program Flow

 

❏     Initializing the notebooks

At the very beginning of the program, you should create two notebooks (one by using the BST, other by using the AVL Tree). 

 

Then, your program will read a text file that contains the section and item data of the notebook. Your program will insert the data into the notebooks accordingly.

 

Your program will display the elapsed insertion time of each section for both of the notebooks. Then the program will direct to the main menu.

 

 

❏     Main menu

On the main menu, there will be 6 options. The user will enter an input between [1-6] then the program will perform the commands on both notebooks accordingly. These options are:

1.      Display the sections (AVL)

Your program should perform an inorder traversal over the AVL notebook and print the section titles in ascending order (alphabetically).

2.      Display the sections (BST)

Your program should perform an inorder traversal over the BST notebook and print the section titles in ascending order (alphabetically).

3.      Select a section

The program will get a section title name from the user then it will search for the section with the same title, both in the AVL and BST notebooks. 

If there exists no such section your program will display an error. Else it will direct to the section menu to perform operations on the selected section. 

 

4.      Add new section

Get a title input from the user. If a section with the given title already exists in the notebook, display an error message. Else, create a new section with that title and insert it into the notebooks. 

5.      Delete a section

Get a title input from the user. If a section with the given title does not exist in the notebook, display an error message. Else, remove the section with that title from the notebooks.

6.      Exit

Terminate the program.

 

 

❏     Section menu

At option 3 of the main page, if the title of any section matches with the input from the user, the program should land on the section menu page to perform operations on the selected section.

 

On the main menu, there will be 7 options. The user will enter an input between [1-7] then the program will perform the commands on both notebooks accordingly. Options are:

 

1.      Display the items (AVL)

For the selected section of the AVL notebook:

Your program should perform an inorder traversal over the items tree of the section and print the item titles in ascending order (alphabetically).

2.      Display the items (BST)

For the selected section of the BST notebook:

Your program should perform an inorder traversal over the items tree of the section and print the item titles in ascending order (alphabetically).

3.      Display the information of an item

Get an item title input from the user. If an item with the given title does not exist in the notebook, display an error message. Else, display the information of the matching item.

 

Note: Although, you should make a query on both the AVL notebook and the BST notebook you can display the matching item information once. Since, if your program works correctly, matching item information of the AVL notebook and the BST notebook will be the same.

 

In both cases, display the elapsed query/insertion time for the AVL notebook and the BST notebook. 

Display the elapsed query time.

 

4.      Add a new item

Get an item title input from the user. If an item with the given title already exists in the section, display an error message. Else, create a new item with that title and insert it into the selected section. 

In both cases, display the elapsed query/insertion time.

5.      Update the information of an item:

Get an item title input from the user. If an item with the given title does not exist in the section, display an error message. Else, get the new information from the user and update the information of the item accordingly. 

Display the elapsed query/update time.

6.      Delete an item

Get an item title input from the user. If an item with the given title does not exist in the section, display an error message. Else, remove the item with that title from the section. Display the elapsed deletion time.

7.      Return to main menu

Go back to the main menu.

 

Text File

As mentioned before we have provided initial data to fill the notebooks at the beginning of the program. You should read the data from a text file (.txt extension) and insert it into the notebooks accordingly.

 

The text file will contain the following 3 sections:

 

-          Courseworks: contains 5 non-sorted items.

-          Movies: contains +90000 non-sorted items.

-          Phonebook: contains +6000 sorted items.

 

❏     Data format

If the first character of a line is not a ‘-‘ (dash), it is the title of a new section. Until the occurrence of a new section, as long as a new line starts with a dash it denotes the item of the given section. Each item line contains exactly two dashes. The first one denotes that it is an item line and the second one separates the item title from the item info.   

 

So, a text file with notebook data inside it will look like the following:

Section title 1

-item title 1-item info 1

-item title 2-item info 2

-item title 3-item info 3

Section title 2

-item title 1-item info 1

-item title 2-item info 2

 

 

Example text file:

 



Movies

-The Holy Mountain (1973)-7.9

-Climax-7

-Midsommar-7.6

 

 

Elapsed Time

 

You should display the elapsed time of the notebook operations. For that purpose, you can use the C++ built-in library chrono. You can include the library by using #include <chrono>.

 

You are recommended to use chrono::high_resolution_clock to obtain accurate results.

Documentation: https://en.cppreference.com/w/cpp/chrono/high_resolution_clock 

 

Here is an example to get the time duration of a foo() function in microseconds:

 


 

Between the start and the end clocks, you should only include the member functions of the trees (insert, delete, update, etc.) and exclude the rest of the code (getline, loops, arithmetic operations, etc.).

 
Sample Run

 

Welcome to the the Notes

 

Section "Courseworks" has been inserted into the AVL notebook.

[AVL] Elapsed time: 15 microseconds

Section "Courseworks" has been inserted into the BST notebook.

[BST] Elapsed time: 7 microseconds

 

Section "Phonebook" has been inserted into the AVL notebook.

[AVL] Elapsed time: 18236 microseconds

Section "Phonebook" has been inserted into the BST notebook.

[BST] Elapsed time: 3864642 microseconds

 

Section "Movies" has been inserted into the AVL notebook.

[AVL] Elapsed time: 300933 microseconds

Section "Movies" has been inserted into the BST notebook.

[BST] Elapsed time: 353231 microseconds

  

MENU

Please enter an input between [1 - 6]:

1- Display the sections [AVL]

2- Display the sections [BST]

3- Select a section

4- Add new section

5- Delete a section

6- Exit

Input: 1

 

*****

Courseworks

Movies

Phonebook

*****

 

Input: 2

 

*****

Courseworks

Movies

Phonebook

*****

 

Input: 3

Enter the title of the section: Cour

Invalid title!

 

Input: 3

Enter the title of the section: Courseworks

 

Selected section -> Courseworks

Please enter an input between [1 - 7]:

1- Display the items [AVL]

2- Display the items [BST]

3- Display the information of a item

4- Add new item

5- Update the information of a item

6- Delete an item

7- Return to main menu

Input: 1

 

*****

CS300

CS303

CS408

ENS492

SPS303

*****

 

Input: 2

 

*****

CS300

CS303

CS408

ENS492

SPS303

*****

 

Input: 3

Enter the title of the item: CS100

[AVL] Elapsed time: 8 microseconds

[BST] Elapsed time: 2 microseconds

Invalid title.

 

Input: 3

Enter the title of the item: CS300

[AVL] Elapsed time: 6 microseconds

[BST] Elapsed time: 0 microseconds

the homework is due Sunday

 

Input: 4

Enter a title for the item: CS303

Item "CS303" already exists in the "Courseworks".

 

Input: 4

Enter a title for the item: CS600

Enter a description for the item: huh?

[AVL] Elapsed time: 14 microseconds

[BST] Elapsed time: 3 microseconds

The new item "CS600" has been inserted.

 

Input: 5

Enter the title of the item: CS999

[AVL] Elapsed time: 5 microseconds

[BST] Elapsed time: 2 microseconds

Item "CS999" does not exist in the "Courseworks".

 

Input: 5

Enter the title of the item: CS300

[AVL] Elapsed time: 6 microseconds

[BST] Elapsed time: 0 microseconds

Enter the new information: great

The content CS300 has updated.

 

Input: 3

Enter the title of the item: CS300

[AVL] Elapsed time: 7 microseconds

[BST] Elapsed time: 1 microseconds

great

 

Input: 6

Enter the title of the item: CS123

Item "CS123" does not exist in the "Courseworks".

 

Input: 6

Enter the title of the item: CS300

[AVL] Elapsed time: 2 microseconds

[BST] Elapsed time: 2 microseconds

The item "CS300" has been deleted.

 

Input: 1

 

*****

CS303

CS408

CS600

ENS492

SPS303

*****

 

Input: 2

 

*****

CS303

CS408

CS600

ENS492

SPS303

*****

 

Input: 7

 

MENU

Please enter an input between [1 - 6]:

1- Display the sections [AVL]

2- Display the sections [BST]

3- Select a section

4- Add new section

5- Delete a section

6- Exit

Input: 4

Enter a title for the section: Courseworks

Section "Courseworks" already exists.

 

Input: 4

Enter a title for the section: Colors

The new section "Colors" has been inserted.

 

Input: 3

Enter the title of the section: Colors

 

Selected section -> Colors

Please enter an input between [1 - 7]:

1- Display the items [AVL]

2- Display the items [BST]

3- Display the information of a item

4- Add new item

5- Update the information of a item

6- Delete an item

7- Return to main menu

Input: 1

 

*****

*****

 

Input: 2

 

*****

*****

 

Input: 4

Enter a title for the item: Red

Enter a description for the item: Fav

[AVL] Elapsed time: 4 microseconds

[BST] Elapsed time: 1 microseconds

The new item "Red" has been inserted.

 

Input: 1

 

*****

Red

*****

 

Input: 2

 

*****

Red

*****

 

Input: 7

 

MENU

Please enter an input between [1 - 6]:

1- Display the sections [AVL]

2- Display the sections [BST]

3- Select a section

4- Add new section

5- Delete a section

6- Exit

Input: 1

 

*****

Colors

Courseworks

Movies

Phonebook

*****

 

Input: 2

 

*****

Colors

Courseworks

Movies

Phonebook

*****

 

Input: 5

Enter the title of the section: Course

Section "Course" does not exist.

 

Input: 5

Enter the title of the section: Courseworks

The section has been deleted.

 

Input: 1

 

*****

Colors

Movies

Phonebook

*****

 

Input: 2

 

*****

Colors

Movies

Phonebook

*****

 

Input: 3

Enter the title of the section: Phonebook

 

Selected section -> Phonebook

Please enter an input between [1 - 7]:

1- Display the items [AVL]

2- Display the items [BST]

3- Display the information of a item

4- Add new item

5- Update the information of a item

6- Delete an item

7- Return to main menu

Input: 3

Enter the title of the item: Aada

[AVL] Elapsed time: 2465 microseconds

[BST] Elapsed time: 0 microseconds

0016839979200

 

Input: 3

Enter the title of the item: Zyrie

[AVL] Elapsed time: 2302 microseconds

[BST] Elapsed time: 2276 microseconds

0017707501460

 

Input: 5

Enter the title of the item: Zyrie

[AVL] Elapsed time: 2410 microseconds

[BST] Elapsed time: 2327 microseconds

Enter the new information: 000000

The content Zyrie has updated.

 

Input: 6

Enter the title of the item: Kadeem

[AVL] Elapsed time: 6 microseconds

[BST] Elapsed time: 878 microseconds

The item "Kadeem" has been deleted.

 

Input: 4

Enter a title for the item: Zxxy

Enter a description for the item: ???

[AVL] Elapsed time: 12 microseconds

[BST] Elapsed time: 2143 microseconds

The new item "Zxxy" has been inserted.

 

Input: 7

 

MENU

Please enter an input between [1 - 6]:

1- Display the sections [AVL]

2- Display the sections [BST]

3- Select a section

4- Add new section

5- Delete a section

6- Exit

Input: 3

Enter the title of the section: Movies

 

Selected section -> Movies

Please enter an input between [1 - 7]:

1- Display the items [AVL]

2- Display the items [BST]

3- Display the information of a item

4- Add new item

5- Update the information of a item

6- Delete an item

7- Return to main menu

Input: 3

Enter the title of the item: Zingaresca

[AVL] Elapsed time: 31739 microseconds

[BST] Elapsed time: 2 microseconds

6.6

 

Input: 5

Enter the title of the item: Aurora

[AVL] Elapsed time: 30734 microseconds

[BST] Elapsed time: 2 microseconds

Enter the new information: cool

The content Aurora has updated.

 

Input: 6

Enter the title of the item: Redskin

[AVL] Elapsed time: 8 microseconds

[BST] Elapsed time: 1 microseconds

The item "Redskin" has been deleted.

 

Input: 7

 

MENU

Please enter an input between [1 - 6]:

1- Display the sections [AVL]

2- Display the sections [BST]

3- Select a section

4- Add new section

5- Delete a section

6- Exit

Input: 6

 

Terminating...

Program ended with exit code: