On 2-protected nodes in random digital trees

DOI10.1016/J.TCS.2016.02.007MaRDI QIDQ5964078zbMATH OpenOpenAlexFDO

Authors M. Fuchs, Chang Koo Lee, G.-R. Yu

Publication date 26 February 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.02.007

zbMATH Keywords

Abel summabilityanalytic combinatoricsdata structuresdigital treeslimit theoremsmoments

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Notes on protected nodes in digital search trees
• Protected node profile of tries
• scientific article; zbMATH DE number 3961005
• The variance of the number of 2-protected nodes in a trie
• On the number of 2-protected nodes in tries and suffix trees

Cites work

• k-protected vertices in binary search trees
• A general central limit theorem for shape parameters of m-ary tries and PATRICIA tries
• A survey of multivariate aspects of the contraction method
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Asymptotic distribution of two-protected nodes in random binary search trees
• Asymptotic distribution of two-protected nodes in ternary search trees
• Asymptotic properties of protected nodes in random recursive trees
• Asymptotic variance of random symmetric digital search trees
• Digital trees and memoryless sources: from arithmetics to analysis
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1222942 (Why is no real title available?)
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Mellin transforms and asymptotics: Harmonic sums
• Notes on protected nodes in digital search trees
• On the number of 2-protected nodes in tries and suffix trees
• On the variance of a class of inductive valuations of data structures for digital search
• Protected nodes and fringe subtrees in some random trees
• Protected points in \(k\)-ary trees
• Protected points in ordered trees
• The variance of the number of 2-protected nodes in a trie
• Using Stein's method to show Poisson and normal limit laws for fringe subtrees

Cited in

(8)

• Asymptotic expectation of protected node profile in random digital search trees
• On the number of 2-protected nodes in tries and suffix trees
• Notes on protected nodes in digital search trees
• Protected node profile of tries
• Normal Limit Law for Protected Node Profile of Random Recursive Trees
• The variance of the number of 2-protected nodes in a trie
• On a random search tree: asymptotic enumeration of vertices by distance from leaves
• On the protected nodes in exponential recursive trees

This page was built for publication: On 2-protected nodes in random digital trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964078)