AVL Rotation

ComparingInsertedUnbalancedRotating

binary search tree

left is smaller, right is larger

pseudocode

balance(node) = height(node.right) - height(node.left)
if |balance| > 1: node is unbalanced
  (LL/RR: single rotation, LR/RL: rotate child first)
  if the child leans the opposite way: rotate the child first
rotateLeft/rotateRight(node): pivot takes node's place
reattach pivot where node used to be

Frame 1 / 4

Starting tree

3 values inserted

Speed4

Tree values

3–9 unique integers, 1–99 each — inserted in order to build the starting tree.