Trie size in a dynamic list structure
Guy Louchard · Random Structures and Algorithms · 1994
Abstract This article considers a classical binary tree implementation of a set of keys: the trie. The trie size properties in a static environment are well known: The size is asymptotically Gaussian when the number of keys is large. In this article we analyze the trie in a dynamic environment, 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 process which is asymptotically Gaussian non‐Markovian. This also allows the complete asymptotic analysis of the trie size maximum and the trie size integrated cost. © 1994 John Wiley & Sons, Inc.