AVL Trees

Not in textbook

22 minute video of this page.

AVL TREE: A type of self-balancing binary search tree.

SELF-BALANCING BINARY SEARCH TREE: AVL TREE SEARCH: INSERT algorithm: DELETE a node algorithm:

Here's a JAVA web-page animation of the find, insert, delete and inorder-scan algorithms for AVL (and other) binary trees.

HOMEWORK: Be prepared to show your work to the class.
Use the tree in example 10-8 page 537:

                               59
                              /   \
                            40     70
                           /  \    /
                          8   45  60
                           \
                           26

Is this tree an AVL tree? (i.e. is it height balanced?)
Use the binary search algorithm to find where would 24 be added to this tree.
What's the smallest sub-tree that becomes unbalanced after adding 24?
Select the correct case and perform one or two rotations to re-balance the tree.

My Solution

Prev
Next