WARNING, THESE SLIDES HAVE NOT YET BEEN UPDATED FOR FALL 2026
Tree Rotation and Red-Black Trees
2
Lecture 19 (Data Structures 4)
CS61B, Spring 2026 @ UC Berkeley
Josh Hug and Kay Oustehrout
Wrapping up Lecture 18
Quick note: We’ll start today by wrapping up lecture 18: https://docs.google.com/presentation/d/1U637ksATIWgiGF1ZwTxEXLV6I8ryiNE6hSJlo_WqcXM/edit?slide=id.g3ccc49945c4_0_63#slide=id.g3ccc49945c4_0_63
B-Trees Are Ugly to Implement
Lecture 19, CS61B, Spring 2026
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
The Bad News
B-Trees for small L, e.g. 2-3 trees and 2-3-4 trees, are a real pain to implement, and suffer from performance problems. Issues include:
“Beautiful algorithms are, unfortunately, not always the most useful.” - Knuth
public void put(Key key, Value val) {
Node x = root;
while (x.getTheCorrectChildKey(key) != null) {
x = x.getTheCorrectChildKey();
if (x.is4Node()) { x.split(); }
}
if (x.is2Node()) { x.make3Node(key, val); }
if (x.is3Node()) { x.make4Node(key, val); }
}
fantasy 2-3 code via Kevin Wayne
Definition of Tree Rotation
Lecture 19, CS61B, Spring 2026
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
Alternate Idea
Let’s try to develop an alternate idea where:
4
1
6
13
9
17
8
no
1
4
8
17
13
9
6
nice
BSTs
Suppose we have a BST with the numbers 1, 2, 3. Five possible BSTs.
Given any BST, it is possible to move to a different configuration using “rotation”.
1
2
3
1
3
2
3
2
1
3
1
2
3
2
1
Tree Rotation Definition (Demo)
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
G
C
P
k
r
A
B
j
l
I’m going left!!
Tree Rotation Definition (Demo)
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
G
C
P
k
r
A
B
j
l
I’m going left!!
I’ll be G’s new boss.
Tree Rotation Definition (Demo)
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
G
C
P
k
r
A
B
j
l
I went left of P.
I am G’s new boss.
Tree Rotation Definition (Demo)
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
G
C
P
k
r
A
B
j
l
I am G’s new boss.
I don’t make sense.
I went left of P.
Tree Rotation Definition (Demo)
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
G
C
P
k
r
A
B
j
l
I am G’s new boss.
I don’t make sense.
I went left of P.
Where should go?
k
j
l
Tree Rotation Definition (Demo)
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
G
C
P
k
r
A
B
j
l
I am G’s new boss.
I went left of P.
Where should go: To the right of G.
k
j
l
I got transferred from P to G.
Tree Rotation Definition (All in One Slide)
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
G
C
P
k
r
A
B
j
l
I’m going left!!
I went left.
I’ll be G’s new boss.
I am G’s new boss.
G
C
P
k
r
A
B
j
l
For this example rotateLeft(G) increased height of tree!
Tree Rotation Definition (Alternate Interpretation)
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
G
C
P
k
r
A
B
j
l
C
k
r
A
B
j
l
G P
C
k
r
A
B
j
l
G
P
For this example rotateLeft(G) increased height of tree!
Your Turn
rotateRight(P): Let x be the left child of P. Make P the new right child of x.
C
k
r
A
B
j
l
G
P
Your Turn
rotateRight(P): Let x be the left child of P. Make P the new right child of x.
G
C
P
k
r
A
B
j
l
For this example rotateRight(P) decreased height of tree!
C
k
r
A
B
j
l
G
P
C
k
r
A
B
j
l
G P
Tree Balancing
Lecture 19, CS61B, Spring 2026
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
Demo: Balancing with Tree Rotation
4
1
6
13
9
17
8
Demo: Balancing with Tree Rotation
4
1
6
13
9
17
8
rotateLeft(9)
Demo: Balancing with Tree Rotation: yellkey.com/approach
4
1
6
13
9
17
8
rotateLeft(9)
If rotateLeft(9), then 9 goes left. Who will be 9’s new parent?
Demo: Balancing with Tree Rotation
4
1
6
13
9
17
8
rotateLeft(9)
If rotateLeft(9), then 9 goes left. Who will be 9’s new parent?
Idea: If you rotateLeft(x), x goes let, and x’s new parent is its right child.
Demo: Balancing with Tree Rotation
4
1
6
17
13
9
8
Demo: Balancing with Tree Rotation
4
1
6
17
13
9
8
rotateLeft(6)
Demo: Balancing with Tree Rotation: yellkey.com/social
4
1
6
17
13
9
8
rotateLeft(6)
If rotateLeft(6), then 6 goes ____. Also, who will be 6’s new parent?
Demo: Balancing with Tree Rotation
4
1
6
17
13
9
8
rotateLeft(6)
If rotateLeft(6), then 6 goes ____. Also, who will be 6’s new parent?
Demo: Balancing with Tree Rotation
1
6
8
17
13
9
4
Demo: Balancing with Tree Rotation
1
6
8
17
13
9
4
rotateLeft(1)
Demo: Balancing with Tree Rotation
4
6
8
17
13
9
1
Demo: Balancing with Tree Rotation
4
6
8
17
13
9
1
rotateRight(6)
Demo: Balancing with Tree Rotation
1
4
8
17
13
9
6
Demo: Balancing with Tree Rotation
1
4
8
17
13
9
6
4
1
6
13
9
17
8
rotateLeft(9)
rotateLeft(6)
rotateLeft(1)
rotateRight(6)
Some Rotations are Undefined
If there is no appropriate child to take your place, a rotation operation is invalid.
4
1
rotateRight(1)
INVALID OPERATION
Time for a Game
If you have a device handy, head to https://joshh.ug/61b/bst_rotation/ (or scan the QR code) and try to win the game. Play for a few minutes to build some intuition.
If you don’t have a device handy, try to find a sequence of operations that balances this tree:
Attendance Link
Attendance link.
Auth with your Berkeley account and answer the Q.
BSTs
Give a sequence of rotation operations that balances the tree on the left.
1
3
2
3
2
1
BSTs
Give a sequence of rotation operations that balances the tree on the left.
1
3
2
3
2
1
1
2
3
There are other correct answers as well!
Rotation for Balance
Rotation:
D
B
rotateRight(D)
rotateLeft(B)
>D
> B and < D
< B
D
B
>D
> B and < D
< B
Rotation for Balance
Rotation:
Can use rotation to balance a BST.
D
B
rotateRight(D)
rotateLeft(B)
>D
> B and < D
< B
D
B
>D
> B and < D
< B
Rotation: An Alternate Approach to Balance
Rotation:
Paying O(n) to occasionally balance a tree is not ideal. In this lecture, we’ll see a better way to achieve balance through rotation. But first...
D
B
rotateRight(D)
rotateLeft(B)
>D
> B and < D
< B
D
B
>D
> B and < D
< B
The 2-3 Tree Isometry
Lecture 19, CS61B, Spring 2026
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
Red-Black Trees: The Big Idea
If we have a BST that is imbalanced, we can always improve the balance through rotations.
1
4
8
17
13
9
6
4
1
6
13
9
17
8
rotateLeft(9)
rotateLeft(6)
rotateLeft(1)
rotateRight(6)
Red-Black Trees: The Big Idea
If we have a BST that is imbalanced, we can always improve the balance through rotations.
Wild idea: Perform rotation such that we maintain a 1-to-1 correspondence with a 2-3 tree.
Representing a 2-3 Tree as a BST
A 2-3 tree with only 2-nodes is trivial.
What do we do about 3-nodes?
e
b
g
o
n
p
m
d f
b
g
o
n
p
m
e
e
b
g
o
n
p
m
????
Representing a 2-3 Tree as a BST: Dealing with 3-Nodes
Creating a one-to-one mapping with a BST seems initially impossible.
How could we possibly represent the tree above as a BST?
d f
b
g
o
n
p
m
e
Representing a 2-3 Tree as a BST: Dealing with 3-Nodes
Possibility 1: Create dummy “glue” nodes.
Any time you have a 3 node (i.e. a node with 3 children) just creating a supernode with a dummy glue at the top, with the left item as left child and right item as right child.
d f
b
g
o
n
p
m
e
o
n
p
m
b
g
e
d
f
Representing a 2-3 Tree as a BST: Dealing with 3-Nodes
Possibility 1: Create dummy “glue” nodes.
Result is inelegant. Wasted link. Code will be ugly.
d f
b
g
o
n
p
m
e
o
n
p
m
b
g
e
d
f
d f
d
f
Representing a 2-3 Tree as a BST: Dealing with 3-Nodes
Possibility 2: Create “glue” links with the smaller item off to the left.
Idea is commonly used in practice (e.g. java.util.TreeSet).
d f
b
g
o
n
p
m
e
o
n
p
m
d
f
d f
e
g
b
d
f
For convenience, we’ll mark glue links as “red”.
Left-Leaning Red Black Binary Search Tree (LLRB)
A BST with left glue links that represents a 2-3 tree is often called a “Left Leaning Red Black Binary Search Tree” or LLRB.
LLRB Properties
Lecture 19, CS61B, Spring 2026
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
Left-Leaning Red Black Binary Search Tree (LLRB)
Draw the LLRB corresponding to the 2-3 tree shown below.
x y
a s
v
u w
Left-Leaning Red Black Binary Search Tree (LLRB)
Draw the LLRB corresponding to the 2-3 tree shown below.
x y
a s
v
u w
s
v
u
w
x
y
a
Left-Leaning Red Black Binary Search Tree (LLRB)
Draw the LLRB corresponding to the 2-3 tree shown below.
Searching an LLRB tree for a key is easy.
s
v
u
w
x
y
a
x y
a s
v
u w
LLRB Problem #1: yellkey.com/shoulder
How many of these are valid LLRBs, i.e. have a 1-1 correspondence with a valid 2-3 tree?
G
B
X
A
C
G
B
X
A
C
G
B
X
A
C
G
C
X
A
B
LLRB Problem #1
How many of these are valid LLRBs, i.e. have a 1-1 correspondence with a valid 2-3 tree?
G
C
X
A
B
G
B
X
A
C
G
B
X
A
C
G
B
X
A
C
G
A B C
X
G
A B
X
C
G
B
X
A
C
B G
X
A
C
Equivalent 2-3
Invalid, has 4 node.
Invalid, not balanced.
Invalid, not balanced.
LLRB Problem #2: yellkey.com/family
How tall is the corresponding LLRB for the 2-3 tree below? (3 - nodes in pink)
D E
P
B
G
J
N
Q R
V W
A
C
F
H
I
K
M
O
S U
T
L
LLRB Problem #2
How tall is the corresponding LLRB for the 2-3 tree below? (3 - nodes in pink)
L
P
U
S
R
Q
D E
P
B
G
J
N
Q R
V W
A
C
F
H
I
K
M
O
S U
T
L
Dark line shows longest path (3 links).
3 black links
2 red links
LLRB Balance
Because 2-3 trees have logarithmic height, and the corresponding LLRB has height that is never more than ~2 times the 2-3 tree height, LLRBs also have logarithmic height!
L
P
U
S
R
Q
D E
P
B
G
J
N
Q R
V W
A
C
F
H
I
K
M
O
S U
T
L
Dark line shows longest path (3 links).
3 black links
2 red links
Extra: LLRB Invariants
Lecture 19, CS61B, Spring 2026
A somewhat more formal look at heights of LLRBs follows in the hidden slides after this one.
LLRB Height
Suppose we have a 2-3 tree of height H.
D E
P
B
G
J
N
Q R
V W
A
C
F
H
I
K
M
O
S U
T
L
LLRB Height
Suppose we have a 2-3 tree of height H.
D E
P
B
G
J
N
Q R
V W
A
C
F
H
I
K
M
O
S U
T
L
Worst case would be if these were both 3 nodes.
Left-Leaning Red Black Binary Search Tree (LLRB) Properties
Some handy LLRB properties:
Extra Slide: Root-to-Leaf vs. Root-to-Null
A version of this lecture from many years ago had a subtle error in its definition of “perfect black balance”. Specifically, it stated:
In fact, the correct invariant is:
An example of a red-black tree which satisfies the erroneous invariant, but has no corresponding 2-3 tree:
G
B
X
A
Invalid LLRB!
B G
X
A
2-3 tree missing child.
Left-Leaning Red Black Binary Search Tree (LLRB) Properties
Some handy LLRB properties:
G
C
X
A
B
G
B
X
A
C
G
B
X
A
C
G
B
X
A
C
Invalid, B has two red links.
Invalid, not
black balanced.
Invalid, not
black balanced.
Valid
Maintaining Isometry with Rotations
Lecture 19, CS61B, Spring 2026
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
LLRB Construction
One last important question: Where do LLRBs come from?
The 1-1 Mapping
There exists a 1-1 mapping between:
Implementation of an LLRB is based on maintaining this 1-1 correspondence.
Design Task #1: Insertion Color
Should we use a red or black link when inserting?�
S
S
E
S
E
S
E S
LLRB World
World 2-3
add(E)
add(E)
add(E)
Design Task #1: Insertion Color
Should we use a red or black link when inserting?
S
S
E
S
E
S
E S
LLRB World
add(E)
add(E)
add(E)
World 2-3
Design Task #2: Insertion on the Right
Suppose we have leaf E, and insert S with a red link. What is the problem below, and what do we do about it?
B
A
E
B
A
E S
B
A
E
B
A
E
S
LLRB World
add(S)
add(S)
World 2-3
Design Task #2: Insertion on the Right
Suppose we have leaf E, and insert S with a red link. What is the problem below, and what do we do about it: Right links aren’t allowed. What rotation fixes this?
B
A
E
B
A
E S
B
A
E
B
A
E
S
LLRB World
add(S)
add(S)
World 2-3
B
A
S
E
Hint: This is the correct representation of the 2-3 tree.
What rotation operation gives us this tree?
Design Task #2: Insertion on the Right
Suppose we have leaf E, and insert S with a red link. What is the problem below, and what do we do about it: Right links aren’t allowed, so rotateLeft(E).
B
A
E
B
A
E S
B
A
E
B
A
E
S
B
A
S
E
LLRB World
add(S)
rotateLeft(E)
add(S)
World 2-3
New Rule: Representation of Temporary 4-Nodes
We will represent temporary 4-nodes as BST nodes with two red links.
B
A
E S
B
A
E S Z
LLRB World
B
A
S
E
B
A
S
E
Z
add(Z)
add(Z)
Represents temporary 4 nodes. Temporarily violates “no red right links”.
Temporarily violates “no 4 nodes”.
World 2-3
Design Task #3: Double Insertion on the Left
Suppose we have the LLRB below and insert E. We end up with the wrong representation for our temporary 4 node. What should we do so that the temporary 4 node has 2 red children (one left, one right) as expected?
LLRB World
World 2-3
B
A
S Z
B
A
E S Z
B
A
Z
S
B
A
Z
S
E
add(E)
add(E)
Design Task #3: Double Insertion on the Left
Suppose we have the LLRB below and insert E. We end up with the wrong representation for our temporary 4 node. What should we do so that the temporary 4 node has 2 red children (one left, one right) as expected?
LLRB World
World 2-3
B
A
S Z
B
A
E S Z
B
A
Z
S
B
A
Z
S
E
add(E)
add(E)
Hint: This is the correct representation of the 2-3 tree.
What rotation operation gives us this tree?
B
A
S
E
Z
Design Task #3: Double Insertion on the Left
Suppose we have the LLRB below and insert E. We end up with the wrong representation for our temporary 4 node. What should we do?
LLRB World
World 2-3
B
A
S Z
B
A
E S Z
B
A
Z
S
B
A
Z
S
E
B
A
S
E
Z
rotateRight(Z)
add(E)
add(E)
Design Task #4: Splitting Temporary 4-Nodes
Suppose we have the LLRB below which includes a temporary 4 node. What should we do next?
LLRB World
World 2-3
G
A B C
X
split(A/B/C)
B G
X
A
C
G
B
X
A
C
Hint: Ask yourself “What Would 2-3 Tree Do?” WW23TD?
Design Task #4: Splitting Temporary 4-Nodes
Suppose we have the LLRB below which includes a temporary 4 node. What should we do next?
LLRB World
World 2-3
G
A B C
X
split(A/B/C)
B G
X
A
C
G
B
X
A
C
G
B
X
A
C
Hint 2: This is the correct representation of the 2-3 tree.
How do we get this tree?
�Hint 3: We don't need rotation.
Design Task #4: Splitting Temporary 4-Nodes
Suppose we have the LLRB below which includes a temporary 4 node. What should we do next?
LLRB World
World 2-3
G
A B C
X
split(A/B/C)
B G
X
A
C
G
B
X
A
C
flip(B)
G
B
X
A
C
BST, the magic was inside of you all along.
… and That’s It!
Congratulations, you just invented the red-black BST.
One last detail: Cascading operations.
Cascading Balance Example
Inserting Z gives us a temporary 4 node.
B
A
E S
B
A
E S Z
B
A
S
E
LLRB World
World 2-3
B
A
S
E
Z
B
A
S
E
Z
B S
A
E
Z
add(Z)
flip(S)
add(Z)
split(E/S/Z)
Cascading Balance Example
Inserting Z gives us a temporary 4 node.
LLRB World
World 2-3
B
A
S
E
Z
B S
A
E
Z
B
A
S
E
Z
rotateLeft(B)
Optional Exercise (Extra)
Lecture 19, CS61B, Spring 2026
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
Insertion of 7 through 1
To get an intuitive understanding of why all this works, try inserting the 7, 6, 5, 4, 3, 2, 1, into an initially empty LLRB.
To check your work, see this demo.
2
1
3
6
5
7
4
Runtime and Implementation (Extra)
Lecture 19, CS61B, Spring 2026
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
LLRB Runtime
The runtime analysis for LLRBs is simple if you trust the 2-3 tree runtime.
We will not discuss LLRB delete.
LLRB Implementation
For those of you interested in implementing an LLRB, we will have an optional set of homeworks at the end of the class that you can complete.
Search Tree Summary
Lecture 19, CS61B, Spring 2026
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
Search Trees
In the last 3 lectures, we talked about using search trees to implement sets/maps.
… and Beyond
There are many other types of search trees out there.
And there are other efficient ways to implement sets and maps entirely.