Enumeration of tree properties by naive methods

Source: https://www.maths.tcd.ie/report_series/abstracts/tcdm0107.html Parent: https://www.maths.tcd.ie/research/papers/

Enumeration of tree properties by naive methods

This paper studies the problem of how much space is saved, on average, when a TRIE is pruned back to a minimal discriminating prefix. Exact figures (on average, half the space is saved) are given for binary trees. All treens with n nodes and m leaves are assumed equally likely. The calculations are based on an unusual form of recurrence relation. This paper was originally published in Algorithms review 1:3,** September 1990, 119--124, a journal which lasted from 1990 to 1992.