1. Find a sequence of numbers which, when incrementally inserted into a red-black tree, causes the...

 

Transcribed Image Text:

1. Find a sequence of numbers which, when incrementally inserted into a red-black tree, causes the following sequence of rotations: left, right, left. You may start with an initially non-empty tree, and you may insert numbers that do not cause any rotations. But there should not be any additional rotations per- formed. Draw the sequence of trees that you obtain after each insertion. For each such tree indicate the node that violates the red-black tree condition, indicate the nodes that participate in the rotation, the type of the rotation, and the subtrees that correspond to each other before and after the rotation. Hint: Use a red-black tree demo from the web. 2. Suppose we insert the following values into a B-Tree with t = 3 in this order: 4,9, 2, 14, 1, 7, 6, 10, 8, 4, 13, 11, 3, 5, 12 Draw the final B-Tree and each B-Tree before and after each split (i.e. you do not need to show the tree after every insertion). 3. Suppose you have a B-tree of minimum degree k and height h. What is the largest number of values that can be stored in such a B-tree? 1. Find a sequence of numbers which, when incrementally inserted into a red-black tree, causes the following sequence of rotations: left, right, left. You may start with an initially non-empty tree, and you may insert numbers that do not cause any rotations. But there should not be any additional rotations per- formed. Draw the sequence of trees that you obtain after each insertion. For each such tree indicate the node that violates the red-black tree condition, indicate the nodes that participate in the rotation, the type of the rotation, and the subtrees that correspond to each other before and after the rotation. Hint: Use a red-black tree demo from the web. 2. Suppose we insert the following values into a B-Tree with t = 3 in this order: 4,9, 2, 14, 1, 7, 6, 10, 8, 4, 13, 11, 3, 5, 12 Draw the final B-Tree and each B-Tree before and after each split (i.e. you do not need to show the tree after every insertion). 3. Suppose you have a B-tree of minimum degree k and height h. What is the largest number of values that can be stored in such a B-tree?