18.6 Exercises

Factual

1. Consider the tree below. If we call rotateLeft(C), which operation reverts the tree back to its original form?

1. When you rotate a nodes in a tree, which of the following can happen?

Problem 1

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

Problem 2

Procedural

1. Consider the following LLRB. What is the height of the corresponding 2-3 tree and how many 3-nodes does it have?

1. Suppose we insert 15 in the LLRB above. What is the first operation that must be applied to maintain the LLRB invariants?

2. 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)$.

Last updated