したがって、KD ツリーのバランスをとるときは、中央値を見つけて、それよりも小さいすべての要素を左側のサブツリーに配置し、大きいものを右側に配置する必要があります。しかし、中央値と同じ値を持つ要素が複数ある場合はどうなるでしょうか? それらは左のサブツリーに入りますか、右のサブツリーに入りますか、それとも破棄しますか?
私は複数のことを試してみましたが、最近傍検索アルゴリズムの結果に影響を与え、ツリーの特定のセクションのすべての要素がすべてまったく同じ値を持つ場合があるため、質問しません。その場合にそれらを分割する方法を知っています。
どこに置いても構いません。できれば、ツリーのバランスを保ってください。したがって、最適なバランスを保つために、必要な数だけ左側に配置してください。
現在の検索半径が中央値に接している場合は、他の部分を確認する必要があります。反対側で結ばれたオブジェクトを処理するために必要なのはそれだけです。これは通常、複数の要素をどこにでも接続するという複雑な処理よりも安価です。
検索スタイルのアルゴリズムを実行する場合、中央値の両側に中央値に等しい要素を配置することをお勧めします。
1 つの方法は、分割を行う前に中央値の等しい要素を「同じ側」に配置することです。もう 1 つの方法は、最初のものを左に、2 番目のものを右に、というように配置することです。
別の解決策は、それぞれを個別に保存するのではなく、等しいものを「カウント」するだけのクランプデータ構造を持つことです。(追加の状態がある場合は、カウントの代わりにその追加の状態を保存できます)
あなたの状況でどれが適切かわかりません。
それはあなたの目的によります。
完全一致や範囲検索などの問題では、両側で同じ値が繰り返される可能性があるため、クエリが複雑になり、両方の葉で同じ値が繰り返されると、時間の複雑さが増します。
解決策は、すべての中央値 (中央値の値に等しい値) をノードに保存することです。左にも右にもありません。kd ツリーのほとんどのバリアントは、内部ノードに中央値を格納します。それらがたまたま多い場合は、中央値に別の (k-1)d ツリーを使用することを検討できます。