kd-tree アルゴリズムでスペースを分割する方法について質問があります。
平面上に (x,y) 座標の点があると仮定します。ポイントが同じ行にある場合、特定の状況にないと仮定します。あるレベルでは x 軸を使用し、次のレベルでは y 軸を使用して、分割座標を交互に使用する必要がある理由を考えていました。スペースを分割するために x 方向のみを使用する場合に重要なことは、常にバイナリ ツリーがあり、検索アルゴリズムは常に平均で log(n) を取得することです (比較的バランスの取れたツリーがあると仮定します)。
分割方向を交互に変えてスペースを分割すると、さらに何が得られますか? 多次元におけるいくつかの一般的な確率的性質に関連しているのだろうか？