Kd-Tree Question

Question

Я пытаюсь реализовать и понять KdTree, Следующая ссылка, которую я нашел.http://ldots.org/kdtree/#buildingAkDTree Но я не понимаю следующего алгоритма

tuple function build_kd_tree(int depth, set points):
    if points contains only one point:
        return that point as a leaf.

    if depth is even:
        Calculate the median x-value.
        Create a set of points (pointsLeft) that have x-values less than
            the median.
        Create a set of points (pointsRight) that have x-values greater
            than or equal to the median.
    else:
        Calculate the median y-value.
        Create a set of points (pointsLeft) that have y-values less than
            the median.
        Create a set of points (pointsRight) that have y-values greater
            than or equal to the median.

    treeLeft = build_kd_tree(depth + 1, pointsLeft)
    treeRight = build_kd_tree(depth + 1, pointsRight)

    return(median, treeLeft, treeRight)

Я не понимаю, в чем смысл Calculate the median x-value.

Answer 1

Ваши points имеют значения x и y. медиана значений x может быть получена путем сортировки по x, затем взятия среднего элемента x (для нечетного числа points) или среднего значения двух средних points 'x (для четного числа points).

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