Lecture 7

Binary Search Trees and Red-Black Trees

Announcements
• HW4 is out today

• HW partners

• Please tag all pages of a question on Gradescope,

not just first one!
 More detailed schedule on the website!

Roadmap We are here

ures

2l
e ct
5l Randomized

ec
tu
Algs

re
s
MIDTERM

str
Asymptotic

Da ture
1 st

uc
cla

ta s
ss Analysis
Sorting
Divide and e n ces
Re curr
conquer MIDTERM

Dynamic
Greedy Algs Programming

MIDTERM
Longe Graphs!
st, Sh MIDTERM
Max a ortes
nd M t,

1l
in… l e c tures The
10

ec
tur
Future!

e
 But first!
• A brief wrap-up of divide and conquer.

Divide and
Conquer: Big problem

Smaller Smaller
problem problem
Recurse! Recurse!

Yet smaller Yet smaller Yet smaller Yet smaller

problem problem problem problem
How do we design divide-and-
conquer algorithms?
• So far we’ve seen lots of examples.
• Karatsuba (and Alien Multiplication)
• MergeSort
• Select
• QuickSort
• Matrix Multiplication (HW2)
• Majority Element (HW3)
• Let’s take a minute to zoom out and look at some
general strategies.
One Strategy
1. Identify natural sub-problems
• Arrays of half the size
• Things smaller/larger than a pivot
2. Imagine you had the magical ability to solve those
natural sub-problems…what would you do?
• Just try it with all of the natural sub-problems you can
come up with! Anything look helpful?
3. Work out the details
• Write down pseudocode, etc.

Think about how you could

arrive at MergeSort or
QuickSort via this strategy!
Other tips
• Small examples.
• If you have an idea but are having trouble working out the details, try it on
a small example by hand.
• Gee, that looks familiar…
• The more algorithms you see, the easier it will get to come up with new
algorithms!
• Bring in your analysis tools.
• E.g., if I’m doing divide-and-conquer with 2 subproblems of size n/2 and I
want an O(n logn) time algorithm, I know that I can afford O(n) work
combining my sub-problems.
• Iterate.
• Darn, that approach didn’t work! But, if I tweaked this aspect of it, maybe
it works better?
• Everyone approaches problem-solving differently…find the way
that works best for you.
There is no universal recipe for
designing algorithms.
• This can be frustrating on HW and midterms ….
• P vs NP: much easier to understand a proof than
to come up with one!

• Practice helps!
• The examples we see in Lecture and in HW are meant to
help you practice this skill.
• There are even more algorithms in the optional texts!
• Check out CLRS Chapter 4, or Algorithms Illuminated
Chapter 3 for even more examples of divide and conquer
algorithms.
 More detailed schedule on the website!

Roadmap We are here

ures

2l
e ct
5l Randomized

ec
tu
Algs

re
s
MIDTERM

str
Asymptotic

Da ture
1 st

uc
cla

ta s
ss Analysis
Sorting
Divide and e n ces
Re curr
conquer MIDTERM

Dynamic
Greedy Algs Programming

MIDTERM
Longe Graphs!
st, Sh MIDTERM
Max a ortes
nd M t,

1l
in… l e c tures The
10

ec
tur
Future!

e
Today
• Begin a brief foray into data structures!
• See CS 166 for more!
• Binary search trees
• You may remember these from CS 106B
• They are better when they’re balanced.

this will lead us to…

• Self-Balancing Binary Search Trees

• Red-Black trees.
Some data structures
for storing objects like 5
(aka, nodes with keys)

• (Sorted) arrays:

1 2 3 4 5 7 8

• Linked lists:
HEAD 3 2 1 8 5 7 4

• Some basic operations:

• INSERT, DELETE, SEARCH
Sorted Arrays 1 2 3 4 5 7 8

• O(n) INSERT/DELETE:
• First, find the relevant element (we’ll see how below), and
then move a bunch elements in the array:

1 2 3 4 54.5 7 8
eg, insert 4.5
• O(log(n)) SEARCH:

1 2 3 4 5 7 8
eg, Binary search to see if 3 is in A.
 (Not necessarily sorted)
Linked lists
7 5 3 4 1 2 8
• O(1) INSERT:

