我想扩充一个二进制搜索树，以便在O（h）时间内仍然支持搜索、插入和删除，然后我想实现一个算法来查找给定范围内所有节点值的总和。
如果向BST类添加额外的数据结构，特别是Hashmap或Hashtable。您的keys将是BST包含的不同数字，而values是每个数字的出现次数。BST search(...)不会受到影响，但是insert(...)和delete(...)将需要轻微的代码更改。
插入
将节点添加到BST时，请检查该值是否作为键存在于Hashmap中。如果确实存在，则将出现次数增加1。如果它不存在，则将其添加到初始值为1的Hashmap中。
删除
删除时，递减Hashmap中的出现次数（假设您没有被告知删除不存在的节点）
总和
现在是求和函数
sum(int start, int end)
您可以反复检查Hashmap，以查看映射中存在该范围中的哪些数字及其出现次数。使用此选项，您可以通过将Map中范围内的所有值乘以它们的出现次数来构建总和。
复杂度
空格：O（n）求和时间法：O（范围大小）
所有其他方法的时间复杂性不会受到影响。
你没有提到空间约束，所以希望这是可以的。我很有兴趣看看你是否可以更有效地使用BST的属性来解决这个问题。