AVL Tree

This page includes an overview of AVL tree.

Useful Features:

  1. AVL tree is a self-balancing binary search tree.
  2. Uses rotations to maintain balance.
  3. It keeps H (height) of tree with N nodes growing in O(log N)

Balance Factor in AVL tree:

The balance factor (bf) is computed as: bf = height(left subtree) - height(right subtree). A node is balanced if the absolute value of the bf is smaller than 2. The sign of bf indicates the direction of inbalance. A tree is balanced if every node is balanced.

Example of a balanced AVL tree

For more details, visit the AVL tree.