是二叉树的给定值的成员 - 概率答案

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小于您的密钥，您向右移动，但您不知道右侧子树中有多少项。

  • ...