范围树构建

Question

让我们看看下面的图片

这就是所谓的范围树。我不明白一件事，它看起来类似于二叉搜索树，所以如果我们插入元素，我们可以使用与在二叉搜索树插入期间相同的过程。那么区别是什么呢？

我已阅读教程，并猜测它是一个kd树的查找，查询搜索树（如几何点搜索等），但如何构造它？像二叉搜索树一样，还是需要额外的参数？也许这样

struct range 
{ 
int lowerbound; 
int upperbound, 
int element; 

}; 

和插入过程中，我们必须检查

if(element>lowerbound && element <upperbound) 
then insert node 

请帮我正确理解如何构建一个范围树。

Answer 1

在二元搜索树中插入值时插入一个新节点。

范围搜索树更类似于binary index tree。这两个数据结构具有固定的结构。当你添加/减去一个点到一个给定的范围，你更新节点中的值，但不要引入新的节点。

该结构的构造与KD-tree非常相似：根据给定的点，选择最合适的分割点。

当你学习新的数据结构时，总是考虑支持的操作 - 这将帮助你更快地理解结构。在你的情况下，它会帮助你区分二叉搜索树和距离树。