An AVL tree is an improved version of the binary search tree (BST) that is self-balancing. It was named after its inventors Adelson-Velsky and Landis, and was first introduced in 1962, just two years after the design of the binary search tree in 1960. The AVL tree is considered to be the first data structure of its type.
A BST is a data structure composed of nodes. It has the following guarantees:
- Each tree has a root node (at the top).
- The root node has zero or more child nodes.
- Each child node has zero or more child nodes, and so on.
- Each node has up to two children.
- For each node, its left descendants are less than the current node, which is less than the right descendants.
AVL trees have an additional guarantee:
- The difference between the depth of right and left subtrees cannot be more than one.
In order to maintain this guarantee, implementations of AVL trees include an algorithm to rebalance the tree when adding an additional element would cause the difference in depth between the right and left trees to be greater than one.
AVL trees have a worst case lookup, insert and delete time of O(log n).
AVL Insertion Process
This works similarly to a normal binary search tree insertion. After the insertion, you fix the AVL property by using left or right rotations.
- If there is an imbalance in left child of right subtree, then you perform a left-right rotation.
- If there is an imbalance in left child of left subtree, then you perform a right rotation.
- If there is an imbalance in right child of right subtree, then you perform a left rotation.
- If there is an imbalance in right child of left subtree, then you perform a right-left rotation.
Here's an example of an AVL tree in Python: