\(k\)-protected vertices in binary search trees

DOI10.1016/j.aam.2013.09.003zbMath1281.05004arXiv1304.6105OpenAlexW2052080402MaRDI QIDQ395245

Miklós Bóna

Publication date: 29 January 2014

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutationsdistanceenumerationtrees

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Permutations, words, matrices (05A05) Enumeration in graph theory (05C30) Distance in graphs (05C12) Asymptotic enumeration (05A16) Data structures (68P05)

Related Items

Protected Branches in Ordered Trees ⋮ Protection number in plane trees ⋮ Weakly protected nodes in random binary search trees ⋮ Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees ⋮ Central limit theorems for additive functionals and fringe trees in tries ⋮ Stochastic approximation on noncompact measure spaces and application to measure-valued Pólya processes ⋮ Random plane increasing trees: Asymptotic enumeration of vertices by distance from leaves ⋮ \(k\)-protected vertices in unlabeled rooted plane trees ⋮ The lemniscate tree of a random polynomial ⋮ On 2-protected nodes in random digital trees ⋮ On a random search tree: asymptotic enumeration of vertices by distance from leaves ⋮ Limiting probabilities for vertices of a given rank in 1-2 trees

Cites Work

• Unnamed Item
• Unnamed Item
• Notes on protected nodes in digital search trees
• Asymptotic distribution of two-protected nodes in random binary search trees
• Protected nodes and fringe subtrees in some random trees
• Protected points in ordered trees
• Limit laws for local counters in random binary search trees
• The Expected Distribution of Degrees in Random Binary Search Trees