Data Structures and Algorithms

AVL Trees

Printable Version


Here are some terms that are used when discussing AVL trees:
Note that terms like favorite and linear are not found in other AVL search tree descriptions. They are used here in order to remove leftness and rightness issues from the main AVL tree algorithms.

AVL properties

An AVL tree has the following properties:
The balance factor marks which child is the root of the taller subtree and is computed by subtracting the height of the right child's subtree from the height of the left child's subtree. This means that an AVL tree is nearly as balanced as it can be with just a little bit of slop allowed. Red-black trees, on the other hand, allow a good deal more slop with regards to balance.

Next: Inserting into AVL trees