TREE SIZE IN A DYNAMIC LIST STRUCTURE

This article considers a classical binary tree implementation of a set of keys: the trie. The trie size properties in a static environment a re well known: The size is asymptotically Gaussian when the number of keys is large. In this article we analyze the trie in a dynamic enviro nment, where the trie is allowed to grow and shrink in a probabilistic way. It appears that the trie size can be described by a stochastic p rocess which is asymptotically Gaussian non-Markovian. This also allow s the complete asymptotic analysis of the trie size maximum and the tr ie size integrated cost. (C) 1994 John Wiley & Sons, Inc.