AVL Tree Introduction

An AVL tree is a self-balancing binary search tree in which the heights of the left and right subtrees of every node differ by at most 1. It is named after its inventors, Adelson-Velsky and Landis.

The key feature of an AVL tree is that it maintains its balance through automatic rotations whenever necessary. These rotations help keep the tree height-balanced, ensuring efficient operations like insertion, deletion, and searching.

In an AVL tree, the balance factor of a node is defined as the height of its left subtree minus the height of its right subtree. The balance factor can be -1, 0, or 1 for each node. If the balance factor exceeds these limits, it means the tree is unbalanced, and rotations are performed to restore balance.


The rotations performed in an AVL tree are:

Left Rotation: It is performed when the balance factor of a node becomes greater than 1, indicating that the tree is leaning to the right.

Right Rotation: It is performed when the balance factor of a node becomes less than -1, indicating that the tree is leaning to the left.

Left-Right Rotation: It is a combination of left and right rotations and is performed when a node has a balance factor greater than 1 and its right child has a balance factor less than 0.

Right-Left Rotation: It is a combination of right and left rotations and is performed when a node has a balance factor less than -1 and its left child has a balance factor greater than 0.

By performing these rotations, the AVL tree maintains a balanced structure, resulting in efficient search, insertion, and deletion operations with a worst-case time complexity of O(log n), where n is the number of nodes in the tree.


Overall, AVL trees are an important data structure in computer science that provides efficient and balanced storage of data, ensuring fast access and manipulation operations.

Example

Example of AVL Tree, Order of Inserting numbers - 51, 26, 11, 6, 8, 4, 31

AVL Tree vs Balanced BST

Both balanced trees and AVL trees are methods of maintaining balance in binary search trees, but there are some differences between them.


Balanced Tree: In a balanced tree, the absolute difference in height between the left and right subtrees of any node is at most 1.

AVL Tree: In an AVL tree, the difference in height between the left and right subtrees of every node is at most 1.

Balanced Tree: Balanced trees may use different balancing operations depending on the implementation, such as rotation, node promotion/demotion, or tree reconstruction.

AVL Tree: AVL trees specifically use rotations to balance the tree. They perform rotations whenever necessary to maintain the balance factor of each node within the acceptable range.

Balanced Tree: Balanced trees aim to keep the tree relatively balanced, but they may tolerate a higher imbalance for the sake of optimizing other operations, such as insertion or deletion.

AVL Tree: AVL trees strictly enforce balance by performing rotations as soon as a violation occurs. This ensures that the tree remains balanced at all times, which guarantees a height of O(log n) for the tree.

Balanced Tree: Balanced trees provide reasonably efficient operations with average-case time complexity of O(log n), but worst-case scenarios may arise in certain situations.

AVL Tree: AVL trees provide guaranteed worst-case time complexity of O(log n) for all operations, including search, insertion, and deletion.

In summary, AVL trees are a specific type of balanced tree that strictly maintains balance using rotations. While other balanced tree implementations may have more relaxed balance conditions, AVL trees guarantee a balanced structure with logarithmic time complexity for all operations.