AVL Trees
Properties of an AVL tree:
  • In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced.
  • Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree.
  • Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
  • The balance factor of a node is the height of its right subtree minus the height of its left subtree and a node with a balance factor 1, 0, or -1 is considered balanced.

Insertion:

  • After inserting a node, it is necessary to check each of the node's ancestors for consistency with the AVL rules.
  • For each node checked, if the balance factor remains 1, 0, or -1 then no rotations are necessary. Otherwise, it's unbalanced.
  • After each insertion, at most two tree rotations are needed to restore the entire tree.

There are four cases, choosing which one depends on different types of unbalanced relations. In the following cases, assume Root is the initial parent before a rotation and Pivot is the child to take the root's place.

 

 

 

Deletion:

  • If a node is a leaf, remove it.
  • If the node is not a leaf, replace it with either the largest in its left subtree (rightmost) or the smallest in its right subtree (leftmost), and remove that node. The node that was found as replacement has at most one subtree.
  • After deletion, retrace the path from parent of the replacement to the root, adjusting the balance factors as needed.
  • More complicated rules for stopping. The retracing can stop if the balance factor becomes -1 or +1 indicating that the height of the subtree has remained unchanged. If the balance factor becomes 0 then the height of the subtree has decreased by one and the retracing needs to continue. This is in contrast to an insertion where a rotation resulting in a balance factor of 0 indicated that the subtree's height has remained unchanged.

Overall, the time required is O(log n) for lookup, plus a maximum of O(log n) rotations on the way back to the root, so the deletion can be completed in O(log n) time.

Lookup (Search):

Lookup in an AVL tree is exactly the same as in an unbalanced BST. Because of the height-balancing of the tree, a lookup takes O(log n) time.

Example. Insert 14, 17, 11, 7, 53, 4, 13, 12, 8 into an empty AVL tree and then remove 53, 11, 8 from the AVL tree.  Please take a look at the following slides for AVL tree insertion and deletion animation (use the slide show mode).