Australia
UK
USA
- Case StudyHelp.com
- Sample Questions
COSC 2007 Data Structures II
2-3 Search Tree
2-3 trees are data structures commonly used to implement ordered lists of records(or tables). A 2-3 tree is a tree satisfying the following requirements
All internal nodes in the tree have either two or three children.
All leaves of the tree are at the same level.The 2-3 tree is also a search tree like the binary search tree, but this tree tries to solve the problem of the unbalanced tree The following link is useful to understand how 2-3 trees works:
Java applet illustrating 2-3 trees.
Practice adding nodes to the tree and see how the structure of the tree changes
For this assignment, you should write a Java program that read numbers from a file(TwoThreeInsert.txt) and store them in a 2-3 tree. The file name MUST be given as an argument for the program. Then your program should provide a menu to allow the user to do the following:
1.insert a new number to the tree.
2.print the tree in an ascending order.
3.print the tree in a descending order.
4.save the current tree to the file and exit.
Your program should handle all cases, such as adding a number which already exists in the tree
Sample run example:
$>
java
MyTree TwoThreeInsert.txt
Loading the file and insert into a 2
–
3 tree
1. insert 2. print ascending 3. print descending 4. save and exit
Enter your choice:1
En
ter a number:23
Number inserted.
1. insert 2. print ascending 3. print descending 4. save and exit
Enter your choice:1
Enter a number:23
Number already exist.
1. insert 2. print ascending 3. print descending 4. save and exit
Enter your choice:2
2 3 5 7 9 1
2 23 65 67
1. insert 2. print ascending 3. print descending 4. save and exit
Enter your choice:5
67 65 23 12 9 7 5 3 2
1. insert 2. print ascending 3. print descending 4. save and exit
Enter your choice:5
File saved. exiting…
$>
Bonus (
1
marks
):
implem
ent a delete
method
that allows the user to delete a node from
the tree.
To delete a node from a 2
–
3 tree is performed analogously. First the node is located and
removed. Call
p
the parent of the removed node. If the number of children of
p
has
decreased
from three to two, the tree is still 2
–
3. If the number of children of
p
has
decreased from two to one, merge
p
with one of its siblings, possibly reducing the
number of children of
p
‘s parent. Precede
recursively
, up to the root of the tree. If at the
end
deleting a root makes its child become root. For more details how delete should work
look at the above java applet link
and the text
–
book
File saved. exiting…
$>
Bonus (
1
marks
):
implem
ent a delete
method
that allows the user to delete a node from
the tree.
To delete a node from a 2
–
3 tree is performed analogously. First the node is located and
removed. Call
p
the parent of the removed node. If the number of children of
p
has
decreased
from three to two, the tree is still 2
–
3. If the number of children of
p
has
decreased from two to one, merge
p
with one of its siblings, possibly reducing the
number of children of
p
‘s parent. Precede
recursively
, up to the root of the tree. If at the
end
deleting a root makes its child become root. For more details how delete should work
look at the above java applet link
and the text
–
book
.
Submission
:
Hand in your complete Java source code; and a copy of the results
after running
your program
(
with the given file
Two Three Insert
.txt)
Upload your source code to
CMS
Demonstrate your program to TA before/on the due date
To get answer chat with online assignment adviser
