On weighted depths in random binary search trees

DOI10.1007/s10959-017-0773-1zbMath1428.60041arXiv1707.00165OpenAlexW2963617856WikidataQ59614041 ScholiaQ59614041MaRDI QIDQ1800490

Rafik Aguech, Anis Amri, Henning Sulzbach

Publication date: 24 October 2018

Published in: Journal of Theoretical Probability (Search for Journal in Brave)

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

zbMATH Keywords

data structurescentral limit theoremscontraction methodanalysis of algorithmbinary search treesrandom probability measures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Central limit and other weak theorems (60F05) Data structures (68P05)

Uses Software

• Quicksort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Large deviations for the weighted height of an extended class of trees
• On the silhouette of binary search trees
• Applications of the theory of records in the study of random trees
• Integers without large prime factors
• Mixed Poisson approximation of node depth distributions in random binary search trees
• Distribution of distances in random binary search trees.
• Spanning tree size in random binary search trees.
• On edge-weighted recursive trees and inversions in random permutations
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• Quickselect and the Dickman Function
• Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation
• On Random Binary Trees
• Limit laws for local counters in random binary search trees
• EXTREMAL WEIGHTED PATH LENGTHS IN RANDOM BINARY SEARCH TREES
• A limiting distribution for quicksort
• A note on the height of binary search trees
• Distances and Finger Search in Random Binary Search Trees
• Asymptotic distribution theory for Hoare's selection algorithm
• ON WEIGHTED PATH LENGTHS AND DISTANCES IN INCREASING TREES
• A limit theorem for “quicksort”
• Quicksort

This page was built for publication: On weighted depths in random binary search trees