Red-Black BSTs
Assignment 8
Submit your answers via Moodle. Submissions may be uploaded as PDF or as plain text files.
A LaTeX answer template is available here: answers.tex.
New to LaTeX? See the LaTeX guide for DSA students.
Exercise 1: Red-black BST (8 points)
Consider the following left-leaning red-black BST. Some of the colors and key values are suppressed.
-
Which one or more of the following keys could be the one labeled with a question mark?
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z -
Which one or more of the following keys must be red
(that is, the link between the key and its parent is red)?
P Q S T Y -
How many
rotateLeft(),rotateRight(), andflipColors()operations would be used to insert each key below into the original red-black BST?
Present your result in a small table with columns E, N, and G
and rows rotateLeft(), rotateRight(), and flipColors().
Exercise 2: Red-black BST Deleting (16 points)
Implement the delete functions of a BST. A fully implemented BST with the four missing
functions located at the beginning of the file is available here: Material.zip.
Using tinyST.txt as input should result in the following output:
A 8
C 4
E 12
H 5
L 11
M 9
P 10
R 3
S 0
X 7
After deleting max
A 8
C 4
E 12
H 5
L 11
M 9
P 10
R 3
S 0
After deleting min
C 4
E 12
H 5
L 11
M 9
P 10
R 3
S 0