<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>Protected nodes are neither leaves nor parents of any leaves in a rooted tree. We study here protected node profile, namely, the number of protected nodes with the same distance from the root in digital search trees, some fundamental data structures to store 0 - 1 strings. When each string is a sequence of independent and identically distributed Bernoulli(<italic>p</italic>) random variables with 0 &lt; <italic>p</italic> &lt; (<inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_jamsi-2022-0004_eq_001.png"></inline-graphic>
<math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>p</mi><mo>≠</mo><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></math>
<tex-math>p \ne {1 \over 2}</tex-math>
</alternatives>
</inline-formula>), Drmota and Szpankowski (2011) investigated the expectation of internal profile by the analytic methods. Here, we generalize the main parts of their approach in order to obtain the asymptotic expectations of protected node profile and non-protected node profile in digital search trees.</p>
</abstract>

Protected nodes are neither leaves nor parents of any leaves in a rooted tree. We study here protected node profile, namely, the number of protected nodes with the same distance from the root in digital search trees, some fundamental data structures to store 0 - 1 strings. When each string is a sequence of independent and identically distributed Bernoulli(p) random variables with 0 < p < (


p≠12
p \ne {1 \over 2}

), Drmota and Szpankowski (2011) investigated the expectation of internal profile by the analytic methods. Here, we generalize the main parts of their approach in order to obtain the asymptotic expectations of protected node profile and non-protected node profile in digital search trees.

Asymptotic expectation of protected node profile in random digital search trees

Journal of Applied Mathematics, Statistics and Informatics

This work is licensed under the Creative Commons Attribution 4.0 International License.

{"article-title":"Asymptotic expectation of protected node profile in random digital search trees"}

Protected nodes are neither leaves nor parents of any leaves in a rooted tree. We study here protected node profile, namely, the number of protected nodes with...

Asymptotic expectation of protected node profile in random digital search trees

Publié en ligne: 04 juil. 2022

Pages: 43 - 57

DOI: https://doi.org/10.2478/jamsi-2022-0004

Mots clés
Digital search trees, profile, protected node, singularity analysis, saddle point method, probability generating function

© 2022 M. Javanian et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Asymptotic expectation of protected node profile in random digital search trees

Publié en ligne: 04 juil. 2022

Pages: 43 - 57

DOI: https://doi.org/10.2478/jamsi-2022-0004

Mots clésDigital search trees, profile, protected node, singularity analysis, saddle point method, probability generating function

© 2022 M. Javanian et al., published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Mots clés
Digital search trees, profile, protected node, singularity analysis, saddle point method, probability generating function