k -dツリー

軸に沿った分割平面を選択する方法は多数あるため、 k -d ツリーを構築する方法も多数あります。k - d ツリー構築の標準的な方法には、次の制約があります。^{[ 4 ]}

• ツリーを下っていくと、分割面を選択するために使用される軸が順番に切り替わります。（例えば、3次元ツリーでは、ルートはx軸に沿った平面を持ち、ルートの子は両方ともy軸に沿った平面を持ち、ルートの孫はすべてz軸に沿った平面を持ち、ルートの曾孫はすべてx軸に沿った平面を持ち、ルートの玄孫はすべてy軸に沿った平面を持つ、といった具合です。）
• 点の挿入は、分割平面を作成するために使用される軸上の座標に関して、サブツリーに挿入される点の中央値を選択することによって行われます。（ n個の点のすべてを事前にアルゴリズムに入力することを前提としています。）

この方法を用いると、各葉ノードが根ノードからほぼ同じ距離にある、バランスのとれたk -d木が得られます。しかし、バランスのとれた木は、必ずしもすべての用途にとって最適とは限りません。

中央値を選択する必要はないことに注意してください。中央値を選択しない場合、ツリーがバランスが取れているという保証はありません。複雑なコーディングを避けるために${\displaystyle O(n)}$中央値探索アルゴリズム^{[ 5 ] [ 6 ]}または${\displaystyle O(n\log(n))}$ヒープソートやマージソートなどのソート手法を用いてn個の点をソートする場合、ランダムに選択した固定数の点をソートし、それらの点のメディアンを分割平面として使用するのが一般的な方法です。実際には、この手法によってバランスの取れたツリーが得られることがよくあります。

n個の点のリストが与えられた場合、以下のアルゴリズムは中央値探索ソートを使用して、それらの点を含むバランスのとれたk -d木を構築します。

