> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/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-spring-2026/17.-red-black-trees/17.1-rotating-trees.md).
# 17.1 Rotating Trees
Wonderfully balanced as they are, B-Trees are really difficult to implement. We need to keep track of the different nodes and the splitting process is pretty complicated. As computer scientists who appreciate clean code and a good challenge, let's find another way to create a balanced tree.
## Multiple Structures of BST
For any BST, there are multiple ways to structure it so that you maintain the BST invariants. Earlier, we talked about how **inserting** elements in different orders will result in a different BST. The sequence in which one inserts into a BST will affect its structure. The BSTs below all consist of the elements 1, 2, and 3, yet all have different structures.
Exercise: For each tree shown above, provide an order of insertion that yields the structure.
1. insert(1), insert(2), insert(3)
2. insert(1), insert(3), insert(2)
3. insert(2), insert(1), insert(3) or insert(2), insert(3), insert(1)
4. insert(3), insert(1), insert(2)
5. insert(3), insert(2), insert(1)
## Tree Rotation
The formal definition of rotation is:
```
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
```
```
rotateRight(G): Let x be the left child of G. Make G the new right child of x.
```
We will slowly demystify this process in the next few paragraphs.
Below is a graphical description of what happens in a left rotation on the node G:
rotateLeft(G)
The written description of what happened above is this:
* G's right child, P, merges with G, bringing its children along.
* P then passes its left child to G and G goes down to the left to become P's left child.
You can see that the structure of the tree changes as well as its height. We can also rotate on a non-root node. We just disconnect the node from the parent temporarily, rotate the subtree at the node, then reconnect the new root.
### Implementation
Here are the implementations of `rotateRight` and `rotateLeft:`
```
private Node rotateRight(Node h) {
// assert (h != null) && isRed(h.left);
Node x = h.left;
h.left = x.right;
x.right = h;
return x;
}
// make a right-leaning link lean to the left
private Node rotateLeft(Node h) {
// assert (h != null) && isRed(h.right);
Node x = h.right;
h.right = x.left;
x.left = h;
return x;
}
```
You may be wondering how does the parent node know about which node to point to after we rotate? That's why we are returning x, and other parts of our code will make use of this information to correctly update the parent node's pointer.
## Balancing BSTs with Tree Rotation
{% embed url="" %}
With rotations, we can actually balance a tree.
Consider the example below:
We can do balance the given BST on the left by calling:
1. `rotateRight(3)`
2. `rotateLeft(1)`
The main observation to make for tree rotation is that it is possible to **shorten** or **lengthen** a tree, while maintaining the search tree's property.
For more examples, see the demo in [these slides](https://docs.google.com/presentation/d/1pfkQENfIBwiThGGFVO5xvlVp7XAUONI2BwBqYxib0A4/edit#slide=id.g465b5392c_00).
---
# 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, and the optional `goal` query parameter:
```
GET https://cs61b-2.gitbook.io/cs61b-textbook-spring-2026/17.-red-black-trees/17.1-rotating-trees.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
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.