On The variance of the extremal path length in a symmetric digital trie
type: Item
instance of: scholarly article
title: On The variance of the extremal path length in a symmetric digital trie
zbMATH Open document ID: 0685.68059
DOI: 10.1016/0166-218X(89)90050-4
author: Peter Kirschenhofer
author: Wojciech Szpankowski
author: Helmut Prodinger
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
reviewed by: C.Radu
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4123313
zbMATH Keywords: binary tree
zbMATH Keywords: search tree
MaRDI profile type: Publication
cites work: Q3948568
cites work: Q4097001
cites work: Digital Search Trees Revisited
cites work: Q3816955
cites work: Q4156973
cites work: Q3730026
cites work: Q3774964
cites work: On some applications of formulae of Ramanujan in the analysis of algorithms
cites work: Q4057549
cites work: &lt;tex&gt;Q&lt;/tex&gt;-ary collision resolution algorithms in random-access systems with free or blocked channel access
cites work: Q5589310
cites work: Some results on V-ary asymmetric tries
cites work: The evaluation of an alternative sum with applications to the analysis of some data structures
description: scientific article; zbMATH DE number 4123313