Analysis of a Class of Tries with Adaptive Multi-Digit Branching

Abstract. We study a class of adaptive multi-digit tries, in which the numbers of digits rn processed by nodes with n incoming strings are such that, in memoryless model (with n→∞): rn → logn η (pr.) where η is an algorithm-specific constant. Examples of known data struc-tures from this class include LC-tries (Andersson and Nilsson, 1993), ”relaxed ” LC-tries (Nilsson and Tikkanen, 1998), tries with logarithmic selection of degrees of nodes, etc. We show, that the average depth Dn of such tries in asymmetric memoryless model has the following asymptotic behavior (with n→∞): Dn = log log n − log (1 − h/η) (1 + o (1)) where n is the number of strings inserted in the trie, and h is the en-tropy of the source. We use this formula to compare performance of known adaptive trie structures, and to predict properties of other possi-ble implementations of tries in this class.