Premium
Data structures with dynamical random transitions
Author(s) -
Dombry C.,
GuillotinPlantard N.,
Pinçon B.,
Schott R.
Publication year - 2006
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.20091
Subject(s) - struct , focus (optics) , computer science , probabilistic logic , queue , random walk , set (abstract data type) , data structure , random variable , algorithm , priority queue , theoretical computer science , mathematics , statistics , artificial intelligence , programming language , physics , optics
We present a ( non‐standard ) probabilistic analysis of dynamic data structures whose sizes are considered dynamic random walks. The basic operations (insertion, deletion, positive and negative queries, batched insertion, lazy deletion, etc.) are time‐dependent random variables. This model is a (small) step toward the analysis of these structures when the distribution of the set of histories is not uniform . As an illustration, we focus on list structures (linear lists, priority queues, and dictionaries) but the technique is applicable as well to more advanced data structures. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006