#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/building-the-wavelet-tree

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/building-the-wavelet-tree

Repovive

Building the Wavelet Tree - Wavelet Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Building the Wavelet Tree

Recursive construction

To build a wavelet tree:

function buildWavelet(arr, lo, hi)
 if lo = hi then
 return leaf node

 mid := (lo + hi) / 2
 node := new WaveletNode(lo, hi)

 // Build bitvector: 0 if value <= mid, 1 if value > mid
 leftArr := []
 rightArr := []
 for val in arr
 if val <= mid then
 node.bitvector.append(0)
 leftArr.append(val)
 else
 node.bitvector.append(1)
 rightArr.append(val)

 node.left := buildWavelet(leftArr, lo, mid)
 node.right := buildWavelet(rightArr, mid + 1, hi)
 return node

Time: $O(n \log \sigma)$ . Space: $O(n \log \sigma)$ for all bitvectors.