eg, insert 6
HEAD 7 5 3 4 1 2 8

• O(n) SEARCH/DELETE:
HEAD 7 5 3 4 1 2 8

eg, search for 1 (and then you could delete it by manipulating pointers).
Motivation for Binary Search Trees
TODAY!
(Balanced)

Sorted Arrays Linked Lists Binary Search

Trees

Search O(log(n)) O(n) O(log(n))

Delete O(n) O(n) O(log(n))

Insert O(n) O(1) O(log(n))

 For today all keys are distinct.

Binary tree terminology [poll]

This is a node.
Each node has two children. This node is It has a key (7).
the root
The left child of 3 is 2
5
The right child of 3 is 4

The parent of 3 is 5 3 7
2 is a descendant of 5
Each node has a pointer to its 2 4 8
left child, right child, and parent.
Both children of 1 are NIL.
(I won’t usually draw them). 1 These nodes
The height of this tree is 3.
(Max number of edges from the NIL NIL are leaves.
root to a leaf).
From your pre-lecture exercise…

Binary Search Trees

• A BST is a binary tree so that:
• Every LEFT descendant of a node has key less than that node.
• Every RIGHT descendant of a node has key larger than that node.
• Example of building a binary search tree:

3 4
5

8 7
1
2
From your pre-lecture exercise…

Binary Search Trees

• A BST is a binary tree so that:
• Every LEFT descendant of a node has key less than that node.
• Every RIGHT descendant of a node has key larger than that node.
• Example of building a binary search tree:

3 4
5

8 7
1
2
From your pre-lecture exercise…

Binary Search Trees

• A BST is a binary tree so that:
• Every LEFT descendant of a node has key less than that node.
• Every RIGHT descendant of a node has key larger than that node.
• Example of building a binary search tree:

3 5
1
4 7
2
8
From your pre-lecture exercise…

Binary Search Trees

• A BST is a binary tree so that:
• Every LEFT descendant of a node has key less than that node.
• Every RIGHT descendant of a node has key larger than that node.
• Example of building a binary search tree:

3 7
1
2 4 8
From your pre-lecture exercise…

Binary Search Trees

• A BST is a binary tree so that:
• Every LEFT descendant of a node has key less than that node.
• Every RIGHT descendant of a node has key larger than that node.
• Example of building a binary search tree:
Q: Is this the only
5 binary search tree I
could possibly build
with these values?
A: No. I made
3 7 choices about
which nodes to
choose when. Any
choices would
2 4 8 have been fine.

1
Aside: this should look familiar
kinda like QuickSort

3 4
5

8 7
1
2
 Which of these is a BST?
1 minute Think-Pair-Share
Binary Search Trees
• A BST is a binary tree so that:
• Every LEFT descendant of a node has key less than that node.
• Every RIGHT descendant of a node has key larger than that node.

5 5

3 7 3 7

2 4 8 2 4 8
NOT a Binary
1 Binary Search Tree 1 Search Tree
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
NIL NIL
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
NIL NIL
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
NIL NIL

2
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
NIL NIL

2
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
NIL NIL

2
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
2 3
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
2 3 4
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
2 3 4
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
2 3 4 5
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
2 3 4 5 7
Aside: In-Order Traversal of
BSTs
• Output all the elements in sorted order!

• inOrderTraversal(x):
• if x!= NIL: 5
• inOrderTraversal( x.left )
• print( x.key ) 3 7
• inOrderTraversal( x.right )
2 4
• Runs in time O(n). 2 3 4 5 7 Sorted!
Back to the goal

Fast SEARCH/INSERT/DELETE
Can we do these?
 SEARCH in a Binary Search Tree
definition by example

EXAMPLE: Search for 4.

5
EXAMPLE: Search for 4.5
• It turns out it will be convenient
3 7 to return 4 in this case
• (that is, return the last node
!!!! before we went off the tree)

2 4 8
Write pseudocode

1 (or actual code) to

implement this!
How long does this take?
O(length of longest path) = O(height) Ollie the over-achieving ostrich
 INSERT in a Binary Search Tree
EXAMPLE: Insert 4.5
5 • INSERT(key):
• x = SEARCH(key)
• Insert a new node with
3 7 desired key at x…
!!!!
2 4 8
x= 4

