What is an AVL tree?

An AVL tree is a self-balancing binary search tree where the difference of heights of left and right subtrees cannot be more than one.

In more detail, an AVL (Adelson-Velsky and Landis) tree is a type of binary search tree that was invented by two Soviet inventors, G.M. Adelson-Velsky and E.M. Landis, in 1962. The unique feature of an AVL tree is its self-balancing property. This means that it automatically adjusts its height to ensure that the tree remains balanced as much as possible. This is achieved by ensuring that the difference in the height of the left and right subtrees of any node in the tree is not more than one. This difference is often referred to as the 'balance factor'.

The balance factor of a node in an AVL tree is the height of the left subtree minus the height of the right subtree. If the balance factor is more than 1 or less than -1, the tree is considered unbalanced and a rotation is performed to restore balance. There are four types of rotations: left-left, right-right, left-right, and right-left. The type of rotation performed depends on whether the unbalanced node is on the left or right subtree and whether the unbalanced node is caused by an insertion in the left or right subtree.

The main advantage of an AVL tree is that it guarantees O(log n) time complexity for search, insert, and delete operations. This is because the height of the tree is always logarithmic in the number of nodes. This makes AVL trees very efficient for database and indexing systems where fast retrieval is crucial.

However, maintaining the balance of an AVL tree can be computationally expensive, as it may require multiple rotations after each insertion or deletion. This makes AVL trees less suitable for situations where the tree is modified frequently. Despite this, the AVL tree is a fundamental concept in computer science and provides a solid foundation for understanding more complex self-balancing trees.