給定n (n > 1) 個不同的數字（例如1, 2, 3, ..., n）以隨機順序，將它們連續插入一個空的 BST。其葉子的預期數量是(n 1) / 3。
我嘗試使用數學歸納法： f[n]是具有 n 個不同數字的 BST 構建中的預期葉子數。我想到的是第 n 個數字插入到哪個位置（它將是一個葉節點）。如果它的父節點以前不是葉子，那么葉子的數量會增加一。所以我計算了它是這樣一個節點的可能性：(n / 3 1) / (2n / 3 1) (方程組n0 = n2 1 , n0 n1 n2 = n和n0 = n / 3其中ni表示具有i個子節點的節點數有助于計算每種節點的數量）但它顯然不是1 / 3所以f[n 1]不等于f[n] 1 / 3。
有人可以解釋一下嗎？謝謝！
uj5u.com熱心網友回復：
在插入 n 個節點后，我們期望 f(n) 個葉子。顯然我們有 f(1)=1。
因此，在可以插入新節點的 n 1 個位置中，我們預計其中 2f(n) 個位于葉子下。我們預計非葉空值的數量為 n 1-2f(n)
LEMMA：插入葉子或非葉子空值的概率與葉子或非葉子的預期數量成正比。
設 p(n,m) 是插入 n 個節點后有 m 個葉子的概率。
期望的葉子數是 f(n) = sum_for_m=1_to_n(m * p(n,m))
如果一棵樹有n個節點和m個葉子，那么在葉子下插入下一個節點的概率是2m/(n 1)。因此，在葉子下插入的無條件概率為：
sum_for_m=1_to_n(2m/(n 1) * p(n,m)) = 2f(n)/(n 1)
在葉子下面插入不會改變葉子的數量，但是在非葉子下面插入會使葉子數量增加一，所以我們有：
f(n 1) = f(n) (n 1-2f(n))/(n 1)
或者
f(n) = f(n-1) (n-2f(n-1))/n = 1 f(n-1) - 2f(n-1)/n
現在很容易通過歸納證明 (n 1)/3 適用于所有 n。如果 f(n-1) = n/3，則：
f(n) = 1 n/3 - 2n/3n = (n 1)/3
uj5u.com熱心網友回復：
您的證明是錯誤的，因為它假設某種“平均”樹具有完全正確的葉子數量。
這是一個有效的證明。也許有一些更短的東西，但這對我來說是正確的。
我們想通過歸納證明，當 n=0 時，平均葉數 L[n] 為 0，當 n=1 時為 1，當 n>1 時為 (n 1)/3。
基本情況很容易檢查：L[0] = 0，L[1] = 1，L[2] = 1。
假設（對于歸納）對于小于 n 的所有樹大小都是正確的。也就是說，對于所有 m<n，L[m] = (m 1)/3。
如果您正在改組 (1...n) 然后將它們插入 BST，那么樹的根是排列中的第一項（稱為 k），左孩子有 (k-1) 個東西, 和 (nk) 右孩子的事情。這些子樹中的每一個都滿足歸納假設——它是由一組不同數字的隨機排列形成的 BST。由于期望的線性，并且因為每個 k=1..n 的可能性相同，所以 L[n] = sum(L[k-1] L[nk], k=1..n)/n。
現在，L[n] = sum(L[k-1] L[nk], k=1..n)/n = ((L[0] L[n-1]) (L[1 ] L[n-2]) sum(L[k-1] L[nk], k=3..n-2) (L[n-2] L[1]) (L [n-1] L[0]))/n - 這只是從總和中分離出 k=1、2、n-1 和 n 的情況。
并且 L[0] L[n-1] L[1] L[n-2] = n/3 1 (n-1)/3（通過感應）= 2/3 2n/3
和 (L[k-1] L[nk], k=3..n-2) = sum(k/3 (n-k 1)/3, k=3..n-2) = (n 1)(n-4)/3（通過歸納法）
所以平均葉子數是 (4/3 4n/3 (n 1)(n-4)/3) / n = (n 1)/3。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/520218.html
標籤：算法数学数据结构
下一篇：查找網格中的最小未填充索引