Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural assumptions...
Digital trees or tries are a general purpose flexible data structure
that implements dictionaries built on words. The present paper is focussed
on the average-case analysis of
an important parameter of this
tree-structure, , the stack-size.
The stack-size of a tree is the memory needed
by a storage-optimal preorder traversal. The analysis is carried out
under a general model in which words are produced by
a source (in the information-theoretic sense)
that emits symbols.
Under some natural...
In this paper we investigate the average Horton-Strahler number of all possible tree-structures of binary tries. For
that purpose we consider a generalization of extended binary trees where leaves are distinguished in order to represent
the location of keys within a corresponding trie. Assuming a uniform distribution for those trees we prove that the
expected Horton-Strahler number of a tree with internal nodes and leaves that correspond to a key is
asymptotically given by provided that and...
Download Results (CSV)