Course Outline

Introduction and Algorithm Analysis (Ch. 2)

Hash Tables: dictionary data structure (Ch. 5)
Heaps: priority queue data structures (Ch. 6)
Balanced Search Trees: general search structures (Ch. 4.1-4.5)
Union-Find data structure (Ch. 8.1–8.5)
Graphs: Representations and basic algorithms
 Topological Sort (Ch. 9.1-9.2)

 Minimum spanning trees (Ch. 9.5)

 Shortest-path algorithms (Ch. 9.3.2)

B-Trees: External-Memory data structures (Ch. 4.7)

kD-Trees: Multi-Dimensional data structures (Ch. 12.6)
Misc.: Streaming data, randomization

0
Search Trees
Searching over an ordered universe of key values.
Maintaining hierarchical information

Repeated linear search in link list too slow for large data
Hashing useful only for “find key” operations.
Heaps useful only for “find Min” or “Find Max”.

But suppose we needed:

 Lookup-by-prefix:
 type in first few letters of a name and output all names in the database beginning
with those letters.
 Find-in-range[key1, key2]: output all keys between key1 and key2
 NearLookup(x): returns the closest key to x when x not in database.
 Find the kth smallest key.
 Rank(x): how many keys are smaller than x.

1
Search Trees
n With appropriate balanced binary search trees, we can do most of
these operations in worst-case O(log n) time.
 searches, inserts, deletes, find successor, find predecessor etc.

n A recursive definition of the tree:

 either empty, or

 a root node r with 0 or subtrees whose roots are children of r

 No other structure: arbitrary distribution of keys and depths

root

T2 T3 T4 ...
T1 T10

2
Search Trees
Some definitions:
 Path: a sequence of edges or nodes

 Path Length: number of edges

 Depth of a node: number of edges from the root

 Parent-Child relationship

 Ancestor-Descendant

B C D E F G

H I J K L M N

P Q

3
An example: directory structure
File directories have a natural tree (hierarchical) structure
Directory traversal and search best visualized by search trees
Tree Traversals:
 List all sub-directories: Pre-Order Traversal
 Print a node, then recursively traverse subtrees
 Compute directory sizes: Post-Order traversal
 Compute sizes of all subtrees, then add to get the size of the directory

/usr*

mark* alex* bill*

book* course* junk junk work* course*

ch1.r ch2.r ch3.r cop3530* cop3212*

fall* spr* sum* fall* fall*

syl.r syl.r syl.r grades prog1.r prog2.r prog2.r prog1.r grades

4
Binary Search Trees (BST)
Each node has at most 2 children (left, right)
 Most commonly used form of search tree

 Some examples: Heaps, expression trees, branch-bound

 BST implements a search ADT

 Input: a set of keys

 Any set with an ordering, but assume numeric keys for simplicity
 For simplicity, also assume all keys are distinct (no duplicates)

A BST is a tree with the following “ordering” property

 For any node X:

 All keys in the left subtrees < key(X)

 All keys in the right subtree > key(X)

5
Binary Search Trees (BST)

A Binary Search Tree is a tree with the following “ordering” property

 For any node X:
 All keys in the left subtrees < key(X)
 All keys in the right subtree > key(X)

 Which of the following are valid BSTs?

6 6

2 8 2 8

1 4 1 4

3 3 7

6
Find (lookup) Operation in BST
if (t = null) return null
elseif (x < t.key) return find(x, t.left)
elseif (x > t.key) return find(x, t.right)
else return t; // match

6 6

2 8 2 8

1 4 1 4

3 3 7

7
FindMin or FindMax in BST
FindMax
if (t != null)
while (t.right != null)
t = t.right
return t;

6 6

2 8 2 8

1 4 1 4

3 3 7

8
Insert Operation in BST
n Do find(X). If X found, nothing to do.
n Otherwise, insert X at the last spot on the path.

if (t = null)
t = new node x; // insert x here //
elseif (x < t.key) Insert(x, t.left)
elseif (x > t.key) Insert(x, t.right)
else;
6 6

2 8 2 8

1 4 1 4

3 3 7
9
Delete Operation in BST
n Delete is typically the most complex operation.

