The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
The Height and Size of Random Hash Trees and Random Pebbled Hash Trees
Luc Devroye,
Pages. 1215-1224
Abstract
Contents 1. Introduction
2. Survey of known results on N-trees and random hash trees
3. The height of the random hash tree
4. The height of the random pebbled hash tree
5. Proof of theorem 4
6. The size of random hash trees
7. BBST: Bucketing followed by binary search trees
8. Extension: $m$ pebbles
9. Dynamic data structures
Key words data structures, probabilistic analysis, hashing with chaining, hash tables, N-trees, random hash trees, expected complexity
Mathmatical Subject Classification 68Q25, 68P10