主題
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.tw/TreeSearching.html

主題分類