On Time-Space Efficiency of Digital Trees with Adaptive Multidigit Branching

Abstract

Parameters of time-space efficiency and sparseness of nodes in trees with adaptive multidigit branching are studied. Both precise and asymptotic expressions, describing average behavior of these parameters in a memoryless model, are obtained. These expressions are used to establish a relation between parameters. As a result, conditions of time-space optimality of trees constructed with the use of Nilsson and Tikkanen algorithm are obtained. [PUBLICATION ABSTRACT]