×

zbMATH — the first resource for mathematics

On The variance of the extremal path length in a symmetric digital trie. (English) Zbl 0685.68059
A trie is a digital search tree whose edges are labelled by elements from an alphabet, the leaves contain keys such that the access path from the root to a key is a prefix of that key. The variance of the external path length (sum of all access paths) for binary tries is studied. First, the authors derive the exact formula on the variance for an asymmetric trie, that is, when the probabilities of appearance of 0 and 1 in a key are not the same. Next, they prove that the variance for the binary symmetric tries is asymptotically equal to \(4.35n+n\cdot f(\log_ 2n)\) where f(x) is a periodic function with a very small amplitude and mean zero.
Reviewer: C.Radu

MSC:
68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.; Hopcroft, J.; Ullman, J., Data structures and algorithms, (1983), Addison-Wesley Reading, MA
[2] Apostol, T., Modular functions and Dirichlet series in number theory, (1976), Springer New York · Zbl 0332.10017
[3] Flajolet, Ph.; Sedgewick, R., Digital search trees revisited, SIAM J. comput., 15, 748-767, (1986) · Zbl 0611.68041
[4] Gonnet, G., ()
[5] Henrici, P., Applied and computational complex analysis, (1977), Wiley New York · Zbl 0377.30002
[6] Kirschenhofer, P.; Prodinger, H., Some further results on digital search trees, (), 177-185, Lectures Notes in Computer Science
[7] Kirschenhofer, P.; Prodinger, H.; Schoissengeier, J., Zur auswertung gewisser reihen mit hilfe modularer functionen, (), 108-110, Lecture Notes in Mathematics
[8] Kirschenhofer, P.; Prodinger, H., On some applications of formulae of Ramanujan in the analysis of algorithms, (1988), Preprint · Zbl 0765.68051
[9] Knuth, D., The art of computer programming 3: sorting and searching, (1973), Addison-Wesley Reading, MA · Zbl 0302.68010
[10] Mathys, P.; Flajolet, P., Q-ary collision resolution algorithms in random-access system with free and blocked channel access, IEEE trans. inform. theory, 31, 2, 217-243, (1985) · Zbl 0566.94001
[11] Paige, R.; Tarjan, R., Three efficient algorithms based on partition refinement, (1986), Preprint
[12] Riordan, J., Combinatorial identities, (1968), Wiley New York · Zbl 0194.00502
[13] Szpankowski, W., Two problems on the average complexity of digital trees, Proceedings performances-87, 189-208, (1987), Brussel
[14] Szpankowski, W., Some results on V-ary asymmetric tries, J. algorithms, 9, 224-244, (1988) · Zbl 0637.68072
[15] Szpankowski, W., The evaluation of an alternative sum with applications to the analysis of some data structures, Inform. process. lett., 28, 13-19, (1988) · Zbl 0657.68071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.