Balanced BSTs: AVL Trees
Explore how AVL trees function as self-balancing binary search trees in JavaScript by automatically maintaining balance after insertions and deletions. Understand balance factors, various rotation techniques to restore balance, and how these ensure logarithmic performance for search, insertion, and deletion operations.
We'll cover the following...
An AVL tree is a special type of self-balancing binary search tree (BST). It automatically maintains balance after every insertion and deletion.
The main idea behind AVL trees is simple:
The height of the left and right subtrees of any node should differ by at most 1.
If this condition is violated, the tree performs rotations to restore balance.
AVL trees were the first self-balancing BSTs, introduced by Adelson-Velsky and Landis (hence the name AVL).
Why AVL trees are needed
In a normal BST, performance depends on the shape of the tree.
If the tree is balanced, operations are fast →
If the tree becomes skewed, operations become slow →
Example of a skewed BST:
This behaves like a linked list, making searching inefficient.
AVL trees solve this problem by automatically maintaining balance, ensuring that operations remain fast.
Balance factor
The key concept in AVL trees is the balance factor.
The balance factor is defined as:
Balance Factor = Height(left subtree) - Height(right subtree)
For an AVL tree, the balance factor of every node must be:
, , or
If it becomes less than
Example
Balance factors:
Node
...