CS61B, 2022
Lecture 18: Balanced Search Trees
The Bad News
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
BST Structure and
Tree Rotation
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
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
G
C
P
k
r
A
B
j
l
Tree Rotation Definition
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.
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.
C
k
r
A
B
j
l
G
P
G
C
P
k
r
A
B
j
l
For this example rotateRight(P) decreased height of tree!
Balancing BSTs with Rotation
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: Demo
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
Red-Black Trees
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
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/defense
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/person
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/life
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/leave
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
Note on Hidden Slides
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
LLRB Construction
One last important question: Where do LLRBs come from?
Maintaining 1-1 Correspondence Through Rotations
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
Design Task #1: Insertion Color
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 #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
World 2-3
add(S)
add(S)
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
World 2-3
add(S)
rotateLeft(E)
add(S)
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
World 2-3
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”.
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?
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
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)
Strongly Recommended Optional Exercise
(see web video)
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
LLRB Runtime and Implementation
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
Amazingly, turning a BST into an LLRB requires only 3 clever lines of code.
private Node put(Node h, Key key, Value val) {
if (h == null) { return new Node(key, val, RED); }
int cmp = key.compareTo(h.key);
if (cmp < 0) { h.left = put(h.left, key, val); }
else if (cmp > 0) { h.right = put(h.right, key, val); }
else { h.val = val; }
if (isRed(h.right) && !isRed(h.left)) { h = rotateLeft(h); }
if (isRed(h.left) && isRed(h.left.left)) { h = rotateRight(h); }
if (isRed(h.left) && isRed(h.right)) { flipColors(h); }
return h;
}
just 3 lines
needed
to balance
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.