One-sided Variations on Tries: Path Imbalance, Climbing, and Key Sampling

One-sided Variations on Tries: Path Imbalance, Climbing, and Key Sampling

One-sided variations on path length in a trie (a sort of digital trees) are investigated: They include imbalance factors, climbing under different strategies, and key sampling. For the imbalance factor accurate asymptotics for the mean are derived for a randomly chosen key in the trie via poissoniza...

Full description

Bibliographic Details
Main Authors: Costas A. Christophi, Hosam M. Mahmoud
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2007-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
singularity analysis.
depoissonization
random trees
digital trees
recurrence
mellin transform
poissonization
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
[info.info-cg] computer science [cs]/computational geometry [cs.cg]
Online Access:https://dmtcs.episciences.org/3522/pdf

Internet

https://dmtcs.episciences.org/3522/pdf

Similar Items