Node profiles of symmetric digital search trees: Concentration properties

DOI10.1002/rsa.20979zbMath1522.68170arXiv1711.06941OpenAlexW3107994392MaRDI QIDQ6049998

Ralph Neininger, Hsien-Kuei Hwang, Michael Fuchs, Michael Drmota

Publication date: 11 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.06941

zbMATH Keywords

Laplace transformMellin transformdigital search treePoissonizationasymptotic transferlevel profiletwo-point concentrationdouble-indexed recurrence

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Searching and sorting (68P10) Data structures (68P05)

Related Items (2)

Normal Limit Law for Protected Node Profile of Random Recursive Trees ⋮ Continuous-time digital search tree and a border aggregation model

Cites Work

• The expected profile of digital search trees
• Mellin transforms and asymptotics: Harmonic sums
• On the performance evaluation of extendible hashing and trie searching
• A diffusion limit for a class of randomly-growing binary trees
• Analytical depoissonization and its applications
• Maxima of Poisson-like variables and related triangular arrays
• A general limit theorem for recursive algorithms and combinatorial structures
• Profiles of PATRICIA tries
• Universal asymptotics for random tries and PATRICIA trees
• Special issue: Average-case analysis of algorithms
• An analytic approach to the asymptotic variance of trie statistics and related structures
• A note on growing binary trees
• Random Trees
• Asymptotic variance of random symmetric digital search trees
• Profiles of Tries
• Exact and asymptotic distributions in digital and binary search trees
• Universal Limit Laws for Depths in Random Trees
• Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme
• Limit laws for the height in PATRICIA tries
• Expected External Profile of PATRICIA Tries
• Asymmetric Rényi Problem
• Extreme value theory for a class of discrete distributions with applications to some stochastic processes
• File structures using hashing functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Node profiles of symmetric digital search trees: Concentration properties