範圍樹構建

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非常相似：根據給定的點，選擇最合適的分割點。

當你學習新的數據結構時，總是考慮支持的操作 - 這將幫助你更快地理解結構。在你的情況下，它會幫助你區分二叉搜索樹和距離樹。