<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

Pubblicato online: 04 lug 2022

Pagine: 43 - 57

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

Parole chiave
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

Pubblicato online: 04 lug 2022

Pagine: 43 - 57

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

Parole chiaveDigital 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.

Parole chiave
Digital search trees, profile, protected node, singularity analysis, saddle point method, probability generating function