a. if the node X is a leaf, easily removed.

b. if node X has only one child, then just bypass it (make the
child directly linked to X). Example. Delete 4

6 6

2 8 2 8

1 4 1 4

3 3
10
Delete Operation in BST
c. if node X has two children,
replace with the smallest node in the right subtree of X;
recursively delete that node.

the second deletion turns out to be easy;

because the second node can't have two children.

11
Example of Delete
Delete 2.
Swap it with Min in Right Subtree (3). Then Delete (3).

6 6

2 8 3 8

1 5 1 5

3 3

4 4

12
Analysis of BST
In the worst-case, BST on n nodes can have height n-1.
Each insert/delete takes O(height) time, same as linked list.
For better worst-case, tree needs to be kept balanced
 Namely, height O(log n) with n keys

Given a set of keys, easy to build a perfect BST initially:

 use the median division rule.

The problem begins when we start doing insert, delete ops.

Suppose we start from an empty tree and do a series of
insertions, what does the tree look like.
 Of course, the worst-case is a path: linear depth

 What about if insert and deletes were random?

13
Analysis of BST
Analysis shows that if insertions are done randomly (keys
drawn from [1,n]), then average depth is log n.
The sum of the depths of all the nodes is O(n log n).

Let D(n) be the internal path length.

If i nodes in the left, and (n – i - 1) on the right, then
D(n) = D(i) + D(n - i - 1) + (n - 1).
Under random insertions, the value of i varies uniformly
between 0 and n-1, and so
D(n) = 2/n ( D(j)) + (n-1)

A famous recurrence, which solves to D(n) = O(n log n).

14
15
randomly generated

Alternate insertions
and deletions
AVL trees
AvL Trees are a form of balanced binary search trees
Named after the initials of their inventors
 Adelson-Velskii and Landis

 One of the first to achieve provable guarantee of

O(log n) worst-case for any sequence of insert and
delete operations.
 A binary tree cannot do better!

16
AVL trees
How do we ensure that an AVL tree on n nodes has height
O(log n) even if an adversary inserts and deletes key to get
tree out of balance?
Simply requiring that the left and right children of the root
node have the same height is not enough:
 They can each have singly branching paths of length n/2

17
Balance Conditions for AVL trees
Demanding that each node should have equal height for
both children too restrictive---doesn’t work unless n = 2k – 1
AVL Trees aim for the next best thing:
 For any node, the heights of its two children can differ by at most 1
 Define height of empty subtree as -1
 Height of a tree = 1 + max{height-left, height-right}
 Which of the following are valid AVL trees?

5 7

2 8 2 8

1 4 7 1 4

3 3 5

18
Height of AvL Trees
Theorem: An AVL tree on n nodes has height O(log n)
What is the minimum number of nodes in a height h AvL tree.
What is the most lop-sided tree?

19
Bound for the Height of AvL Trees
n Recursive construction
n Let S(h) = min number of nodes in AVL tree of height h

S(h) = S(h-1) + S(h-2) + 1

Like Fibonacci numbers. Solves to h = 1.44 log (n+2).

20
Keeping AVL Trees Balanced
n Theorem: An AVL tree on n nodes has height O(log n)

n Building an initially balanced tree on n keys is easy.

n The problem is insertions/deletions cause unbalance.
n AVL trees perform simple restructuring operations on the
tree to regain balance.
n These operations, called rotations, change a couple of
pointers.

n We will show that an insert, delete, or search operations

touches O(1) nodes per level of the tree, giving O(log n)
bound.

21
Tree Rotations

right rotation
b
d

d
b

A
E
C E
A C
left rotation

22
AVL Tree Rebalancing
We only discuss inserts; deletes similar though a bit more
messy.
How can an insert violate AVL condition?
Before the insert, at some node x the height difference
between children was 1, but becomes 2 after the insert.
We will fix this violation from bottom (leaf) up.

23
AVL Tree Rebalancing
n Suppose A is the first node from bottom that needs rebalancing.
n Then, A must have two subtrees whose heights differ by 2.
n This imbalance must have been caused by one of two cases:

(1) The new insertion occurred into

the left subtree of the left child of A; or
the right subtree of the right child of A.

