Lecture 09

This lecture discusses balanced search trees, focusing on red-black trees and 2-3 trees, which ensure O(log n) height for efficient searching and insertion. Red-black trees utilize color properties to maintain balance, while 2-3 trees are simpler with nodes having 2 or 3 children. The lecture also covers operations like insertion, deletion, and the theoretical height of red-black trees.

Uploaded by

benno0810

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

7 views40 pages

Lecture 09

Uploaded by

benno0810

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Introduction to Algorithms

6.046J/18.401J

Lecture 9
Prof. Piotr Indyk
Today
• Balanced search trees,
or how to avoid this 1
even in the worst case 2
3
4
5
6

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.2
Balanced search trees
Balanced search tree: A search-tree data
structure for which a height of O(lg n) is
guaranteed when implementing a dynamic
set of n items.
• AVL trees
• 2-3 trees
Examples: • 2-3-4 trees
• B-trees
• Red-black trees

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.3
Red-black trees
BSTs with an extra one-bit color field in
each node.
Red-black properties:
1. Every node is either red or black.
2. The root and leaves (NIL’s) are black.
3. If a node is red, then its parent is black.
4. All simple paths from any node x to a
descendant leaf have the same number
of black nodes.
© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.4
Example of a red-black tree
77

33 18
18
NIL NIL
10
10 22
22
NIL
88 11
11 26
26
NIL NIL NIL NIL NIL NIL

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.5
Use of red-black trees
• What properties would we like to prove about
red-black trees ?
– They always have O(log n) height
– There is an O(log n)–time insertion
procedure which preserves the red-black
properties
• Is it true that, after we add a new element to a
tree (as in the previous lecture), we can always
recolor the tree to keep it red-black ?
© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.6
Example of a red-black tree
77

33 18
18

10
10 22
22

88 11
11 26
26
7.5
7.5

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.7
Use of red-black trees
• What properties would we like to prove about red-
black trees ?
– They always have O(log n) height
– There is an O(log n)–time insertion procedure
which preserves the red-black properties
• Is it true that, after we add a new element to a tree (as
in the previous lecture), we can always recolor the
tree to keep it red-black ?
• NO
• After insertions, sometimes we need to juggle nodes
around
© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.8
Rotations
BB RIGHT-ROTATE(B) AA
AA LEFT-ROTATE(A) BB
γγ αα
αα ββ ββ γγ

Rotations maintain the inorder ordering of keys:

• a ∈ α, b ∈ β, c ∈ γ ⇒ a ≤ A ≤ b ≤ B ≤ c.
A rotation can be performed in O(1) time.
© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.9
Rotations can reduce height
B A
2 1
LEFT-ROTATE(A) B
A 1 3 γ 2 γ
3

BB AA

AA BB
γγ αα
αα ββ ββ γγ

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.10
Red-black tree wrap-up
• Can show how
– O(log n) re-colorings
– 1 rotation
can restore red-black properties after an
insertion
• Instead, we will see 2-3 trees (but will come
back to red-black trees at the end)

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.11
2-3 Trees
• The simplest balanced trees on the planet!
• Although a little bit more wasteful

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.12
2-3 Trees
• Degree of each node is 12
either 2 or 3
• Keys are in the leaves
6 8 12
• All leaves have equal
depth
• Leaves are sorted 1 5 6 7 8 9 12
• Each node x contains
maximum key in the
sub-tree, denoted
x.max
© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.13
Internal nodes
• Internal nodes:
– Values:
• x.max: maximum key in the sub-tree
– Pointers:
• left[x]
• mid[x]
• right[x] : can be null
• p[x] : can be null for the root
•…
• Leaves:
– x.max : the key

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.14
Height of 2-3 tree
• What is the maximum height h of a 2-3 tree
with n nodes ?
• Alternatively, what is the minimum number of
nodes in a 2-3 tree of height h ?
• It is 1+2+22+23+…+2h =2h+1-1
• n ≥ 2h+1-1 ⇒ h = O(log n)
• Full binary tree is the worst-case example!

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.15
Searching
• How can we search for a 12
key k ?
Search(x,k):
• If x=NIL then return NIL
• Else if x is a leaf then 6 8 12
– If x.max=k then return x
– Else return NIL
• Else 1 5 6 7 8 9 12
– If k ≤ left[x].max
then Search(left[x],k)
– Else if k ≤ mid[x].max Search(8)
then Search(mid[x],k)
Search(13)
– Else Search(right[x],k)

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.16
Insertion
• How to insert x ? 12
13
• Perform Search for the
key of x
• Let y be the last internal 6 8 12
13
node
• Insert x into y in a
sorted order 1 5 6 7 8 9 12
• At the end, update the
5.5 13
max values on the path 7.5
to root Insert(7.5)
(continued on the next Insert(13)
slide)
Insert(5.5)
© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.17
Insertion, ctd.
(continued from the 12
13
previous slide)
• If y has 4 children, 6 y 8 12
13
then Split(y)
1 5 6 7 8 9 12
5.5 13
7.5
x

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.18
z
Split
y
• Split y into two nodes
y1, y2
• Both are linked to a b c d
z=parent(y)*
z
• If z has 4 children, split z

*If y is a root, then create y1 y2

new parent(y)=new root
a b c d
© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.19
Split

12
13

6 8 12
13

1 5 6 7 8 9 12
5.5 13
7.5

12
13

5.5 6 8 12
13

1 5 5.5 6 7 8 9 12
13
7.5

6 13

5.5 6 8 12
13

1 5 5.5 6 7 8 9 12
13
7.5
• Insert and Split preserve heights, unless new root is created, in which case all heights are
increased by 1
• After Split, all nodes have 2 or 3 children
• Everything takes O(log n) time

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.22
Delete
12
• How to delete x ?
6 12
• Let y=p(x)
• Remove x from y z
5.5 6 8 y 12
• If y has 1 child:
– Remove y 1 5 5.5 6 7 8 9 12
– Attach x to y’s sibling z x

Delete(8)

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.23
Delete
12
• How to delete x ?
6 12
• Let y=p(x)
• Remove x from y z
5.5 6 12
• If y has 1 child:
– Remove y 1 5 5.5 6 7 9 12
– Attach x to y’s sibling z
• If z has 4 children, then
Split(z) Delete(8)
INCOMPLETE – SEE THE END FOR FULL VERSION
© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.24
Summing up
• 2-3 Trees:
– O(log n) depth ⇒ Search in O(log n) time
– Insert, Delete (and Split) in O(log n) time
• We will now see 2-3-4 trees
– Same idea, but:
• Each parent has 2,3 or 4 children
• Keys in the inner nodes
• More complicated procedures

5 9

1 2 4 7 8 10 12

© Piotr Indyk and Charles E. Leiserson Introduction to Algorithms October 13, 2004 L9.26
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).