Describe an AVL tree

An AVL tree (Adelson-Velsky and Landis, 1962) is a self-balancing binary search tree in which, for every node, the heights of the left and right subtrees differ by at most one.

• Balance factor = height(left) − height(right) ∈ {−1, 0, +1}.
• It is a BST, so left keys < node < right keys, and in-order traversal gives sorted order.
• After an insertion or deletion that makes a balance factor ±2, the tree is restored by single (LL, RR) or double (LR, RL) rotations.
• Height of an AVL tree with n nodes is always O(log n) (at most about 1.44·log₂ n), so search, insertion and deletion take O(log n) even in the worst case.

      30   (bf +1)
     /  \
   20    40      A valid AVL tree
  /
10

Here node 20 has bf = +1 (left height 1, right height 0), node 30 has bf = +1 (left height 2, right height 1), and the leaves 10 and 40 have bf = 0, so the tree is balanced.