Premium
Trie size in a dynamic list structure
Author(s) -
Louchard G.
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050505
Subject(s) - trie , probabilistic logic , computer science , tree (set theory) , gaussian , set (abstract data type) , mathematics , combinatorics , data structure , statistics , physics , quantum mechanics , programming language
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.