Comment on page
18.6 Exercises
- 1.Consider the tree below. If we call
rotateLeft(C)
, which operation reverts the tree back to its original form?

- 2.When you rotate a nodes in a tree, which of the following can happen?
- If the tree was previously a valid search tree, it can become invalid.
- The height can stay the same.
- The height can increase.
- The height can decrease.
- The number of nodes can change.
- The root of the tree can change.
- If the tree was previously a valid search tree, it can become invalid. Rotation always preserves search tree properties.
- The height can stay the same. If the rotation does not affect any leaf nodes on the bottommost level, the height will stay the same.
- The height can increase. If the rotation affects a leaf on the bottommost level, the height can increase.
- The height can decrease. If the rotation affects a leaf on the bottommost level, the height can increase.
- The number of nodes can change. Rotation only changes the structure of the tree, not the nodes.
- The root of the tree can change. For example, rotating the root.
- 1.Consider the following LLRB. What is the height of the corresponding 2-3 tree and how many 3-nodes does it have?

- 2.Suppose we insert
15
in the LLRB above. What is the first operation that must be applied to maintain the LLRB invariants? - 3.Suppose in the process of insertion, we end up with the following temporary 4-node. What is the corresponding LLRB representation of this node?

- 1.Give a range of values, when inserted into the LLRB below, results in a
rotateRight
operation as the first balancing operation. Assume that values are distinct, but not necessarily integers.

Last modified 8mo ago