伯爵在时间o在BST与密钥k条目数（H） [英] Count the number of entries in BST with key k in time O(h)

问题描述

我有一个考试，上周，我遇到了以下问题：

I had a exam last week and I faced the following question:

描述你将如何修改二叉搜索树来算   与O（高）时间密钥k T中的条目数。该算法应该返回   整数，而不是列表

Describe how you would modify the binary search tree to count the number of entries in T with key k in O(h) time. This algorithm should return an integer, not a list.

那么考试之后公布的答案被公布，这是如下：

then after the exam the answer was published and it is as follow:

解决方案：通过增加，到每个节点，在所述内部节点的数目修改树 根的子树的那个节点。重新计算这些插入节点时，删除， 并有可能重组。这将需要下面的算法：

Solution: Modify the tree by adding, to each node, the number of internal nodes in the subtree rooted at that node. Recalculate these when nodes are inserted, removed, and potentially restructured. This would need the following algorithm:

但似乎很混乱。我的问题是什么是那些我盘旋他们的红色部分的作用是什么？

But it seems very confusing. My question is what is the role of those parts that I circled them with red?

推荐答案

假设你找到一个节点节点值为 K ，这是你要搜索的内容。现在，假设 node.left.value = K 。你怎么知道的一切子树做 node.left.right ？每个值必须小于或等于 K （因为它是为节点左侧），但比也越大或等于 K （因为它是为 node.left 的右侧）。因此，在该子树的所有值都等于 K 。该算法，作为一种优化，避免向下递归遍历子树在这种情况下，而是在子树总只是自动添加的一切。这是必要的，以获得O（高）运行;如果你在探索那些树的所有节点，运行时可能会与欧米茄（N），如果树中的所有n个值等于 K

Suppose you find a node node with value k, which is what you're searching for. Now, suppose node.left.value = k. What do you know about everything in the subtree node.left.right? Every value there must be less than or equal to k (because it's to the left of node) but also greater than or equal to k (because it's to the right of node.left). Therefore, all the values in that subtrees are equal to k. The algorithm, as an optimization, avoids recursively descending into that subtree in that case and instead just automatically adds everything in that subtree to the total. This is necessary to get the O(h) runtime; if you explored all the nodes in those trees, the runtime might be Ω(n) if all n values in the tree are equal to k.

同样的逻辑也适用于 node.right.left 的情况下，其中 node.right.value = K 。

Similar logic applies for node.right.left in the case where node.right.value = k.

希望这有助于！

这篇关于伯爵在时间o在BST与密钥k条目数（H）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！