私が見つけた唯一の妥当なスライド セットはこれで、15 ページには次のように書かれています。
- すべてのポイントを x 座標値で並べ替え、バランスの取れたバイナリ ツリー (つまり、範囲ツリー) のリーフ ノードに格納します。
ルートから始まる各ノードには、ツリーの浅い深さに格納されていない y 座標の最大値を持つサブツリー内のポイントが含まれます。そのようなノードが存在しない場合、ノード
は空です
の直前に範囲ツリーを実装したので、そこで使用した例に基づいて、(優先検索ツリーの場合):
7
------ 0 ---------------------
| |
6 6
---- -3 ---- ---- 4 ------
| | | |
4 2 1 3
---- -4 - -2 --- 3 --- 5
| | / \ | | / \
0 (-3,4) (-2,2)(0,7) NIL (4,-4) (5,3)(6,-1)
-5 2
/ \ / \
(-5,6) (-4,0) (2,1) (3,6)
ここで、すべての内部ノードは次の形式です。
mid_x
max y
私が提起している範囲クエリは (-inf, 1) x (-0.5, 5)、つまり (x_low, x_high) x (y_low, y_high) です。
- それでは、ルートから始めましょう。x (=0) が (-inf, 1) にあるかどうか、および 7 > (-0.5, 5) であるかどうかを確認します。したがって、両方の子で進めますが、簡単にするために、左側の子に従います (すべての場合で今から)。
- -3 が x 範囲であるかどうか、および 6 がクエリの y 範囲の上限 (つまり 5) 以上であるかどうかを確認します。ですので、続けます。
- 次のレベルでも同じなので、次のレベルに進み、この内側のノードに注目してください。これは、サブツリーの最大 y が 0 であることを示します (左の子は (-5, 6)) *です。
構築/検索プロセスで何が欠けていますか?
言い換えると：
ツリーの一番左の枝を確認してください。値としてmax_y(引用符の 2 番目の箇条書き)、7、6、4、0 があります。
しかし、その値は、内部ノードの下のサブツリーに格納されている最大の y 値を示すものではありませんか? もしそうなら、これは0and ポイントには当てはまりません(-5, 6)(6 は第 2 レベルで使用されるため、使用されません)。
*私が提起している特定のクエリは、それによって破損しないかもしれませんが、別のクエリは破損する可能性があります。