Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T06:12:46.622Z Has data issue: false hasContentIssue false

An Analysis of the Height of Tries with Random Weights on the Edges

Published online by Cambridge University Press:  01 March 2008

N. BROUTIN
Affiliation:
School of Computer Science, McGill University, Montreal H3A2K6Canada (e-mail: nicolas.broutin@m4x.org, luc@cs.mcgill.ca)
L. DEVROYE
Affiliation:
School of Computer Science, McGill University, Montreal H3A2K6Canada (e-mail: nicolas.broutin@m4x.org, luc@cs.mcgill.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We analyse the weighted height of random tries built from independent strings of i.i.d. symbols on the finite alphabet {1, . . .d}. The edges receive random weights whose distribution depends upon the number of strings that visit that edge. Such a model covers the hybrid tries of de la Briandais and the TST of Bentley and Sedgewick, where the search time for a string can be decomposed as a sum of processing times for each symbol in the string. Our weighted trie model also permits one to study maximal path imbalance. In all cases, the weighted height is shown to be asymptotic to c log n in probability, where c is determined by the behaviour of the core of the trie (the part where all nodes have a full set of children) and the fringe of the trie (the part of the trie where nodes have only one child and form spaghetti-like trees). It can be found by maximizing a function that is related to the Cramér exponent of the distribution of the edge weights.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2007