Notes on protected nodes in digital search trees

DOI10.1016/J.AML.2011.11.017zbMATH Open1244.05055arXiv1111.1471OpenAlexW2157896076MaRDI QIDQ419140FDOQ419140

Authors: Rosena R. X. Du, Helmut Prodinger 

Publication date: 18 May 2012

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

Abstract: Recently, 2-protected nodes were studied in the context of ordered trees and $k$-trees. These nodes have a distance of at least 2 to each leaf. Here, we study digital search trees, which are binary trees, but with a different probability distribution underlying. Our result says, that emph{grosso modo} some 31% of the nodes are 2-protected. Methods include exponential generating functions, contour integration, and some elements from $q$-analysis.

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

Recommendations

• On 2-protected nodes in random digital trees
• Protected nodes and fringe subtrees in some random trees
• Protected points in \(k\)-ary trees
• Asymptotic distribution of two-protected nodes in ternary search trees
• Protected node profile of tries

zbMATH Keywords

digital search trees

Mathematics Subject Classification ID

Trees (05C05)

Cites Work

• Title not available (Why is that?)
• Asymptotics of the moments of extreme-value related distribution functions
• Title not available (Why is that?)
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Asymptotic variance of random symmetric digital search trees
• Digital Search Trees Revisited
• Protected points in ordered trees
• Protected points in \(k\)-ary trees
• Title not available (Why is that?)
• External Internal Nodes in Digital Search Trees via Mellin Transforms

Cited In (17)

• \(k\)-protected vertices in binary search trees
• Protected points in \(k\)-ary trees
• Protected cells in compositions
• Asymptotic distribution of two-protected nodes in random binary search trees
• Degree profile of \(m\)-ary search trees: a vehicle for data structure compression
• Protected vertices in Motzkin trees
• On 2-protected nodes in random digital trees
• \(k\)-protected vertices in unlabeled rooted plane trees
• On the peel number and the leaf-height of Galton–Watson trees
• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
• On a random search tree: asymptotic enumeration of vertices by distance from leaves
• Asymptotic distribution of two-protected nodes in ternary search trees
• Limiting probabilities for vertices of a given rank in 1-2 trees
• The distribution of the maximum protection number in simply generated trees
• Protected Branches in Ordered Trees
• Asymptotic expectation of protected node profile in random digital search trees
• Protection number in plane trees

This page was built for publication: Notes on protected nodes in digital search trees

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