AVL Insert - Maintaining the AVL Invariant

The algorithm for the insert operation on an AVL tree:

  1. Perform a standard BST insert:
    a. Traverse the tree looking for where to insert an item, then insert it there.

  2. Fix the AVL Property from the changed node up.
    a. Suppose 'x' is the lowest node that is not AVL. To find this: start at the changed node, check the heights of its children, and walk upwards doing the same until we reach a non-AVL node. b. Assume that right(x) is heigher than left(x) (It could be the left; it's symmetric, so it doesn't matter).

    c. If x's right child is right-heavy or balanced, we right-rotate x.

    d. Else x's right child is left-heavy, in which case we do two rotations: right-rotate the right child, then left-rotate x.

AVL Sort

  • Insert n items (takes O(nlogn) time)
  • Perform in-order traversal (takes O(n) time)

AVL as an Abstract Data Type:

  • Insert
  • Delete
  • Min
  • Successor / Predecessor

Just "insert" and "min" form a priority queue. To get all four of the operations, you'll need some form of Balanced Binary Search Tree.