Разъяснение алгоритма ближайшего соседа 2d-дерева

Question

Я пытаюсь реализовать рекурсивный алгоритм ближайшего соседа для 2d-дерева. Рекурсия (и раскрутка рекурсии) все еще немного сбивает меня с толку, и лучший псевдокод, который я нашел, - это вопрос Stackru:

2D KD Tree и поиск ближайшего соседа

Однако в ответе используется значение "Медиана", которое я не знаю, как вычислить. Также статья в Википедии о kd-деревьях содержит псевдокод ближайшего соседа, который не использует медианное значение.

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

Answer 1

Если вы отчаянно не используете медиану, вы можете использовать среднее. Здесь есть простой подход:

Пример 1: Что означает среднее число этих чисел?

6, 11, 7

Add the numbers: 6 + 11 + 7 = 24
Divide by how many numbers (there are 3 numbers): 24 / 3 = 8

Среднее значение 8

---

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

Пример: найти медиану 12, 3 и 5

Поместите их в порядок:

3, 5, 12

Среднее число равно 5, поэтому медиана равна 5.

Источник

Вам не нужно их сортировать. Достаточно псевдосортировки, например, с помощью Quickselect.

Например, в C++ вы можете использовать nth_element() для эффективного поиска медианы. Вы можете увидеть мой вопрос здесь, где я нуждался в медиане для общих измерений. В случае 2D это может быть упрощено.