TOPICS
Search

Tree Searching

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

alpha=sum_(k=1)^(infty)1/(2^k-1)
(1)
=1-(psi_(1/2)^((0))(1))/(ln2)
(2)
=1.6066951524...
(3)
beta=sum_(k=1)^(infty)1/((2^k-1)^2)
(4)
=(psi_(1/2)^((1))(1)+ln2psi_(1/2)^((0))(1))/(ln^22)-1
(5)
=1.1373387363...
(6)

(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

E=(lnn)/(ln2)+(gamma-1)/(ln2)-alpha+3/2+delta(n)+O(n^(-1/2))
(7)
∼lgn-0.716644...+delta(n),
(8)

and for an unsuccessful search is

E=(lnn)/(ln2)+gamma/(ln2)-alpha+1/2+delta(n)+O(n^(-1/2))
(9)
∼lgn-0.273948...+delta(n)
(10)

(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

V∼1/(12)+(pi^2+6)/(6(ln2)^2)-alpha-beta+epsilon(s)
(11)
∼2.844383...+epsilon(s)
(12)

(OEIS A086311) and for inserting is

V∼1/(12)+(pi^2)/(6(ln2)^2)-alpha-beta+epsilon(s)
(13)
∼0.763014...+epsilon(s)
(14)

(OEIS A086312).

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

<A_n>=[c+rho(n)]n+O(sqrt(n)),
(15)

where

c=theta+1-1/Q(1/(ln2)+alpha^2-alpha)
(16)
=0.3720486812...
(17)

(OEIS A086313), which can also be written

c=1/(ln2)int_0^inftyx/(1+x)(dx)/((1+x)(1+1/2x)(1+1/4x)(1+1/8x)...).
(18)

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

Q=product_(k=1)^(infty)(1-1/(2^k))
(19)
=(1/2;1/2)_infty
(20)
=1/3-1/(3·7)+1/(3·5·15)-1/(3·5·15·31)+...
(21)
=exp[-sum_(n=1)^(infty)1/(n(2^n-1))]
(22)
=sqrt((2pi)/(ln2))exp((ln2)/(24)-(pi^2)/(6ln2))×product_(n=1)^(infty)[1-exp(-(4pi^2n)/(ln2))]
(23)
=2^(-7/24)[theta_1^'(2^(-1/2))]^(1/3)
(24)
=0.2887880950
(25)

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

theta=sum_(k=1)^(infty)(k2^(k(k-1)/2))/(1·3·7·15...(2^k-1))sum_(j=1)^(k)1/(2^j-1)
(26)
=7.7431319855...
(27)

(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

References

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 Resource. https://mathworld.wolfram.com/TreeSearching.html

Subject classifications