Description
• Write a command line program with the following behaviour.
• Let � be a random number between 1000 and 3000.
• Create a set � containing � integers. Each integer must be a random
number in the range −3000 and +3000. Make sure that there are no
duplicates in this set.
Set X contains ??? elements
• Let � be a random number between 500 and 1000.
• Create a second set � containing � integers. Each integer must be a
random number in the range −3000 and +3000. Make sure that there are
no duplicates in this set.
Set Y contains ??? elements
• Note that the sets X and Y may have elements in common.
Sets X and Y have ??? elements in common
• Insert all the elements in the set X into an AVL tree and into a Red-Black
tree. Both are binary search trees. The AVL tree and Red-Black tree
implementations must be your own.
• After inserting all the values into each tree, you must show: the number of
rotations performed in total, the height of the tree, the number of nodes in
the tree, and the number of comparison operations (left/right decisions)
made in total.
AVL: ?? tot. rotations req., height is ??, #nodes is ??, #comparisons is ??
RBT: ?? tot. rotations req., height is ??, #nodes is ??, #comparisons is ??
• Delete all the elements in the set Y from the AVL tree and from the RedBlack Tree. After deleting all the values into each tree, you must show: the
number of rotations performed in total, the height of the tree, the number
of nodes in the tree, and the number of comparison operations (left/right
decisions) made in total.
AVL: ?? tot. rotations req., height is ??, #nodes is ??, #comparisons is ??
RBT: ?? tot. rotations req., height is ??, #nodes is ??, #comparisons is ??
• Let � be a random number between 1000 and 2000.
• Create a third set � containing � integers. Each integer must be a random
number in the range −3000 and +3000. Make sure that there are no
duplicates in this set.
• Search for every element in the set � in both the AVL tree and the RedBlack tree. Note that a search may be successful or not.
k is ???
AVL: ??? total comparisons required
RBT: ??? total comparisons required
• In your report, write a high-quality discussion comparing AVL trees to
Red-Black trees. In this section, make sure to discuss the suitability of
each method in real-world applications.
Statement of completion – MUST be included in your report
Item Completed (Yes/No/Partial)
AVL tree (insert, delete, search)
Red-Black tree (insert, delete, search)
Discussion comparing AVL to RBT
If partial, explain what has been done
