c++ - レンジツリーの構築

Question

次の写真を考えてみましょう

これはいわゆる範囲ツリーです。わかりませんが、二分探索木に似ているので、要素を挿入する場合は、二分探索木挿入時と同じ手順で使用できます。では、違いは何ですか？

チュートリアルを読んだことがありますが、これはkdツリーのバリエーションであり、検索ツリーのクエリ（幾何学的な点の検索など）であると思いますが、どのように構築するのですか？二分探索木のように、または追加のパラメータが必要ですか？多分このように

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

};

挿入中にチェックする必要があります

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

範囲ツリーの構築方法を正しく理解するのを手伝ってください。

Answer 1

二分探索木では、値を挿入すると新しいノードが挿入されます。

範囲検索ツリーは、バイナリ インデックス ツリーに似ています。これら 2 つのデータ構造には、固定構造があります。特定の範囲にポイントを加算/減算すると、ノードの値が更新されますが、新しいノードは導入されません。

この構造の構築はKD-treeの構築とよく似ています: 与えられた点に基づいて、最も適切な分割点を選択します。

新しいデータ構造を学習するときは、サポートされている操作を常に考慮してください。これにより、構造をより速く理解することができます。あなたの場合、二分探索木と範囲木を区別するのに役立ちました。