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

- Named for the people who invented it in 1962: G.M. Adelson-Velskii and E.M. Landis
- Search, insertion, and deletion all take O(log
_{2}n) time even in the worst case.

- Any binary search tree that automatically keeps its height small, even with arbitrary insertions and deletions.
- Types of self-balancing binary search trees:
- AVL Tree
- Red-Black tree (chap 12, we won't study)
- Several others we won't study

- Exactly as in an ordinary (unbalanced) binary search tree.
- Because of the height-balancing of the tree, a lookup takes O(log
_{2}n) time, even in the worst case.

- Scan (like binary search) tree for correct insertion point.
- After inserting a node, check each of the node's ancestors for balance and rotate if needed. There are 4 cases as shown in the diagram below.
- At most 2 rotations will be needed to re-balance the tree after an
insertion as shown below:

Figure from wikipedia.org - C++ re-balancing code for each case.
- Example:
Start with : 7 Insert 11: 7 Node 12 becomes unbalanced (2-0) / \ / \ 9 is root in above diagram. 4 12 4 12 11 is pivot in above diagram. / / Left-right case. 9 9 \ 11 Rotate left: 7 Rotate right: 7 Now tree is balanced again. / \ / \ Difference in depth of any 4 12 4 11 left and right sub-tree is / / \ 0 or 1. 11 9 12 / 9

- If node is a leaf, just delete it.
- If not not a leaf, replace it with either the largest in its left subtree (inorder predecessor) or the smallest in its right subtree (inorder successor), and remove that node (see diagram below).
- The node that was found as replacement has at most one subtree.
- After deletion, retrace the path back up the tree (parent of the replacement) to the root, adjusting the balance factors as needed. Stop when you come to a subtree that's already balanced.
- Maximum of O(log
_{2}n) rotations.

Figure from wikipedia.org - Example: Delete 4:
Start with: 7 Delete 4: 7 Root is unbalanced (2-0) / \ \ Rotate left: 11 4 11 11 / \ / \ / \ 7 12 9 12 9 12 \ 9

- Example 2: Delete 7:
Start with: Repl with 6(largest left). 7 6 / \ / \ 4 11 4 11 \ / \ / 6 9 5 9 / 5 Resulting tree happens to be balanced. If not check ancestors of 6 for balance.

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.