# The Moments of the Profile in Random Binary Digital Trees

Volume 6, Issue 3, pp 176-190 Publication Date: April 15, 2013
• 705 Views

### Authors

Ramin Kazemi - Department of Statistics, Imam Khomeini International University, Qazvin, Iran. Saeid Delavar - Department of Statistics, Imam Khomeini International University, Qazvin, Iran.

### Abstract

The purpose of this paper is to provide a precise analysis of the $t$-th moment of the profile in random binary digital trees. We assume that the $n$ input strings are independent and follow a (binary) Bernoulli model. In tries, the main difference with the previous analysis is that we have to deal with an inhomogeneous part in the proper functional equation satisfied by the $t$-th moment and in digital search trees with an inhomogeneous part in a proper functional-differential equation. We show that $t$-th moment of the profile ($t\geq 2$) is asymptotically of the same order as the expected value ($t=1$). These results are derived by methods of analytic combinatorics.

### Keywords

• Digital trees
• Tries
• Digital search trees
• Profile
• The $t$-th moment.

•  68P05
•  05C80

### References

• [1] R. Cguech, K. Lasmar, H. M. Mahmoud, Distribution of inter-node distances in digital trees, International Conference on Cnalysis of Clgorithms, DMTCS proc. CD, (2005), 1-10

• [2] R. de la. Briandais, File searching using variable length keys, Proceedings of the AFIPS Spring Joint Computer Conference. AFIPS Press, Reston, Va., (1959), 295-298

• [3] J. E. CoGman, T. Eve, File structures using hashing functions, Communications of the ACM, 13 (1970), 427-432