E = I + T: The internal extent formula for compacted tries
classification
💻 cs.DS
cs.DM
keywords
compactedextentexternalformulainternallengthnumberpath
read the original abstract
It is well known that in a binary tree the external path length minus the internal path length is exactly 2n-2, where n is the number of external nodes. We show that a generalization of the formula holds for compacted tries, replacing the role of paths with the notion of extent, and the value 2n-2 with the trie measure, an estimation of the number of bits that are necessary to describe the trie.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.