Tree Searching

In database structures, two quantities are generally of interest: the average number of comparisons required to

1. Find an existing random record, and

2. Insert a new random record into a data structure.

Some constants which arise in the theory of digital tree searching are


(OEIS A065442 and A065443), where psi_q(z) is a q-polygamma function. Erdős (1948) proved that alpha is irrational, and alpha is sometimes known as the Erdős-Borwein constant.

The expected number of comparisons for a successful search is


and for an unsuccessful search is


(OEIS A086309 and A086310). Here gamma is the Euler-Mascheroni constant, delta(n), epsilon(s), and rho(n) are small-amplitude periodic functions, and lg is the base 2 logarithm.

The variance for searching is


(OEIS A086311) and for inserting is


(OEIS A086312).

The expected number of pairs of twin vacancies in a digital search tree is




(OEIS A086313), which can also be written


(Flajolet and Richmond 1992). Here, the individual pieces are given by


(OEIS A048651), where theta_1(q) is a Jacobi theta function, and


(OEIS A086315; Flajolet and Sedgewick 1986, Finch 2003, with a typo in the exponent appearing in the original paper corrected).

See also

Erdős-Borwein Constant

Explore with Wolfram|Alpha


Finch, S. R. "Binary Search Tree Constants" and "Digital Search Tree Constants." §5.13 and 5.14 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 349-361, 2003.Flajolet, P. and Richmond, B. "Generalized Digital Trees and their Difference-Differential Equations." Random Structures and Algorithms 3, 305-320, 1992.Flajolet, P. and Sedgewick, R. "Digital Search Trees Revisited." SIAM Review 15, 748-767, 1986.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, pp. 21, 134, 156, 493-499, and 580, 1973.Sloane, N. J. A. Sequences A048651, A065442, A065443, A086309, A086310, A086311, A086312, A086313, and A086315 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Tree Searching

Cite this as:

Weisstein, Eric W. "Tree Searching." From MathWorld--A Wolfram Web Resource.

Subject classifications