AVL Tree : Rotation, and Balance Factor Explained

Mohamed Benlmaoujoud — Sat, 18 Dec 2021 20:31:56 +0000

What is an AVL Tree?

An AVL tree is a type of binary search tree. Named after it's inventors Adelson, Velskii, and Landis, AVL trees have the property of dynamic self-balancing in addition to all the other properties exhibited by binary search trees.

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, one, or two child nodes
Each child node has zero, one, or two child nodes
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

So The difference between the depth of right and left sub- trees cannot be more than one |depth(right) - dépt(left)|>1. This difference is called the balance factor.

So how we can balance our BST , well 💁 we can use some ruls (rotations) to balance it .

1. Left Rotation (LL Rotation)

In left rotations, every node moves one position to left from the current position.

2. Right Rotation (RR Rotation

In right rotations, every node moves one position to right from the current position.

3. Left-Right && Right-Left Rotation (LR && RL Rotation

LR or RL rotations are a combination of a single left
resp (right) rotation followed by a single right resp(left) rotation.

Application of AVL Trees
AVL trees are beneficial in cases like a database where insertions and deletions are not that frequent, but you frequently check for entries.

DEV Community: Mohamed Benlmaoujoud

AVL Tree : Rotation, and Balance Factor Explained

What is an AVL Tree?