18.6 Exercises

Factual

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.

Problem 1

rotateRight(D). The inverse of any rotateLeft operation is a rotateRight on the node's left child.

Problem 2

• 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.

Procedural

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?

Problem 1

The corresponding 2-3 tree has height 1 and has two 3-nodes (17 25 and 39 43).

Problem 2

15 is inserted to the right of 13. Since we cannot have a right-leaning red link, we must rotateLeft(13).

Problem 3

Metacognitive

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.

Problem 1

rotateRight occurs when we have two red links in a row. This occurs when we insert to the left of 39. This value must be larger than 25 (since it is in its right branch) but less than 39 (since it is the left child of 39). So our final range is $(25, 39)$.