Stephan Wagner - On unary nodes in tries

dmtcs:2776 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2776
On unary nodes in triesArticle

Authors: Stephan Wagner 1

  • 1 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]

The difference between ordinary tries and Patricia tries lies in the fact that all unary nodes are removed in the latter. Their average number is thus easily determined from earlier results on the size of tries/Patricia tries. In a well-known contention resolution algorithm, whose probabilistic model is essentially equivalent to tries, unary nodes correspond to repetitions, i.e., steps in the algorithm that do not resolve anything at all. In this paper, we take an individual's view on such repetitions: we consider the distribution of the number of repetitions a certain contender encounters in the course of the algorithm―-which is equivalent to the number of unary nodes on the path from the root to a random string in a trie. We encounter an example of a sequence of distributions that does not actually converge to a limit distribution, but rather oscillates around a (discrete) limit distribution.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: tries,Patricia tries,contention trees,unary nodes,limit distribution,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Consultation statistics

This page has been seen 202 times.
This article's PDF has been downloaded 181 times.