AVL Trees

What is it?

An AVL tree is type of Binary Search Tree where the heights of the two child subtrees of any node differ by at most one.

AVL tree steps

  1. Every node has a balancing factor of -1,0, or 1.
  2. After every insertion or deletion, tree rotations happen to make the tree balanced again.
  3. Search, insert, and delete all run in O(log n) time.

Sample Diagram

AVL tree rotation example

Learn more

AVL trees information