Lab 07 Solution

Purpose:




The purpose of this lab is to implement a 2-3 tree in C++.




General Requirements:




In this lab, you are required to implement a 2 -3 tree using pointer implementation. Each node of the tree will have a value(s) and left, right, and middle pointers (if any), where the left pointer will point to its left subtree, the right pointer will point to its right subtree, and the middle pointer will point to its middle subtree (if any). Each node of a tree can be a 2-node or 3-node. You are to read in a collection of characters from a data file called data.txt. Duplicate values are not allowed in the 2-3 tree. You may hard code the file name if you wish. After building the structure, your program should ask the user to choose one of the options below:




------------------------------------------------------------

Please choose one of the following commands:

1- Insert




2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit




The 2- 3 tree should be implemented with an appropriate constructor and destructor. The rest of the methods should be implemented as follows:




IsEmpty() – Return true if the tree is empty, i.e., if the root node is null.



Insert(x) – Insert a value x into the tree at its appropriate position. Note that a node will have value(s) with lower priority in its left subtree and higher priority value(s) in its right subtree.



Delete(x) – Delete the value x from 2-3 tree if it is present, else throw an error message.



DeleteMin – Delete the character that occurs first in alphabetical order in the tree.



DeleteMax – Delete the character that occurs last in alphabetical order in the tree.



FindMin() – Retrieve the character that occurs first in alphabetical order in the tree.



FindMax() – Retrieve the character that occurs last in alphabetical order in the tree.



Find(x) – Find the character if present in the tree, otherwise throw an error message if not present in the tree.



LevelOrder() – Traverse the tree in level order and print all the elements.












Expected Results:




data.txt: D I Y L S B F K V P




We will insert these values, in the given order, into an initially empty 2-3 tree. We will use the terminal node optimization approach as given in your lecture notes.



















D
D I
I


I




D
Y
D
L
Y















I

….











D






L


S


















































































































B




F


K




P






V
Y










































Please note that you are not expected to show the 2-3 tree graphically in your output. This is just for your reference.




Now that you have built the 2-3 tree, these are the expected results of performing the various options on the 2-3 tree.




------------------------------------------------------------

Please choose one of the following commands:

1- Insert




2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

8

IDLSBFKPVY




------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

2

Enter character to be deleted

F




Delete was successful

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

8

LISBDKPVY




------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

2

Enter character to be deleted

L

Delete was successful

------------------------------------------------------------




Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

8

KDSBIPVY

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

2

D

Delete was successful

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

8

KSBIPVY




------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete




3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

2
P

------------------------------------------------------------

Please choose one of the following commands: 1- Insert




2- Delete

3- DeleteMin




4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit 8

ISBKVY




------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin




4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

2

Enter character to be deleted:

A

Delete was unsuccessful.

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin




4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

1

Enter a character to be inserted:

Z

Insert was successful




------------------------------------------------------------

Please choose one of the following commands:




1- Insert




2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

8

SIYBKVZ

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete




3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

1

Enter character to be inserted

K

Insert was unsuccessful

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin




4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

1

Enter character to be inserted

O

Insert was successful

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete




3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

8

SIYBKOVZ

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin




4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

5

Enter character to be found

N

Character not found in tree

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax




5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

5

Enter character to be found

S

Character found in tree

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin




4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

6

B

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax




5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

7

Z

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax




8- LevelOrder

9- Exit

3

Delete was successful

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder




9- Exit

8

SKYIOVZ




------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder




9- Exit

4

Delete was successful

------------------------------------------------------------

Please choose one of the following commands:




1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

8

KSIOYV




Please choose one of the following commands:

1- Insert

2- Delete

3- DeleteMin

4- DeleteMax

5- Find

6- FindMin

7- FindMax

8- LevelOrder

9- Exit

9




Done!







Submission:




Follow the conventions below to facilitate grading:




Source Code




Place all your source files (*.cpp, *.hpp) and input files in a single folder with no subfolders.



Name your folder using the convention Lastname_LabX (e.g., Smith_Lab07).



Include a functioning Makefile inside the folder. (The makefile should also include the clean command.)



Verify that your code runs on the Linux machines in the lab.



Compress using .zip, .rar, or .tar.gz.



Name your file using the convention Lastname_LabX (e.g., Smith_Lab07.zip).
Email




Use the following subject for your email: Lastname_LabX (e.g., Smith_Lab07).



Send you code to l290w868@ku.edu if you are in one of Lei’s sections or, to dhwanipandya1401@ku.edu if you are in one of Dhwani’s sections.



Anytime you have a question about the lab, put the word question in the subject of the email.