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