是二叉樹的給定值的成員 - 概率答案

Question

問題：

考慮到與N節點BST，與基數D（域名正在爲節點密鑰的可能值）的域。 給定域中的密鑰，但可能會或可能不是BST的成員。 在開始時，我們對節點在樹中的信心應該是1/D，但是當我們深入樹中時，D和N大約分成兩半。這表明我們的信心，即我們的關鍵是樹的成員應該保持不變，直到我們觸底或發現關鍵。然而，我不確定這個推理是否完成，因爲它看起來更像是我們從D中選擇N個節點。

我在想this，但這裏的推理看起來還不完整。有人能指出我正確的方向嗎？

Answer 1

Apriori，你鍵入樹的概率是N/D。

不失一般性，假設節點的取值範圍是[1..D]。

當你走在樹，或者：

• 當前節點的關鍵，因此P = 1

• 當前節點值C比你的關鍵字時，你向左走匹配，但是你不知道左子樹中有多少項。現在你可以做出以下假設之一：

  • 樹是平衡的。子樹中的範圍是[1..C-1]，子樹中有（D-1）/ 2個節點。因此，P =（（D-1）/ 2）/（C-1）
  • 樹不平衡。子樹中的範圍是[1..C-1]，子樹中節點數的最大似然估計是N *（C-1）/ D。因此，P =（N *（C-1）/ D）/（C-1）= N/D。 （無變化）
  • 如果您瞭解有關樹如何構建的更多信息 - 您可以爲子樹中的節點數創建更好的MLE。

• 當前節點的值C小於您的密鑰，您向右移動，但您不知道右側子樹中有多少項。

  • ...