AVL Trees: Self Balancing Binary Search Trees!

What is an AVL Tree?

An AVL tree is a type of self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. The name AVL is derived from the initials of its inventors Georgy Adelson-Velsky and Evgenii Landis, who created the data structure in 1962.

Properties of AVL Trees

• Every node maintains a balance factor, which is the difference in height between the left and right subtrees. If the balance factor is greater than 1, the tree requires rebalancing.
• AVL trees are balanced to ensure O(log N) time complexity for search, insertion, and deletion operations.
• Rebalancing operations like rotations (single and double) are used to maintain balance.

Insertion in AVL Trees

Insertion in an AVL tree follows the same rules as in a regular binary search tree. However, it has the added step of rebalancing the tree, using rotations if necessary to maintain the AVL property. Here are some of the types of rotations that you might need to encounter for proper rebalancing:

• Left Rotation
• Right Rotation
• Left-Right Rotation
• Right-Left Rotation

Here's an example of an AVL Tree!

If you would like to learn more, visit this page: Wikipedia.