function kdtree (ポイントのリストpointList, int depth) { // 深度に基づいて軸を選択することで、軸がすべての有効な値を循環するようにします。var int axis := depth mod k; // ポイントリストをソートし、中央値をピボット要素として選択します 。select median by axis from pointList;// ノードを作成し、サブツリーを構築する node.location := median; node.leftChild := kdtree( pointList内の中央値より前の点、深さ+1); node.rightChild := kdtree(points in pointList after median, depth+1); return node; }

中央値より「後」の点には、現在の次元において中央値より厳密に大きい点のみが含まれるのが一般的です。現在の次元において中央値上にある点については、すべての次元でそれらを比較する関数を定義することが可能です。場合によっては、中央値に等しい点が中央値の片側に位置することを許容することもあります。例えば、点を「より小さい」部分集合と「以上」部分集合に分割するなどです。

このアルゴリズムは、任意のノードについて、左サブツリー内のすべてのノードが分割平面の片側にあり、右サブツリー内のすべてのノードが反対側にあるという不変条件を作成します。分割平面上にある点は、どちらの側にも現れる可能性があります。ノードの分割平面は、そのノードに関連付けられた点（コードではnode.locationと呼ばれます）を通ります。

バランスのとれたk -d ツリーを構築するための代替アルゴリズムでは、ツリー構築前にデータを事前ソートします。そして、ツリー構築中に事前ソートの順序を維持するため、各分割レベルで中央値を求めるコストのかかるステップが不要になります。このようなアルゴリズムのうち 2 つは、3 次元コンピュータグラフィックスのレイ トレーシングの実行時間を改善するために、三角形をソートするバランスのとれたk -d ツリーを構築します。これらのアルゴリズムは、k -d ツリーを構築する前にn個の三角形を事前ソートし、次にツリーを構築します。${\displaystyle O(n\log n)}$最良の場合で時間。^{[ 7 ] [ 8 ]}点をソートするためにバランスのとれたk -d木 を構築するアルゴリズムの最悪ケースの複雑さは${\displaystyle O(kn\log(n))}$^{[ 9 ] [ 10 ]}このアルゴリズムは、k次元のそれぞれでn個の点を事前にソートします。${\displaystyle O(n\log(n))}$ツリーを構築する前に、ヒープソートやマージソートなどのソートを実行します。そして、ツリー構築中にこれらのk個の事前ソートの順序を維持し、各分割レベルでの中央値を求めることを回避します。

k -d木に新しい点を追加する方法は、他の探索木に要素を追加する方法と同じです。まず、ルートから始めて木をたどり、挿入する点が分割平面の「左側」にあるか「右側」にあるかに応じて、左の子ノードまたは右の子ノードに移動します。子ノードを配置するノードに到達したら、新しい点を葉ノードの左の子ノードまたは右の子ノードとして追加します。これも、新しいノードがノードの分割平面のどちら側にあるかに応じて行います。

このようにポイントを追加すると、ツリーのバランスが崩れ、ツリーのパフォーマンスが低下する可能性があります。ツリーのパフォーマンス低下の速度は、追加されるツリーポイントの空間分布と、ツリーのサイズに対する追加ポイントの数に依存します。ツリーのバランスが崩れすぎた場合は、最近傍探索など、ツリーのバランスに依存するクエリのパフォーマンスを回復するために、ツリーを再バランス調整する必要が生じる場合があります。

既存のk -d ツリーから不変条件を破らずに点を削除する最も簡単な方法は、対象ノードの子からすべてのノードと葉のセットを作成し、ツリーのその部分を再作成することです。^{[ 2 ]}

別のアプローチとしては、削除された点の代替点を見つけることが挙げられます。^{[ 11 ]}まず、ノードを見つけます。${\displaystyle R}$削除する点を含む点。基本ケースでは、R が葉ノードであるため、置換は不要です。一般ケースでは、置換点を見つけます。${\displaystyle p}$根元が${\displaystyle R}$. 保存されているポイントを置き換えます${\displaystyle R}$と${\displaystyle p}$.次に、再帰的に削除します${\displaystyle p}$。

代替点を見つけるには、${\displaystyle R}$差別する${\displaystyle x}$（言う）そして${\displaystyle R}$右の子を持つ、最小の点を見つける${\displaystyle x}$右の子を根とする部分木から値を取得する。そうでない場合は、最大値を持つ点を見つける。${\displaystyle x}$左の子を根とする部分木からの値。

k -d木のバランスを取るには注意が必要です。なぜなら、 k -d木は複数の次元でソートされているため、木の回転手法を使ってバランスを取ると不変条件が破られる可能性があるからです。

バランス型k -d木にはいくつかのバリエーションが存在する。これらには、分割型k -d木、擬似k -d木、KDB木、hB木、Bkd木などがある。これらのバリエーションの多くは適応型kd木である。

最近傍探索（NN）アルゴリズムは、与えられた入力点に最も近いツリー内の点を見つけることを目的としています。この探索は、ツリーの特性を利用して探索空間の大部分を迅速に排除することで効率的に行うことができます。

k -d木における最近傍探索は、以下の手順で行われます。

1. アルゴリズムはルートノードから開始し、検索点を挿入する場合と同様に、ツリーを再帰的に下に進みます（つまり、分割された次元において、その点が現在のノードより小さいか大きいかに応じて、左または右に進みます）。
2. アルゴリズムがリーフノードに到達すると、ノードポイントをチェックし、距離が「現在の最良値」よりも優れている場合、そのノードポイントが「現在の最良値」として保存されます。
3. このアルゴリズムはツリーの再帰を巻き戻し、各ノードで以下の手順を実行します。
   1. 現在のノードが現在の最適ノードよりも近い場合、そのノードが現在の最適ノードとなる。
   2. このアルゴリズムは、分割平面の反対側に、現在の最適解よりも探索点に近い点が存在するかどうかをチェックします。概念的には、これは、現在の最短距離に等しい半径を持つ探索点を中心とする超球と分割超平面を交差させることによって行われます。超平面はすべて軸に平行であるため、これは、探索点の分割座標と現在のノード間の距離が、探索点から現在の最適解までの距離（全体の座標）よりも小さいかどうかを比較するだけの単純な方法で実装されます。
      1. 超球が平面を横切る場合、平面の反対側により近い点が存在する可能性があるため、アルゴリズムは現在のノードからツリーのもう一方の枝を下り、より近い点を探し、探索全体と同じ再帰プロセスに従う必要があります。
      2. 超球面が分割平面と交差しない場合、アルゴリズムはツリーを上方向に進み続け、そのノードの反対側の枝全体が削除されます。
4. アルゴリズムがルートノードに対するこの処理を完了すると、検索は完了します。

一般的に、このアルゴリズムは平方根の計算を避けるために、比較に距離の二乗を使用します。さらに、現在の最良距離の二乗を比較変数に保持することで、計算量を削減できます。

このアルゴリズムは、簡単な修正を加えることで様々な方法で拡張できます。例えば、現在の最良点を1つだけでなくk個保持することで、ある点のk個の最近傍点を提供できます。分岐はk個の点が見つかった場合にのみ削除され、その分岐にはk個の現在の最良点よりも近い点があってはなりません。

より高速に実行するために、近似アルゴリズムに変換することもできます。たとえば、ツリー内で調べる点の数に上限を設定するか、リアルタイムクロックに基づいて検索プロセスを中断することによって（ハードウェア実装では後者の方が適切な場合があります）、近似的な最近傍探索を実現できます。既にツリー内に存在する点の最近傍は、距離がゼロのノードの精緻化を更新しないことで実現できます。その結果、一意ではないものの元の検索点と同じ位置にある点が破棄されるという欠点があります。

近似最近傍法は、最適な点を網羅的に探索しないことで大幅な速度向上を実現できるため、ロボット工学などのリアルタイムアプリケーションで有用です。その実装例の一つに、ベストビン優先探索があります。

範囲検索は、パラメータの範囲を検索します。たとえば、ツリーが収入と年齢に対応する値を格納している場合、範囲検索は、年齢が20歳から50歳の間で、収入が50,000から80,000の間のツリーのすべてのメンバーを探すようなものになります。kdツリーは、ツリーの各レベルでドメインの範囲を半分に分割するため、範囲検索を実行するのに役立ちます。

二分探索木の解析により、 n個のノードを含むk次元k -d木における範囲探索の最悪ケース時間は、次の式で与えられることがわかった。^{[ 12 ]}

${\displaystyle t_{\text{worst}}=O\left(k\cdot n^{1-{\frac {1}{k}}}\right)}$

点の代わりに、k -d ツリーには長方形または超直方体も含まれることがあります。^{[ 15 ] [ 16 ]}したがって、範囲検索は、検索矩形と交差するすべての長方形を返す問題になります。ツリーは、すべての長方形を葉に配置して通常の方法で構築されます。直交範囲検索では、中央値と比較するときに反対の座標が使用されます。たとえば、現在のレベルが x _{highに沿って分割されている場合、検索矩形の x low}座標を確認します。中央値が検索矩形の x _low座標より小さい場合、左ブランチの長方形は検索矩形と交差することはないため、剪定できます。そうでない場合は、両方のブランチを走査する必要があります。1次元の特殊なケースである区間ツリーも参照してください。

葉にのみ点が格納されたk -d 木を定義することも可能である。 ^{[ 4 ]}この形式のk -d 木では、標準的な中央値分割以外のさまざまな分割メカニズムが使用可能である。中間点分割ルール^{[ 17 ]}は、点の分布に関係なく、検索対象空間の最長軸の中央を選択する。これにより、アスペクト比は最大で 2:1 となることが保証されるが、深さは点の分布に依存する。スライディング中間点と呼ばれるバリエーションでは、分割の両側に点がある場合にのみ中央で分割する。そうでない場合は、中央に最も近い点で分割する。Maneewongvatana と Mount は、これが一般的なデータセットで「十分な」パフォーマンスを提供すると示している。

スライディングミッドポイントを使用すると、近似最近傍クエリに回答できます。${\displaystyle O\left({\tfrac {1}{{\epsilon \ }^{d}}}\log n\right)}$概算範囲のカウントは次のように答えることができます。${\displaystyle O\left(\log n+{\left({\tfrac {1}{\epsilon \ }}\right)}^{d}\right)}$この方法で。