4

一連のポイントを検索するためのkdツリーを構築しようとしていますが、ウィキペディアの記事での「中央値」の使用について混乱しています。使いやすさのために、ウィキペディアの記事では、kdツリー構築の擬似コードを次のように述べています。

function kdtree (list of points pointList, int depth)
{
    if pointList is empty
        return nil;
    else
    {
        // Select axis based on depth so that axis cycles through all valid values
        var int axis := depth mod k;

        // Sort point list and choose median as pivot element
        select median by axis from pointList;

        // Create node and construct subtrees
        var tree_node node;
        node.location := median;
        node.leftChild := kdtree(points in pointList before median, depth+1);
        node.rightChild := kdtree(points in pointList after median, depth+1);
        return node;
    }
}

ここで中央値を適用する「正しい」方法がよくわからないという理由だけで、「中央値を選択...」の行について混乱しています。

私の知る限り、奇数サイズの（ソートされた）数値リストの中央値は、中央の要素（5つのリストの場合、要素番号3、または標準のゼロベースの配列のインデックス2）であり、偶数サイズの配列の中央値は、2つの「中央」要素の合計を2で割ったものです（つまり、6つのリストの場合、中央値は要素3と4の合計です。ゼロの場合は2と3です。インデックス付き-2で割った値）。

ただし、ここでは明確なポイントのセットを使用しているため、その定義は機能しませんか？それでは、特に長さ2のリストの場合、偶数サイズの数値リストの正しい中央値をどのように選択するのでしょうか。

私はすべての助けに感謝します、ありがとう！

-スティーブン

4

2 に答える 2

3

あなたは中央値の意味を理解しているように見えますが、他の何かと混同されています。明確なポイントのセットとはどういう意味ですか？

ウィキペディアによって提示されたコードは再帰関数です。ポイントのセットがあるので、ルートノードを作成し、セットの中央値を選択します。次に、関数を再帰的に呼び出します。左側のサブツリーの場合は、元のリストの分割値（中央値）よりも小さいすべてのポイントを持つパラメーターを渡し、右側のサブツリーの場合は、同じ以上のサブツリーを渡します。次に、サブツリーごとに、同じことが発生するノードが作成されます。こんなふうになります：

First step (root node):
Original set: 1 2 3 4 5 6 7 8 9 10
Split value (median): 5.5

Second step - left subtree:
Set: 1 2 3 4 5
Split value (median): 3

Second step - right subtree:
Set: 6 7 8 9 10
Split value (median): 8

Third step - left subtree of left subtree:
Set: 1 2
Split value (median): 1.5

Third step - right subtree of left subtree:
Set: 3 4 5
Split value (median): 4

等。

したがって、中央値は、そのサブツリーに入る一連の数値（ポイント、データ）に基づいて、ツリー内の各ノードに対して選択されます。お役に立てれば。

于 2010-05-28T07:32:14.223 に答える
0

片側に他の要素と同じ数の要素がある軸を選択する必要があります。ポイントの数が奇数であるか、ポイントが不可能なように配置されている場合は、軸を選択して、可能な限り均等に再分割します。

于 2010-05-28T07:13:37.697 に答える