pith. sign in

arxiv: 1111.1471 · v1 · pith:U67XDP2Mnew · submitted 2011-11-07 · 🧮 math.CO · math.PR

On protected nodes in Digital Search Trees

classification 🧮 math.CO math.PR
keywords treesnodesprotecteddigitalsearchsomeanalysisbinary
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.