wavelet-tree · shipping · also Wavelet trees

Wavelet tree

A wavelet tree represents a symbol sequence through recursive alphabet partitions and routing bitmaps that support access, rank and select queries.

Structure: In the basic ordered binary form, each internal node splits its symbol range and stores one routing bit per symbol in its subsequence. Stable partitioning preserves relative order within each child; subsequences need not be stored explicitly. [1]

Queries: Access recovers a symbol, rank counts its occurrences in a prefix, and select locates an occurrence. Balanced trees take O(log sigma) steps for alphabet [0, sigma), assuming constant-time bitmap rank/select. Prefix endpoints and occurrence numbering must be stated. [2]

Space: For n symbols, the basic routing bitmaps use at most n * ceil(log2(sigma)) bits. Rank/select support and tree representation add space. Compressed bitmaps or Huffman shaping change this accounting; a tree alone does not ensure compression. [1]

Order: Ordered symbol partitions support range counting and quantiles. Ordinary Huffman shaping need not preserve numeric order, so those operations do not transfer unchanged. This is an exact sequence index, not a signal-processing wavelet transform. [1] [3]

Relations

related
RRR bitvector, Wavelet matrix, Rank/select, Huffman coding

Citations

  1. Gonzalo Navarro: Wavelet Trees for All, Journal of Discrete Algorithms 25 (2014), sections 1-4 and 6.2 (accessed 2026-11-17)
  2. Francisco Claude and Gonzalo Navarro: The Wavelet Matrix, SPIRE 2012, sections 1-2 (accessed 2026-11-17)
  3. Claude, Navarro and Ordonez: Efficient Compressed Wavelet Trees over Large Alphabets, arXiv:1405.1220, sections 2 and 6 (accessed 2026-11-17)
Sources & caveats
  • Primary-source synthesis of sequence indexing and space bounds, not a benchmark replication or a universal speed comparison.

JSON: /data/terms/wavelet-tree.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Wavelet tree. Hesela. 2026-11-17. https://hesela.dev/terms/wavelet-tree/