Discrete Math. for Engineering, 2005.
Application slides 5
c Theodore Norvell, Memorial University
Application: AVL trees and the golden
ratio
AVL trees are used for storing information in an efficient
manner.
We will see exactly how in the data structures course.
This slide set takes a look at how high an AVL tree of
a given size can be.
The golden ratio
1+ 5
2
The golden ratio is an irrational number =
with many interesting properties. Among them
1 = 1/
= 1 + 1+
= 1.618
1
1+
. . .1
turns up in many geometric figures including
pentagrams and dodecahedra
It is the ratio, in the limit, of successive members of
the Fibonacci sequence
Typeset October 31, 2005
Discrete Math. for Engineering, 2005. Application slides 5
c Theodore Norvell, Memorial University
Binary trees
A binary tree is either
The empty binary tree, for which Ill write
Or a point (called a node) connected to two smaller
binary trees (called its children)
The children must not share any nodes.
An empty
binary tree
A nonempty
binary tree
Typeset October 31, 2005
Another
nonempty
binary tree
Discrete Math. for Engineering, 2005. Application slides 5
c Theodore Norvell, Memorial University
The height and size of a binary tree
The size of a binary tree is the number of nodes it has.
The height of a binary tree is number of levels of nodes
it has
height is 3
size is 5
Note that has height 0 and size 0.
Clearly a binary tree of size n can have a height of up to
n.
When binary trees are used to store data:
The amount of information stored is proportional to
size of tree
The time to access data is proportional to the height
Typeset October 31, 2005
Discrete Math. for Engineering, 2005. Application slides 5
c Theodore Norvell, Memorial University
AVL trees
AVL trees are binary trees with the following restrictions.
The empty tree is an AVL tree
A nonempty binary tree is AVL if
the height difference of the children is at most 1,
and
both children are AVL trees
AVL
Typeset October 31, 2005
Not AVL
Not AVL
Discrete Math. for Engineering, 2005. Application slides 5
c Theodore Norvell, Memorial University
The question
We wish to access large amounts of data quickly.
Remember amount of information is proportional to
size of tree
and access time is proportional to the height of the
tree.
So the question is how high can an AVL tree of a given
size be?
We start by asking a closely related question:
How small can an AVL tree of a given height be?
Typeset October 31, 2005
Discrete Math. for Engineering, 2005. Application slides 5
c Theodore Norvell, Memorial University
How small can an AVL tree of a given
height be?
Lets make a table with the smallest AVL tree of each
height
(empty trees are implied)
Height
0
Size
0
Typeset October 31, 2005
Smallest tree
12
Discrete Math. for Engineering, 2005. Application slides 5
c Theodore Norvell, Memorial University
The minsize function
In the table, each tree (of height h > 1) has, as children,
smallest trees of heights h 2 and h 1
So we have
minsize(0) = 0
minsize(1) = 1
minsize(h) = minsize(h 1) + minsize(h 2) + 1, for h 2
Note the recurrence is not homogeneous.
Try a few values
0, 1, 2, 4, 7, 12, 20, 33, 54
Compare with the Fibonacci sequence
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
We find
minsize(h) = fib(h + 1) 1
where
fib(0) = 1
fib(1) = 1
fib(n) = fib(n 1) + fib(n 2), for n 2
We can prove this by (complete induction).
Typeset October 31, 2005
c Theodore Norvell, Memorial University
Discrete Math. for Engineering, 2005. Application slides 5
Since fib is defined by a linear homogeneous recurrence
relation of degree 2 we can solve it
1
1
1
fib(n) = n+1 ( )n+1 for all n N
5
5
where
1+ 5
=
2
n+1
1
1
1
Consider 5
5 ( )n+1 for n R and n 0.
The first term is real, the second is complex.
As n gets big, the complex term becomes small.
So we get minsize(h)
= 15 h+2 1
12
10
size 6
0
1
minsize(h) dots
Typeset October 31, 2005
height
1
5
h+2 1 line
8
Discrete Math. for Engineering, 2005. Application slides 5
c Theodore Norvell, Memorial University
The maximum height per given size
Height 0 1 2 3 4 5
Min size 0 1 2 4 7 12
Let h0 be the height of a tree of size s0. We know that for
all h,
h0 h s0 minsize(h)
Contrapositively: For all h,
s0 < minsize(h) h0 < h
Size
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Max height 0 1 2 2 3 3 3 4 4 4 4 4 5 5 5
Note that for s such that minsize(h 1) < s minsize(h)
maxheight(s) = h
maxheight(s) is approximately an inverse of minsize(h)
Typeset October 31, 2005
Discrete Math. for Engineering, 2005. Application slides 5
c Theodore Norvell, Memorial University
h+2 1
1
s = h+2 1
5
h+2
5 (s
+
1)
=
log 5 (s + 1) = h + 2
log 5 (s + 1) 2 = h
So invert
1
5
log 2 log2(s + 1) + log 5 2 = h
so maxheight(s)
= 1.44 log2(s + 1) 0.3
For example
maxheight(106)
= 29
maxheight(109)
= 43
maxheight(1012)
= 58
This means large amounts of data can be accessed in a
small amount of time, if we store the data in AVL trees.
Typeset October 31, 2005
10
c Theodore Norvell, Memorial University
Discrete Math. for Engineering, 2005. Application slides 5
Graphing maxheight
6
5
4
h3
2
1
0
maxheight(s) dots
Typeset October 31, 2005
10
s
12
14
16
18
20
1.44 log2(s + 1) 0.3 line
11
