Балансировка дерева KD
Таким образом, при балансировке дерева KD вы должны найти медиану, а затем поместить все элементы, которые меньше в левом поддереве, а те, которые больше в правом. Но что произойдет, если у вас будет несколько элементов с одинаковым значением медианы? Они идут в левое поддерево, право или вы их отбрасываете?
Я спрашиваю, потому что я пытался сделать несколько вещей, и это влияет на результаты моего алгоритма поиска ближайшего соседа, и есть некоторые случаи, когда все элементы для данного раздела дерева будут иметь одинаковое значение, и поэтому я не знаю, как разделить их в этом случае.
Решение
Неважно, где вы их положили. Желательно, чтобы ваше дерево было сбалансированным. Поэтому разместите столько слева, сколько необходимо, чтобы сохранить оптимальный баланс!
Если ваш текущий радиус поиска прикосновений Медиана, вам придется проверить другую часть, это все, что вам нужно для обработки связанных объектов на другой стороне. Обычно это дешевле, чем сложная обработка прикрепления нескольких элементов в любом месте.
Другие решения
При выполнении алгоритма стиля поиска часто рекомендуется размещать элементы, равные медиане, по обе стороны от медианы.
Один из методов заключается в том, чтобы поместить медианные выравнивающие элементы на «ту же сторону», где они находились до того, как вы делали раздел. Другой способ — поместить первый слева, второй справа и т. Д.
Другое решение состоит в том, чтобы иметь структуру данных сгущения, которая просто «считает» вещи равными, а не хранит каждую из них по отдельности. (если у них есть дополнительное состояние, то вы можете сохранить это дополнительное состояние вместо просто счетчика)
Я не знаю, что подходит в вашей ситуации.
Это зависит от вашей цели.
Для таких задач, как точное совпадение или поиск по диапазону, возможность повторения одного и того же значения с обеих сторон усложнит запрос, а повторение одного и того же значения на обоих листах увеличит сложность времени.
Решение — хранить все медианы (значения, равные значению медианы) в узле, ни слева, ни справа. Большинство вариантов kd-деревьев хранят медианы на внутренних узлах. Если их окажется много, вы можете использовать другое (k-1) d дерево для медиан.