Иерархия дерева KD

Question

У меня есть чисто теоретический вопрос о иерархии дерева KD. Предположим, что у нас есть двумерное дерево с «левым правилом».

Один из узлов дерева имеет двух детей, которые должны быть отсортированы по значению Х. В то же время оба ребенка имеют одинаковое значение Х.

Итак, что я должен делать в этом случае?

На мой взгляд, есть два варианта, скорее, я сортирую их по второму (Y) значению и распределяю согласно «левому правилу» - слева идет один с наименьшим значением Y, а справа - с большим ,

И вторым вариантом может быть поиск расстояний между этими дочерними точками, и он является родителем и распределяет его по значению расстояния: ближайший идет влево, а другой вправо.

Answer 1

Может быть, это очень неудачный пример, но все еще может быть проблема наличия двух узлов как «срединных» кандидатов с тем же параметром оценки, не имеет значения X или Y.