algorithm - 通过扩充 BST 找到二叉搜索树中其值在一定范围内的节点之和

Question

我想扩充二叉搜索树，以便在 O(h) 时间内仍然支持搜索、插入和删除，然后我想实现一种算法来查找给定范围内所有节点值的总和。

Answer 1

如果您向 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 的属性更有效地解决这个问题，但我没有想到。