We study a class of tries that adaptively choose degrees of their
nodes by processing multiple digits of input keys at a time. We
demonstrate that the size (total number of pointers) of such tries
depends on the strategy used for selecting the degrees of their nodes,
and propose a local space-efficiency criterion that can be used to
guide a dynamic construction of tries minimizing their size. We study
the expected behavior of this criterion (as a function of the number
of keys and the number of digits
processed by a node) in a
binary memoryless model, and demonstrate that it attains a maximum
when
, where
is a constant depending on the parameters
(
and
) of the source. Surprisingly enough, we also find that
under asymmetric memoryless sources, the expected number of empty
pointers in nodes with such a relation between
and
is about
50