Description
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
….
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
I
B
D L S
F K P V Y
5- Find
6- FindMin
7- FindMax
8- LevelOrder
9- Exit
>8
I D L S B F K P V Y
————————————————————
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
L I S B D K P V Y
————————————————————
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
K D S B I P V Y
————————————————————
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
K S B I P V Y
————————————————————
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
I S B K V Y
————————————————————
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
S I Y B K V 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
> 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
S I Y B K O V 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
>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
S K Y I O V 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
>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
K S I O Y V
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.
Compressed File
• 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.
