Tree Rotation and Red-Black Trees
1
Lecture 18 (Data Structures 4)
CS61B, Spring 2024 @ UC Berkeley
Slides credit: Josh Hug
B-Trees Are Ugly to Implement
Lecture 18, CS61B, Spring 2024
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 18, CS61B, Spring 2024
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
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 18, CS61B, Spring 2024
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
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
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
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
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
4
1
rotateRight(1)
???
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 18, CS61B, Spring 2024
B-Trees Are Ugly to Implement
Tree Rotation
Left Leaning Red-Black Trees (LLRBs)
Search Tree Summary
Search Trees
There are many types of search trees:
Let’s try something clever, but strange.
Our goal: Build a BST that is structurally identical to 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
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 18, CS61B, Spring 2024
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/view
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: yellkey.com/view
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/chair
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: yellkey.com/chair
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 18, CS61B, Spring 2024
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 18, CS61B, Spring 2024
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
Lecture 18, CS61B, Spring 2024
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
Lecture 18, CS61B, Spring 2024
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.
Search Tree Summary
Lecture 18, CS61B, Spring 2024
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.