Запутался в определении «медианы» при построении дерева kd - PullRequest
Новая
       11

Запутался в определении «медианы» при построении дерева kd

4 голосов
/ 28 мая 2010

Я пытаюсь создать 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 в стандартном массиве с нулями) ), а медиана массива четного размера - это сумма двух «средних» элементов, разделенных на два (иначе, для списка из 6 вещей, медиана - это сумма элементов 3 и 4 - или 2 и 3, если индексирован нулями - делится на 2.).

Однако, конечно, это определение здесь не работает, так как мы работаем с определенным набором точек? Как тогда выбрать правильную медиану для списка чисел четного размера, особенно для списка длины 2?

Я ценю любую помощь, спасибо!

-Stephen

Ответы [ 2 ]

3 голосов
/ 28 мая 2010

Мне кажется, что вы понимаете значение медианы, но вас смущает что-то еще. Что вы имеете в виду, чтобы быть четким набором точек?

Код, представленный Википедией, является рекурсивной функцией. У вас есть набор точек, поэтому вы создаете корневой узел и выбираете медиану из набора. Затем вы вызываете функцию рекурсивно - для левого поддерева вы передаете параметр со всеми точками, меньшими, чем значение разделения (медиана) исходного списка, для правого поддерева вы передаете равные и более крупные. Затем для каждого поддерева создается узел, где происходит то же самое. Это выглядит так: 

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

Etc.

Таким образом, медиана выбирается для каждого узла в дереве на основе набора чисел (точек, данных), которые входят в это поддерево. Надеюсь, это поможет.

0 голосов
/ 28 мая 2010

Вы должны выбрать ось с таким количеством элементов на одной стороне, чем на другой. Если количество точек нечетное или точки расположены таким образом, что это невозможно, просто выберите ось, чтобы дать как можно более равномерное распределение.

...