1 4.5 You thought about this on

your pre-lecture exercise!
(See skipped slide for
pseudocode.)
 This slide

INSERT in a Binary Search Tree

skipped in
class – here
for reference

EXAMPLE: Insert 4.5

5 • INSERT(key):
• x = SEARCH(key)
• if key > x.key:
3 7 • Make a new node with the
!!!! correct key, and put it as the
right child of x.
2 4 8 • if key < x.key:
• Make a new node with the
x= 4 correct key, and put it as the
left child of x.
1 4.5 • if x.key == key:
• return
 DELETE in a Binary Search Tree
EXAMPLE: Delete 2
5 • DELETE(key):
• x = SEARCH(key)
•
3 7 if x.key == key:
• ….delete x….

2 4 8
You thought about this in your pre-
x= 2
lecture exercise too!

1 This is a bit more complicated…see

the skipped slides for some pictures
of the different cases.
 DELETE in a Binary Search Tree
This slide skipped
in class – here for
several cases (by example) reference!
say we want to delete 3

5 5 5 5
3 3 2
Case 1: if 3 is a leaf,
just delete it.
2
This triangle
is a cartoon
for a subtree
Write pseudocode for all of these!

Case 2: if 3 has just one child,

move that up.
Siggi the Studious Stork
 This slide skipped
DELETE in a Binary Search Tree in class – here for
ctd. reference!

Case 3: if 3 has two children,

replace 3 with it’s immediate successor. • Does this maintain the BST
(aka, next biggest thing after 3) property?
• Yes.
• How do we find the
5 5 immediate successor?
• SEARCH for 3 in the subtree
3 3.1 under 3.right
• How do we remove it when
we find it?
2 4 2 4 • If [3.1] has 0 or 1 children,
do one of the previous cases.
• What if [3.1] has two
children?
3.1 • It doesn’t.
 How long do these operations take?
• SEARCH is the big one.
• Everything else just calls SEARCH and then does some
small O(1)-time operation.

5 Time = O(height of tree)

3 7
Trees have depth
O(log(n)). Done! Wait a
2 4 6 8 second…

How long does search take?

1 minute think; 1 minute pair+share

Lucky the Plucky the Pedantic

lackadaisical lemur. Penguin
Search might take time O(n).
2 • This is a valid binary search tree.
3 • The version with n nodes has
depth n, not O(log(n)).
4
5
6
7
8
 How often is “every so
often” in the worst case?

What to do?
It’s actually pretty often!

Ollie the over-achieving ostrich

• Goal: Fast SEARCH/INSERT/DELETE

• All these things take time O(height)
• And the height might be big!!! 

• Idea 0:
• Keep track of how deep the tree is getting.
• If it gets too tall, re-do everything from scratch.
• At least Ω(n) every so often….

• Turns out that’s not a great idea. Instead we turn to…

 Self-Balancing
Binary Search Trees
 No matter what lives underneath A,B,C,
Idea 1: Rotations this takes time O(1). (Why?)

• Maintain Binary Search Tree (BST) property, while

moving stuff around.
Note: A, B, C, X, Y are
variable names, not the
contents of the nodes.

YOINK! X Y Y

Y C A B X A X

B fell
A B That’s not
bin ary!!
C down. B C
CLAIM:
this still has BST property.
This seems helpful

3 YOINK!
5
2 5 3 7

4 7 2 4 6 8

6 8
Strategy?
• Whenever something seems unbalanced, do
rotations until it’s okay again.

Even for Lucky this is pretty vague.

What do we mean by “seems
unbalanced”? What’s “okay”?

Lucky the Lackadaisical Lemur

Idea 2: have some proxy for balance
• Maintaining perfect balance is too hard.
• Instead, come up with some proxy for balance:
• If the tree satisfies [SOME PROPERTY], then it’s pretty
balanced.
• We can maintain [SOME PROPERTY] using rotations.

There are actually several

ways to do this, but today
we’ll see…
Red-Black Trees
• A Binary Search Tree that balances itself!
• No more time-consuming by-hand balancing!
• Be the envy of your friends and neighbors with the
time-saving…

