> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/18.-red-black-trees/18.6-exercises.md).
# 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.
* [x] **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.
* [x] **The height can increase.** If the rotation affects a leaf on the bottommost level, the height can increase.
* [x] **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.
* [x] **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)$$.
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://cs61b-2.gitbook.io/cs61b-textbook/18.-red-black-trees/18.6-exercises.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.