CS61B
Lecture 18: Balanced Search Trees
¡ñ Tree Rotation
¡ñ Left Leaning Red-Black Trees
¡ñ Maintaining Correspondence Through Rotation
datastructur.es
The Bad News
2-3 trees (and 2-3-4 trees) are a real pain to implement, and suffer from performance problems. Issues include:
¡ñ Maintaining different node types.
¡ñ Interconversion of nodes between 2-nodes and 3-nodes.
¡ñ Walking up the tree to split nodes. fantasy 2-3 code via Kevin Wayne
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); } }
¡°Beautiful algorithms are, unfortunately, not always the most useful.¡± – Knuth
datastructur.es
BST Structure and Tree Rotation
datastructur.es
BSTs
Suppose we have a BST with the numbers 1, 2, 3. Five possible BSTs.
¡ñ The specific BST you get is based on the insertion order.
¡ñ More generally, for N items, there are Catalan(N) different BSTs. 11 33
2
2312 13
32 21
Given any BST, it is possible to move to a different configuration using ¡°rotation¡±.
¡ñ In general, can move from any configuration to any other in 2n – 6 rotations
(see Rotation Distance, Triangulations, and Hyperbolic Geometry or Amy Liu). datastructur.es
Tree Rotation Definition
rotateLeft(G): Let x be the right child of G. Make G the new left child of x. ¡ñ Preserves search tree property. No change to semantics of tree.
P
GG
CPC
AkrAkr
Bjl Bjl
Tree Rotation Definition
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
¡ñ Can think of as temporarily merging G and P, then sending G down and left.
¡ñ Preserves search tree property. No change to semantics of tree.
G GP P
CPC Gr
AkrAkrCk
BjlBjlAjl
B
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.
¡ñ
Can think of as temporarily merging G and P, then sending P down and right.
P
Gr
Ck
Ajl
B
Your Turn
rotateRight(P): Let x be the left child of P. Make P the new right child of x.
¡ñ
Can think of as temporarily merging G and P, then sending P down and right.
P
Gr
Ck
Ajl
B
Your Turn
rotateRight(P): Let x be the left child of P. Make P the new right child of x.
¡ñ ¡ñ
Can think of as temporarily merging G and P, then sending P down and right. Note: k was G¡¯s right child. Now it is P¡¯s left child.
P
Gr
Ck
Ajl
G
CP
Akr
Bjl
B
For this example rotateRight(P) decreased height of tree!
BSTs
Give a sequence of rotation operations that balances the tree on the left.
1
3
2
2
13
datastructur.es
BSTs
Give a sequence of rotation operations that balances the tree on the left. ¡ñ rotateRight(3)
¡ñ rotateLeft(1)
11
32
23
2
13
There are other correct answers as well!
datastructur.es
Rotation for Balance
Rotation:
¡ñ ¡ñ
Can shorten (or lengthen) a tree. Preserves search tree property.
B
D
rotateRight(D)
D
B
>D
>D
rotateLeft(B)
< B
> B and < D
< B
> B and < D
Rotation for Balance
Rotation:
¡ñ ¡ñ
Can shorten (or lengthen) a tree. Preserves search tree property.
B
D
rotateRight(D)
D
B
>D
>D
< B
> B and < D
< B
> B and < D
rotateLeft(B)
Can use rotation to balance a BST: Demo
¡ñ Rotation allows balancing of a BST in O(N) moves.
Rotation: An Alternate Approach to Balance
Rotation:
¡ñ ¡ñ
Can shorten (or lengthen) a tree. Preserves search tree property.
B
D
rotateRight(D)
D
B
>D
>D
rotateLeft(B)
< B
> B and < D
< B
> B and < D
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...
Red-Black Trees
datastructur.es
Search Trees
There are many types of search trees:
¡ñ Binary search trees: Can balance using rotation, but we have no algorithm for doing so (yet).
¡ñ 2-3 trees: Balanced by construction, i.e. no rotations required.
Let¡¯s try something clever, but strange.
Our goal: Build a BST that is structurally identical to a 2-3 tree.
¡ñ Since 2-3 trees are balanced, so will our special BSTs.
datastructur.es
Representing a 2-3 Tree as a BST
A 2-3 tree with only 2-nodes is trivial. ¡ñ BST is exactly the same!
m
eo
bgnp
What do we do about 3-nodes?
m
df o
begnp
m
eo
bgnp
????
datastructur.es
Representing a 2-3 Tree as a BST: Dealing with 3-Nodes
Possibility 1: Create dummy ¡°glue¡± nodes.
mm
df o o
begnp dfnp
Result is inelegant. Wasted link. Code will be ugly.
df
df
beg
datastructur.es
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. mm
df o f o
begnp dgnp be
Idea is commonly used in practice (e.g. java.util.TreeSet).
df
f d
For convenience, we¡¯ll mark glue links as ¡°red¡±.
datastructur.es
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.
¡ñ LLRBs are normal BSTs!
¡ñ There is a 1-1 correspondence between an LLRB and an equivalent 2-3 tree.
¡ñ The red is just a convenient fiction. Red links don¡¯t ¡°do¡± anything special.
datastructur.es
Left-Leaning Red Black Binary Search Tree (LLRB)
Draw the LLRB corresponding to the 2-3 tree shown below.
uw
as v x y
datastructur.es
Left-Leaning Red Black Binary Search Tree (LLRB)
Draw the LLRB corresponding to the 2-3 tree shown below.
uw
as v x y
w
uy
svx
a
datastructur.es
Left-Leaning Red Black Binary Search Tree (LLRB)
Draw the LLRB corresponding to the 2-3 tree shown below.
uw
as v x y
Searching an LLRB tree for a key is easy. ¡ñ Treat it exactly like any BST. w
uy
svx
a
datastructur.es
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?
GGGG
CXBXBXBX
B A
ACACAC
datastructur.es
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?
GGGG
CXBXBXBX
B A
ACACAC
Equivalent 2-3
GG
G AB X B X B G
AB C X C A C A C X Invalid, has 4 node. Invalid, not balanced. Invalid, not balanced.
datastructur.es
LLRB Problem #2: yellkey.com/leave
How tall is the corresponding LLRB for the 2-3 tree below? (3 - nodes in pink)
L
DE P
B G J N SU
QR T V W
A
C
F
H
I
K
M
O
Note: The version of this slide used in live lecture was slightly different.
datastructur.es
LLRB Problem #2: yellkey.com/leave
How tall is the corresponding LLRB for the 2-3 tree below? (3 - nodes in pink)
¡ñ ¡ñ ¡ñ
Each 3-node becomes two nodes in the LLRB.
Total height is 3 (black) + 2 (red) = 5.
More generally, an LLRB has no more than ~2x the height of its 2-3 tree.
LL
DE P P
3 black links
B G J N SU
QR T V W Dark line shows longest path (3 links).
2 red links
R
U
S
A
C
F
H
I
K
M
O
Q
datastructur.es
LLRB Height
Suppose we have a 2-3 tree of height H.
¡ñ What is the maximum height of the corresponding LLRB?
L
DE P
B G J N SU
QR T V W
A
C
F
H
I
K
M
O
datastructur.es
LLRB Height
Suppose we have a 2-3 tree of height H.
¡ñ What is the maximum height of the corresponding LLRB?
¡ð Total height is H (black) + H + 1 (red) = 2H + 1. L
DE P
Worst case would be if these were both 3 nodes.
B G J N SU
QR T V W
A
C
F
H
I
K
M
O
datastructur.es
Left-Leaning Red Black Binary Search Tree (LLRB) Properties
Some handy LLRB properties:
¡ñ No node has two red links [otherwise it¡¯d be analogous to a 4 node, which are disallowed in 2-3 trees].
¡ñ Every path from root to a leaf has same number of black links [because 2-3 trees have the same number of links to every leaf]. LLRBs are therefore balanced.
This should say ¡°a null reference¡±, not ¡°a leaf¡±.
datastructur.es
Left-Leaning Red Black Binary Search Tree (LLRB) Properties
Some handy LLRB properties:
¡ñ ¡ñ
No node has two red links [otherwise it¡¯d be analogous to a 4 node, which are disallowed in 2-3 trees].
Every path from root to a leaf has same number of black links [because 2-3 trees have the same number of links to every leaf]. LLRBs are therefore balanced.
GGGG
CXBXBXBX
B
ACACAC
A
Invalid, B has two red links.
Invalid, not black balanced.
Invalid, not black balanced.
Valid
datastructur.es
LLRB Construction
One last important question: Where do LLRBs come from?
¡ñ Would not make sense to build a 2-3 tree, then convert. Even more complex.
¡ñ Instead, it turns out we implement an LLRB insert as follows:
¡ð Insert as usual into a BST.
¡ð Use zero or more rotations to maintain the 1-1 mapping.
datastructur.es
Maintaining 1-1 Correspondence Through Rotations
datastructur.es
The 1-1 Mapping
There exists a 1-1 mapping between: ¡ñ 2-3 Tree
¡ñ LLRB
Implementation of an LLRB is based on maintaining this 1-1 correspondence.
¡ñ When performing LLRB operations, pretend like you¡¯re a 2-3 tree.
¡ñ Preservation of the correspondence will involve tree rotations.
datastructur.es
Design Task #1: Insertion Color
Should we use a red or black link when inserting?
S
S E
S E
LLRB World
add(E) S
ES
World 2-3
datastructur.es
add(E)
add(E)
Design Task #1: Insertion Color
Should we use a red or black link when inserting?
¡ñ Use red! In 2-3 trees new values are ALWAYS added to a leaf node (at first).
S
S E
S E
LLRB World
add(E) S
ES
World 2-3
datastructur.es
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 add(S) B
AE AE
S
LLRB World
B
add(S)
B
AE
A ES
World 2-3
datastructur.es
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 add(S) B rotateLeft(E) B
AEAEAS
SE
LLRB World
B
add(S)
B
AE
A ES
World 2-3
datastructur.es
New Rule: Representation of Temporary 4-Nodes
We will represent temporary 4-nodes as BST nodes with two red links.
¡ñ This state is only temporary (more soon), so temporary violation of ¡°left
leaning¡± is OK.
B
AS
E
add(Z)
B
AS
EZ
Represents temporary 4 nodes. Temporarily violates ¡°no red right links¡±.
LLRB World
B
add(Z)
B
Temporarily violates ¡°no 4 nodes¡±.
A ES
A
E SZ
World 2-3
datastructur.es
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?
B
AZ
S
add(E)
B
AZ
S
E
LLRB World
B
add(E)
B
A SZ
A
ES Z
World 2-3
datastructur.es
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?
¡ñ Rotate Z right. B
AZ
S
add(E)
B
AZ
S
E
rotateRight(Z)
B
AS
EZ
LLRB World
B
add(E)
B
A SZ
A
ES Z
World 2-3
datastructur.es
Design Task #4: Splitting Temporary 4-Nodes
Suppose we have the LLRB below which includes a temporary 4 node. What should we do next?
¡ñ Try to figure this one out! It¡¯s a particularly interesting puzzle.
G
BX
AC LLRB World
Hint: Ask yourself ¡°What Would 2-3 Tree Do?¡± WW23TD?
G
split(A/B/C)
BG
AB C
X
ACX
World 2-3
datastructur.es
Design Task #4: Splitting Temporary 4-Nodes
Suppose we have the LLRB below which includes a temporary 4 node. What should we do next?
¡ñ Flip the colors of all edges touching B.
¡ð Note: This doesn¡¯t change the BST structure/shape.
GG flip(B)
BX BX
AC AC LLRB World
BST, the magic was inside of you all along.
G
split(A/B/C)
BG
AB C
X
ACX
World 2-3
datastructur.es
... and That¡¯s It!
Congratulations, you just invented the red-black BST.
¡ñ When inserting: Use a red link.
¡ñ If there is a right leaning ¡°3-node¡±, we have a Left Leaning Violation.
¡ð Rotate left the appropriate node to fix.
¡ñ If there are two consecutive left links, we have an Incorrect 4 Node Violation.
¡ð Rotate right the appropriate node to fix.
¡ñ If there are any nodes with two red children, we have a Temporary 4 Node.
¡ð Color flip the node to emulate the split operation. One last detail: Cascading operations.
¡ñ It is possible that a rotation or flip operation will cause an additional violation that needs fixing.
datastructur.es
Cascading Balance Example
Inserting Z gives us a temporary 4 node.
¡ñ Color flip yields an invalid tree. Why? What¡¯s next?
BBB
A S add(Z) A S flip(S) A S
EEZEZ
LLRB World
B
add(Z) B split(E/S/Z) B S
A ESZ A E Z
A ES
datastructur.es
World 2-3
Cascading Balance Example
Inserting Z gives us a temporary 4 node.
¡ñ Color flip yields an invalid tree. Why? What¡¯s next?
¡ñ We have a right leaning 3-node (B-S). We can fix with rotateLeft(b).
B
AS
EZ
rotateLeft(B)
S
BZ
AE
LLRB World
BS AEZ
datastructur.es
World 2-3
Optional Exercise
datastructur.es
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.
¡ñ You should end up with a perfectly balanced BST! To check your work, see this demo.
4
26
1357
datastructur.es
LLRB Runtime and Implementation
datastructur.es
LLRB Runtime
The runtime analysis for LLRBs is simple if you trust the 2-3 tree runtime.
¡ñ LLRB tree has height O(log N).
¡ñ Contains is trivially O(log N).
¡ñ Insert is O(log N).
¡ð O(log N) to add the new node.
¡ð O(log N) rotation and color flip operations per insert.
We will not discuss LLRB delete.
¡ñ Not too terrible really, but it¡¯s just not interesting enough to cover. See optional textbook if you¡¯re curious (though they gloss over it, too).
datastructur.es
LLRB Implementation
Amazingly, turning a BST into an LLRB requires only 3 clever lines of code. ¡ñ Does not include helper methods (which do not require cleverness).
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
https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html
datastructur.es
Search Tree Summary
datastructur.es
Search Trees
In the last 3 lectures, we talked about using search trees to implement sets/maps.
¡ñ Binary search trees are simple, but they are subject to imbalance.
¡ñ 2-3 Trees (B Trees) are balanced, but painful to implement and relatively slow.
¡ñ LLRBs insertion is simple to implement (but delete is hard).
¡ð Works by maintaining mathematical bijection with a 2-3 trees. ¡ñ Java¡¯s TreeMap is a red-black tree (not left leaning).
¡ð Maintains correspondence with 2-3-4 tree (is not a 1-1 correspondence).
¡ð Allows glue links on either side (see Red-Black Tree).
¡ð More complex implementation, but significantly (?) faster.
datastructur.es
… and Beyond
There are many other types of search trees out there.
¡ñ Other self balancing trees: AVL trees, splay trees, treaps, etc. There are at least hundreds of different such trees.
And there are other efficient ways to implement sets and maps entirely.
¡ñ Other linked structures: Skip lists are linked lists with express lanes.
¡ñ Other ideas entirely: Hashing is the most common alternative. We¡¯ll discuss
this very important idea in our next lecture.
datastructur.es