Skip to content Skip to navigation

Radix sort and PATRICIA bridges

Saturday, February 1, 2020 - 2:55pm
"Radix sort and PATRICIA bridges"

Given a finite collection of pairwise distinct infinite binary words, there is a minimal length finite prefix for each word such that the resulting collection of finite prefixes is also pairwise distinct. The set of initial segments of these finite prefixes may be identified with the vertices of a finite rooted tree in which each interior vertex has a left child, a right child or both, and the finite prefixes themselves correspond to the leaves of the tree. A depth first search of this so-called radix sort tree produces an ordering of the leaves that agrees with the lexicographic ordering of the corresponding infinite binary words. The radix sort tree stores information that is redundant for the purpose of sorting the input infinite binary words into lexicographic order. Indeed, if one deletes the out-degree one vertices in the radix sort tree and “closes up the gaps”, then the resulting PATRICIA tree maintains all the information that is necessary for sorting. We investigate the infinite bridges corresponding to the radix sort and PATRICIA chains; that is, the tree-valued Markov chains built by successively feeding the radix sort and PATRICIA algorithms the elements of an infinite i.i.d. sequence of infinite binary words. In particular, we show that the infinite PATRICIA bridges coincide with those associated with a chain introduced by Rémy for successively generating uniform random binary trees with larger and larger numbers of leaves, and we obtain a concrete representation of all such bridges in terms of sampling from an underlying real tree.