[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

Search Tree

T-----> a
          .
            .
              b
                .
                  .
                    c
                      .
                        etc.
where height(T) is about n

Search Tree

One might imagine that a weight-balanced tree

where   | weight(R) - weight(L) |   is as small as possible would be a good idea.

But . . . it is hard to maintain.

Search Tree.

Define:

T is an AVL Tree   if T is a binary search tree, and . . .

©
L
.
A
l
l
i
s
o
n
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

A legal AVL Tree:
-
becomes unbalanced by insertion:
-
balance is restored by a ``Left-2'' rotation:
-

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

[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

© 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).