Wavelet Tree

A sequence over an 8-symbol alphabet, with access, rank and select traced step by step.

colour = symbol value (a → h) current position bits being counted path taken

Pick an operation and press Run. The active position is followed down (or up) the tree, one bitvector at a time.

Result —

Operation

Symbol c

Position i

—

Length 12

Delay 650ms

Each internal node stores a bitvector: 0 sends a symbol to the left child, 1 to the right, splitting the alphabet in half each level until every leaf holds one symbol. access walks down reading bits; rank walks down counting them; select walks back up.