Algorithm dossier

  • Category: Tree op
  • Worst-case complexity: O(1)
  • Approach: Iterative
  • Data structure: Tree
  • First formalised: 1960s

Why this snippet is AVL Rotation

Why AVL rotation. Constant-time pointer surgery to restore a height-balance invariant. This is a *left rotation*: the right child b becomes the new root, the old root a becomes b's left child, and b's old left subtree becomes a's new right subtree. Heights are recomputed from the new children. Why bother. Without rotations, an unlucky insertion sequence degenerates a BST into a linked list — O(n) operations instead of O(log n).

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.