我上周参加了一次考试，我遇到了以下问题：
描述如何修改二叉搜索树以在 O(h) 时间内计算 T 中带有键 k 的条目数。这个算法应该返回一个整数，而不是一个列表。
然后在考试后公布答案，如下：
解决方案：通过向每个节点添加以该节点为根的子树中的内部节点数来修改树。在插入、删除和可能重组节点时重新计算这些。这将需要以下算法：
但这似乎很混乱。我的问题是我用红色圈出的那些部分的作用是什么？
问问题
616 次
1 回答
2
假设您找到一个node带有 value的节点k，这就是您要搜索的内容。现在，假设node.left.value = k. 您对子树中的所有内容了解node.left.right多少？每个值都必须小于或等于k（因为它在 的左侧node），但也必须大于或等于k（因为它在 的右侧node.left）。因此，该子树中的所有值都等于k。作为一种优化，该算法避免在这种情况下递归下降到该子树，而是自动将该子树中的所有内容添加到总数中。这是获得 O(h) 运行时所必需的；如果您探索了这些树中的所有节点，如果树中的所有 n 值都等于 ，则运行时间可能为 Ω(n) k。
类似的逻辑适用node.right.left于 的情况node.right.value = k。
希望这可以帮助！
于 2013-10-13T23:36:06.967 回答