TOPICS
Search

Tree Searching

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Tree searching is the process of locating a record in a tree data structure. 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.

The following asymptotics concern digital search trees built by inserting n>=1 keys into an initially empty tree. The keys are independent and identically distributed infinite streams of unbiased binary digits. Each graph vertex stores one key, and the successive digits choose the left or right child while descending from the root vertex. A successful query is chosen uniformly from the stored keys, while an unsuccessful query is an independent stream. One comparison with the stored key is counted at each visited graph vertex.

Some constants which arise in this model 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_s(n)+O(n^(-1/2))
(7)
∼lgn-0.716644...+delta_s(n),
(8)

and for an unsuccessful search is

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

(OEIS A086309 and A086310). Here gamma is the Euler-Mascheroni constant, lg is the base 2 logarithm, and s=lgn. The terms delta_s(n), delta_i(n), and rho(n) are small-amplitude oscillations periodic in lgn. The corresponding variance terms epsilon_s(s) and epsilon_i(s) are periodic functions of s.

The variance for searching is

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

(OEIS A086311) and for inserting is

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

(OEIS A086312).

A pair of twin vacancies consists of the two null child pointers at a graph vertex. The expected number of such pairs 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, p. 318). 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·7·15)-1/(3·7·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(z,q) is a Jacobi theta function and theta_1^'(q) denotes its derivative with respect to z, evaluated at z=0, 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, p. 759; 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

Erdős, P. "On Arithmetical Properties of Lambert Series." J. Indian Math. Soc. 12, 63-66, 1948. https://users.renyi.hu/~p_erdos/1948-04.pdf.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. https://doi.org/10.1002/rsa.3240030309.Flajolet, P. and Sedgewick, R. "Digital Search Trees Revisited." SIAM J. Comput. 15, 748-767, 1986. https://doi.org/10.1137/0215054.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching. 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