Neo & Byte · #4 · AVL vs red-black trees

The Perfectionist

Four-panel comic. Keys 10, 20 and 30 make a plain search tree lean. The AVL tree measures a height difference of two and rotates, and measures again after every key, while the red-black tree relaxes in a deck chair: never more than twice as tall as it needs to be.

Transcript

  1. Panel 1. Byte: “Why is it leaning?”
  2. Panel 2. AVL: “Height difference: 2. Unacceptable.”
  3. Panel 3. Byte: “You check after every key?” AVL: “Every single one.”
  4. Panel 4. Red-black: “Relax. I'm never more than twice as tall as I need to be.”

Actually…

An AVL tree keeps the heights of every node's two subtrees within one of each other, so it stays lower and lookups are slightly faster. A red-black tree only promises that no path from the root is more than twice as long as another, so it can be taller, but it repairs itself more cheaply: a deletion needs at most three rotations, where an AVL deletion can need one at every level. Both search, insert and delete in O(log n).

See it step by step

In the VisiGrab app, build AVL and red-black trees yourself and watch every insert and delete, rotation by rotation. App Store · Google Play