Вычисление медиан при построении k-d деревьев
Не понимаю принцип вычисления медиан. Разбираю одну задачу, имею следуюший набор данных: (3; 4); (6; 1); (6; 6); (9; 7); (11; 2); (13; 6); (15; 1).
Из этого необходимо построить k-d дерево. Я строю правильно, но у меня не все медианы сходятся с ответом. Вот правильный ответ на скриншоте:
В чём моя проблема: Считаю медиану 1: суммирую все значения Х, делю на 7. Получаю точно так же 9. Считаню медиану 2: суммирую Y от (3; 4); (6; 1); (6; 6) и делю на 3. (1+6+4)/3 = 3.66. Считаю медиану 3: у меня выходит 4 итд. Т.е. очевидно что в решении считали медиану, делили элементы, а потом смещали медиану в сторону минимального из правой части. Почему? Разве не обычная медиана должна использоваться?
Ответы (1 шт):
Вы путаете медиану и среднее значение.
Медиана - такое значение в наборе, что существует поровну элементов меньше его и больше его. Если набор отсортировать, то медиана будет стоять на среднем месте - иметь индекс n/2
(для нечётного числа это место однозначно определено, для чётного один из средней пары считается медианой)
Например, для набора 1,1,3,4,5,6,29 медианой будет 4, а среднее значение - 7.
После первого разделения у вас остаются (3; 4); (6; 1); (6; 6); с набором Y 1,4,6 медиана 4, и (9; 7); (11; 2); (13; 6); (15; 1) с набором Y 1,2,6,7 и медиана 6 как элемент с индексом 2 в сортированном порядке.
P.S. Для нахождения медиан полная сортировка не нужна, есть более быстрые методы (Quickselect)