Notes on protected nodes in digital search trees
From MaRDI portal
Abstract: Recently, 2-protected nodes were studied in the context of ordered trees and -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 -analysis.
Recommendations
Cites work
- scientific article; zbMATH DE number 4106282 (Why is no real title available?)
- scientific article; zbMATH DE number 1222942 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- Asymptotic variance of random symmetric digital search trees
- Asymptotics of the moments of extreme-value related distribution functions
- Digital Search Trees Revisited
- External Internal Nodes in Digital Search Trees via Mellin Transforms
- Mellin transforms and asymptotics: Finite differences and Rice's integrals
- Protected points in \(k\)-ary trees
- Protected points in ordered trees
Cited in
(17)- On a random search tree: asymptotic enumeration of vertices by distance from leaves
- \(k\)-protected vertices in unlabeled rooted plane trees
- On the peel number and the leaf-height of Galton–Watson trees
- \(k\)-protected vertices in binary search trees
- Protected cells in compositions
- Protected Branches in Ordered Trees
- Degree profile of \(m\)-ary search trees: a vehicle for data structure compression
- Asymptotic expectation of protected node profile in random digital search trees
- Asymptotic distribution of two-protected nodes in random binary search trees
- Protected vertices in Motzkin trees
- Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
- Asymptotic distribution of two-protected nodes in ternary search trees
- Protected points in \(k\)-ary trees
- The distribution of the maximum protection number in simply generated trees
- Protection number in plane trees
- Limiting probabilities for vertices of a given rank in 1-2 trees
- On 2-protected nodes in random digital 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)
