The algorithm for the insert operation on an AVL tree:
-
Perform a standard BST insert:
a. Traverse the tree looking for where to insert an item, then insert it there. -
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:
Operations:
- 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.