AVL Tree Rotations

An AVL tree rebalances after every insert by checking the balance factor (left height − right height) at each ancestor. A magnitude over 1 triggers one of four rotation cases — LL, RR, LR, RL — restoring O(log n) height.

Category: Trees
Time complexity: O(log n)
Space complexity: O(1) per rotation

Pseudocode

insert as in a normal BST
walking back up, recompute height
if |balance| > 1: identify LL/RR/LR/RL
rotate to restore balance

Reference implementation

def insert(n, v):
    # normal BST insert, then:
    balance = height(n.l) - height(n.r)
    if balance &gt; 1 and v &lt; n.l.v: return rotate_right(n)   # LL
    if balance &lt; -1 and v &gt; n.r.v: return rotate_left(n)   # RR
    # LR / RL: rotate the child first, then the node

Open the interactive AVL Tree Rotations visualisation →