(2) The new insertion occurred into

the right subtree of the left child of A; or
the left subtree of the right child of A.

(1) and (2) are different: former is an outside (left-left, or right-right)

violation, while the latter is an inside (left-right) or (right-left) violation.

We fix (1) with a SINGLE ROTATION; and (2) with a DOUBLE ROTATION.

24
Single Rotation

n Insert 6. Where is the AVL condition violated?

n Case (1): insertion into the left subtree of the left child of A
n Fixed by rotation at 7.

5 5

2 8 2 7

1 4 7 1 4 6 8

3 6 3

25
Single Rotation: Generic Form

k2 k1

k1 k2
Z
X
Y Y Z
X

k1 k2

k2 k1
X

Y X Y Z
Z

26
Single Rotation: Example
Perform inserts in the following order:
3, 2, 1, 4, 5, 6, 7.

27
Failure of the Single Rotation

Single rotation can fail in case (2):

 Insert into right subtree of left child or vice versa

k2 k1

k1 k2
Z X

X Z
Y Y

28
When Single Rotation Fails: Double Rotation

Need to look one level deeper.

Called Double Rotation: generic form
One of B or C is at level D+2.

k3 k2

k1 k1 k3
k2 D
B C
A A D
B C

29
Double Rotation: Example
To the example of previous AVL tree (keys 1-7),
insert 16, 15, 14, …., 10, followed by insert 8, 9

30
Removing an element from an AVL tree
Similar process:
 locate & delete the element

 adjust tree height

 perform up to O(log n) necessary rotations

Example

Complexity of operations:
 O(h) = O(log n)
n : number of nodes, h : tree height

31
Deletion Example
15 delete 10 15

10 30 5 30
5 12 17 35 12 17 35
14 20 31 40 14 20 31 40
50 50

30 15

15 35 12 30
12 17 31 40 5 14 17 35
5 14 20 50 20 31 40
50
32
AVL Tree Complexity Bounds
An AVL Tree can perform the following operations
in worst-case time O(log n) each:
 Insert

 Delete

 Find

 Find Min, Find Max

 Find Successor, Find Predecessor

 It can report all keys in range [Low, High] in time

O(log n + OutputSize)

33
More illustrations… Single Rotation (left-left)

1
2

2
1
Z

X Y Z
Y

Y cannot be at X’s level

Y cannot be at Z’s level either

34
Single Rotation (right-right)

1 2

2 1

X
Z
Y X Y

Y cannot be at Z’s level

Y cannot be at X’s level either

35
Double Rotation (left-right): Single Won’t Work
Single rotation does not work because it does not make
Y any shorter
1
2

2
1
Z X

Z
X
Y Y

36
Double Rotation (left-right): First Step
First rotation between 2 and 1

3 3

1 2
D
D 1
2
C
A
B
B C
A

37
Double Rotation (left-right): Second Step
Second rotation between 2 and 3

3 2

3
2 1
D
1
C B C D
A
B
A

38
Double Rotation (left-right): Summary

2
3

3
1 1

D
2
B C D
A A

B C

39
Double Rotation (right-left): First Step
First Rotation between 2 and 3

1 1

3 2

A A
2 3
B
D
C
B C D

40
Double Rotation (right-left): Second Step
Second Rotation between 1 and 2

2
1

2 3
1
A
3
B B C D
A
C
D

41
Double Rotation (right-left): Summary

2
1

3 3
1
A
2
B C D
D A

B C

42
Insertion into an AVL tree AvlTree
AvlNode
Tree height element

right
left
Search height

Insertion: AvlTree::insert(x, t)
 search to find if (t = NULL)
then t = new AvlNode(x, …);
insertion point else if (x < t→element)
then
 adjust the tree insert (x, t→left);
height if (height(t→left) – height(t→right) = 2)
then if (x < t→left→element )
 rotation if necessary then rotateWithLeftChild (t);
else doubleWithLeftChild (t);
else if (t→element < x )
then
insert (x, t→right);
if (height(t→right) – height(t→left) = 2)
then if (t→right→element < x)
then rotateWithRightChild (t);
else doubleWithRightChild (t);
t→height =
max{height(t→left), height(t→right)}+1;
43