AVL Tree

What is an AVL Tree?

An AVL tree is a self-balancing Binary Search Tree (BST). This means it maintains a specific structure to ensure efficient search, insertion, and deletion operations. The key property of an AVL tree is:

• Balance Factor: For every node in the tree, the difference in height between its left and right subtrees is at most 1. This difference is called the "balance factor."

Why AVL Trees?

• Regular BSTs can become skewed (like a linked list) in worst-case scenarios, leading to O(n) time complexity for operations.

• AVL trees guarantee a height of O(log n), ensuring that search, insertion, and deletion remain efficient.

Balance Factor Calculation

• Balance Factor = Height(left subtree) - Height(right subtree)

• An AVL tree is balanced if the balance factor of every node is -1, 0, or 1.

Rotations

To maintain the balance property, AVL trees use rotations:

• Left Rotation: Used when the right subtree is too heavy.

• Right Rotation: Used when the left subtree is too heavy.

• Left-Right Rotation: A combination of left and right rotations.

• Right-Left Rotation: A combination of right and left rotations.

Summary

• AVL trees are self-balancing BSTs.

• They maintain balance using balance factors and rotations.

• They ensure efficient operations with O(log n) time complexity.

References:

https://www.geeksforgeeks.org/