我想扩充二叉搜索树,以便在 O(h) 时间内仍然支持搜索、插入和删除,然后我想实现一种算法来查找给定范围内所有节点值的总和。
最佳答案
如果您向 BST 类添加额外的数据结构,特别是 Hashmap
或 Hashtable
。您的 keys
将是您的 BST 包含的不同数字,您的 values
将是每个数字的出现次数。 BST search(...)
不会受到影响,但是 insert(...)
和 delete(...)
将需要少量代码变化。
Insert
将节点添加到 BST 时,检查该值是否作为键存在于 Hashmap 中。如果它确实存在,则将出现次数加 1。如果它不存在,则将其添加到 Hashmap 中,初始值为 1。
Delete
删除时减少 Hashmap 中的出现次数(假设您没有被告知删除不存在的节点)
Sum
现在求和函数
sum(int start, int end)
您可以反复检查您的 Hashmap 以查看该范围内的哪些数字存在于您的 map 中以及它们出现的次数。使用此方法,您可以通过将 Map 中位于范围内的所有值与其出现次数相加来得出总和。
Complexities
空间:O(n)
时间求和法:O(range size)。
所有其他方法的时间复杂度不受影响。
您没有提到空间限制,所以希望这没问题。我很想知道您是否可以使用 BST 的属性更有效地解决这个问题,但我没有想到。
关于algorithm - 通过扩充 BST 找到二叉搜索树中其值在一定范围内的节点之和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33427479/