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
(1)
| |||
(2)
| |||
(3)
| |||
(4)
| |||
(5)
| |||
(6)
|
(OEIS A065442 and A065443), where is a q-polygamma function. Erdős (1948) proved that is irrational, and is sometimes known as the Erdős-Borwein constant.
The expected number of comparisons for a successful search is
(7)
| |||
(8)
|
and for an unsuccessful search is
(9)
| |||
(10)
|
(OEIS A086309 and A086310). Here is the Euler-Mascheroni constant, , , and are small-amplitude periodic functions, and lg is the base 2 logarithm.
The variance for searching is
(11)
| |||
(12)
|
(OEIS A086311) and for inserting is
(13)
| |||
(14)
|
(OEIS A086312).
The expected number of pairs of twin vacancies in a digital search tree is
(15)
|
where
(16)
| |||
(17)
|
(OEIS A086313), which can also be written
(18)
|
(Flajolet and Richmond 1992). Here, the individual pieces are given by
(19)
| |||
(20)
| |||
(21)
| |||
(22)
| |||
(23)
| |||
(24)
| |||
(25)
|
(OEIS A048651), where is a Jacobi theta function, and
(26)
| |||
(27)
|
(OEIS A086315; Flajolet and Sedgewick 1986, Finch 2003, with a typo in the exponent appearing in the original paper corrected).