[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:49: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 . . .

### Search Tree

• Worst-case performance of search trees comes from degenerate List-like Trees

```T-----> a
.
.
b
.
.
c
.
etc.
```

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:

### 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, Sunday, 28-Nov-2021 04:49:13 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/10AVL.shtml
Computer Science, Software Engineering, Science (Computer Science).