主题
Search

树搜索

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

在数据库结构中，通常关注两个量：找到现有随机记录和

1. 找到现有随机记录所需的平均比较次数，以及

2. 将新的随机记录插入数据结构所需的平均比较次数。

数字树搜索理论中出现的一些常数是

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 和 A065443)，其中 psi_q(z) 是一个 q-多伽玛函数。Erdős (1948) 证明了 alpha 是无理数，而 alpha 有时被称为 Erdős-Borwein 常数。

成功搜索的期望比较次数是

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

而不成功搜索的期望比较次数是

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

(OEIS A086309 和 A086310)。 这里 gamma 是欧拉-马歇罗尼常数， delta(n), epsilon(s), 和 rho(n) 是小振幅周期函数，而 lg 是以 2 为底的对数。

搜索的方差是

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

(OEIS A086311) 而插入的方差是

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

(OEIS A086312)。

数字搜索树中双空位对的期望数量是

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

其中

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

(OEIS A086313)，也可以写成

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

(Flajolet 和 Richmond 1992)。 这里，各个部分由下式给出

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)，其中 theta_1(q) 是一个 雅可比 theta 函数，以及

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 和 Sedgewick 1986, Finch 2003，原始论文中出现的指数错误已更正)。

另请参阅

Erdős-Borwein 常数

使用 探索

参考文献

Finch, S. R. "Binary Search Tree Constants" and "Digital Search Tree Constants." §5.13 和 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, 和 A086315 in "The On-Line Encyclopedia of Integer Sequences."

在 上被引用

树搜索

引用为

Weisstein, Eric W. “树搜索”。 来自 —— 资源。 https://mathworld.net.cn/TreeSearching.html

主题分类