3. (a) (5 points) Consider the following sequence of keys: (18, 30, 50, 12, 1). Insert...

 

Transcribed Image Text:

3. (a) (5 points) Consider the following sequence of keys: (18, 30, 50, 12, 1). Insert the items with this set of keys in the order given into the red-black tree in the figure below. Draw the tree after each insertion. 16 10 22 (b) (5 points) Design and give the pseudocode for an O(logn) algorithm that determines whether a red-black tree with n keys stores any keys within a certain (closed) interval. That is, the input to the algorithm is a red-black tree T and two keys, I and r, where Ir. If T has at least one key k such that < k 3. (a) (5 points) Consider the following sequence of keys: (18, 30, 50, 12, 1). Insert the items with this set of keys in the order given into the red-black tree in the figure below. Draw the tree after each insertion. 16 10 22 (b) (5 points) Design and give the pseudocode for an O(logn) algorithm that determines whether a red-black tree with n keys stores any keys within a certain (closed) interval. That is, the input to the algorithm is a red-black tree T and two keys, I and r, where Ir. If T has at least one key k such that < k