----- NEEDS JAVASCRIPT ON. -----
[Subject home ],
[FAQ ],
[progress ],
Bib' ,
Alg's ,
C ,
Java
- L.A. ,
Thursday, 28-Mar-2024 23:00:13 AEDT
Instructions :
Topics discussed in these lecture notes are examinable
unless otherwise indicated.
You need to follow instructions,
take more notes &
draw diagrams especially as [indicated] or
as done in lectures,
work through examples, and
do extra reading.
Hyper-links not in [square brackets] are mainly for revision,
for further reading, and for lecturers of the subject.
Tables: AVL Trees: Introduction
Remember: A Lookup Table is an ADT
with operations:
clear, lookup, insert, delete, & empty?
which obey certain
rules .
A table can be implemented in many ways
e.g. by
search tree
average time for lookup, insert, delete O(log(n))
worst case time is O(n).
We can improve worst-case to O(log(n)) by using
a height balanced tree ,
e.g. an AVL-tree . . .
Worst-case performance of search trees comes
from degenerate List-like Trees
T-----> a
.
.
b
.
.
c
.
etc.
where height(T) is about n
Search Tree
One might imagine that a weight-balanced tree
weight( empty_tree ) = 0
weight( fork E L R ) = 1 + weight(L) + weight(R)
where | weight(R) - weight(L) | is as small as possible
would be a good idea.
But . . . it is hard to maintain.
Search Tree .
Define:
height( empty_tree ) = 0
height( fork E L R ) = 1 + max( height(L), height(R) )
T is an AVL Tree
if T is a binary search tree, and . . .
T = empty_tree, or
T = fork( E, L, R ), and . . .
| height(R) - height(L) | <= 1
L and R are AVL trees
Search Tree
e.g. fred(-1)
. .
. .
. .
ann(0) george(0)
. .
. .
. .
alan(0) carol(0)
A small AVL Tree
( ? ) = height(right) - height(left) = -1, 0, or +1
Search Tree
AVL, insertion
initially as for binary search tree, but
balance may be upset, so
rotations may be needed to restore . . .
A legal AVL Tree:
becomes unbalanced by insertion:
balance is restored by a ``Left-2'' rotation:
NB. ``Rotation'' is perhaps a misnomer (but common terminology)
L is promoted, T is demoted
left to right ordering is maintained [why_________?].
Lecturer: derive code for pointer manipulation in a left-2 rotation;
class: copy it here:
Another legal AVL tree:
becomes unbalanced by insertions:
balance is restored by a ``left-3'' rotation:
Lecturer: derive code to do the pointer manipulation in a left-3 rotation;
class: copy it here:
If T is an AVL-tree containing `n ' elements,
then h = height(T) is O(log(n ))
Proof
let n(h) = min # elts in a tree of height h
n(1) = 1, n(2) = 2
n(h) = n(h-1) + n(h-2) + 1
so n(h) > 2 × n(h-2)
so n > 2h/2 ,
i.e. h < 2 log(n)
[lecturer: draw max height trees for n = 1, 2, ... ]
[class: add them to these notes!]
Use the
[demo' ].
Predict how an insertion will change the current AVL tree,
use `insert', were you correct?
Tables: AVL Trees: Summary
| height(right) - height(left) | <= 1, etc.
height(T) is O(log(n)), so . . .
insertion and deletion O(log(n))-time, all cases
balance can be restored by
Left-2- , Left-3- , Right-2- , and Right-3- rotations
as recursion "unwinds".
There are other height balanced trees, e.g.
2-3- ,
2-3-4-, and B-trees [-- coming soon, prepare ]
There are also many other types of tree.
© L.Allison ,
Thursday, 28-Mar-2024 23:00:13 AEDT
users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/10AVL.shtml
Computer Science,
Software Engineering,
Science (Computer Science).