t r ee !
- B l a ck
R ed 3
5
7
Maintain balance by stipulating that black
nodes are balanced, and that there aren’t 2 4 6 8
too many red nodes.

It’s just good

sense!
Leo Guibas Bob Sedgewick
 Red-Black Trees
obey the following rules (which are a proxy for balance)
• Every node is colored red or black.
• The root node is a black node.
• NIL children count as black nodes.
• Children of a red node are black nodes. 5
• For all nodes x:
• all paths from x to NIL’s have the same 3 7
number of black nodes on them.

2 4 6 8
I’m not going to draw the NIL
children in the future, but they NIL NIL NIL NIL NIL NIL NIL NIL
are treated as black nodes.
 • Every node is colored red or black.
Examples(?) • The root node is a black node.
• NIL children count as black nodes.
• Children of a red node are black nodes.
• For all nodes x:
• all paths from x to NIL’s have the same
Which of these number of black nodes on them.
are red-black trees?
Yes! (NIL nodes not drawn)
1 minute think
1 minute share

No! No! No!

Break
 Why these rules???????
5
• This is pretty balanced.
• The black nodes are balanced 3 7
• The red nodes are “spread out”
so they don’t mess things up
too much.
2 4 6 8
• We can maintain this property
as we insert/delete nodes, by 9
using rotations.
This is the really clever idea!
This Red-Black structure is a proxy for balance.
It’s just a smidge weaker than perfect balance, but we can actually maintain it!
 Let’s build some intuition!

This is “pretty balanced” Lucky the

lackadaisical
lemur

• To see why, intuitively, let’s try to build a

Red-Black Tree that’s unbalanced.

One path can be at most twice

as long another if we pad it
with red nodes.
no Oth
de e r
s n int
e
he eed rna
re to l
! go

Conjecture:
Note, this is just a
the height of a red-black tree conjecture to build
intuition! We’ll prove a
with n nodes is at most 2 log(n) rigorous statement on
the next slide.
 The height of a RB-tree with n non-NIL nodes
 is at most x

• Define b(x) to be the number of black

nodes in any path from x to NIL. y z
• (excluding x, including NIL).
• Claim:
• There are at least 2b(x) – 1 non-NIL
nodes in the subtree underneath x.
(Including x).
• [Proof by induction – on board if time] NIL
 Then: Claim: at least 2b(x) – 1 nodes in this
WHOLE subtree (of any color).
using the Claim

b(root) >= height/2 because of RBTree rules.

Rearranging:
This is great!
• SEARCH in an RBTree is immediately O(log(n)), since
the depth of an RBTree is O(log(n)).

• What about INSERT/DELETE?

• Turns out, you can INSERT and DELETE items from an
RBTree in time O(log(n)), while maintaining the RBTree
property.
• That’s why this is a good property!
INSERT/DELETE
• I expect we are out of time…
• There are some slides which you can check out to see how
to do INSERT/DELETE in RBTrees if you are curious.
• See CLRS Ch 13. for even more details.
• You are not responsible for the details of
INSERT/DELETE for RBTrees for this class.
• You should know what the “proxy for balance” property is
and why it ensures approximate balance.
• You should know that this property can be efficiently
maintained, but you do not need to know the details of how.
INSERT: Many cases
6 6 6

3 7 3 7 3 7

• Suppose we want to insert 0 here.

• There are 3 “important” cases for different colorings of

the existing tree, and there are 9 more cases for all of
the various symmetries of these 3 cases.
 6

INSERT: Case 1 3 7

• Make a new red node.

• Insert it as you would normally. What if it looks like this?

Example: insert 0
6

3 7

0
INSERT: Many cases
6 6 6

3 7 3 7 3 7

• Suppose we want to insert 0 here.

• There are 3 “important” cases for different colorings

of the existing tree, and there are 9 more cases for all
of the various symmetries of these 3 cases.
 6

INSERT: Case 2 3 7

• Make a new red node.

• Insert it as you would normally. What if it looks like this?

• Fix things up if needed.

Example: insert 0
6
No!
3 7

0
 6

INSERT: Case 2 3 7

• Make a new red node.

• Insert it as you would normally. What if it looks like this?

• Fix things up if needed.

Example: insert 0
6
Can’t we just insert 0 as
3 7 a black node?

No!
0
 6
We need a bit more context 3 7

What if it looks like this?

-1 Example: insert 0

3 7
 6
We need a bit more context 3 7

• Add 0 as a red node.

What if it looks like this?

-1 Example: insert 0

3 7

0
 6
We need a bit more context 3 7

• Add 0 as a red node.

• Claim: RB-Tree
properties still hold. What if it looks like this?

-1 Example: insert 0

6 Flip
colors!

3 7

0
 6
But what if that was red? 3 7

What if it looks like this?

-1 Example: insert 0

3 7

0
 6
More context… 3 7

-3
What if it looks like this?

-1 Example: insert 0

3 7

0
 6
More context… 3 7

-3
What if it looks like this?

-1 Example: insert 0

Now we’re basically

inserting 6 into some
smaller tree. Recurse!
This one!
Example, part I
-3

-4 -1

-2 6

3 7

Want to
insert 0
here.
Example, part I
-3

-4 -1

-2 6

3 7

0
Example, part I
-3

-4 -1

-2 6 Flip colors!

3 7

0
Example, part I
-3 Need to know how
to insert into trees
that look like this…

-4 -1
Want to
-2 6 insert 6 here.

3 7

0
INSERT: Many cases That’s this
case!
6 6 6

3 7 3 7 3 7

• Suppose we want to insert 0 here.

• There are 3 “important” cases for different colorings

of the existing tree, and there are 9 more cases for all
of the various symmetries of these 3 cases.
 6

INSERT: Case 3 3 7

• Make a new red node.

• Insert it as you would normally. What if it looks like this?

• Fix things up if needed.

6
Example: Insert 0.
• Maybe with a
3 7 subtree below it.

0
 Recall Rotations
• Maintain Binary Search Tree (BST) property, while
moving stuff around.

YOINK! X Y Y

Y C A B X A X

A B That’s not
bin ary!!
C B C
CLAIM:
this still has BST property.
 6
Inserting into a Red-Black Tree 3 7
• Make a new red node.
• Insert it as you would normally.
• Fix things up if needed. What if it looks like this?

YOINK! Argue that this is a

6 3 good thing to do!

3 7 0 6
0 7
Example, part 2

-3

-4 -1 Want to
insert 6 here.

-2 6

3 7

0
Example, part 2
YOINK!
YOINK!
-3
-1
-4 -1

-3 6
-2 6

3 7
3 7 -4 -2

0 0
Example, part 2 YOINK!

-1

-3 6

3 7
-4 -2
0
Example, part 2 TA-DA!

-1

-3 6

3 7
-4 -2
0
Many cases
6 6 6

3 7 3 7 3 7

• Suppose we want to insert 0 here.

• There are 3 “important” cases for different colorings

of the existing tree, and there are 9 more cases for all
of the various symmetries of these 3 cases.
Deleting from a Red-Black tree

Fun exercise!

Ollie the over-achieving ostrich

That’s a lot of cases!
• You are not responsible for the nitty-gritty details
of Red-Black Trees. (For this class)
• Though implementing them is a great exercise!
• You should know:
• What are the properties of an RB tree?
• And (more important) why does that guarantee that
they are balanced?
What have we learned?
• Red-Black Trees always have height at most 2log(n+1).
• As with general Binary Search Trees, all operations are
O(height)
• So all operations with RBTrees are O(log(n)).
Conclusion: The best of both
worlds

Sorted Arrays Linked Lists Binary Search

Trees*

Search O(log(n)) O(n) O(log(n))

Delete O(n) O(n) O(log(n))

Insert O(n) O(1) O(log(n))

Today
• Begin a brief foray into data structures!
• See CS 166 for more!
• Binary search trees
• You may remember these from CS 106B
• They are better when they’re balanced.

this will lead us to…

• Self-Balancing Binary Search Trees

• Red-Black trees.
Recap
Recap
• Balanced binary trees are the best of both worlds!
• But we need to keep them balanced.
• Red-Black Trees do that for us.
• We get O(log(n))-time INSERT/DELETE/SEARCH
• Clever idea: have a proxy for balance
5
3 7

2 4 6 8
Next time
• Hashing!

Before next time

• Pre-lecture exercise for Lecture 8
• More probability yay!