Почему нужно чередовать измерения в построении kd-дерева

Question

У меня есть вопрос относительно способа разделения пробелов в алгоритме kd-дерева.

Предполагая, что у меня есть точки на плоскости с координатами (x,y). Предполагая, что мы не находимся в конкретной ситуации, когда точки находятся на одной линии. Я думал, почему мы должны чередовать координаты разделения, на одном уровне, использовать ось X, следующий уровень, использовать ось Y. Что имеет значение, если мы используем только направление x для разделения пробелов, у нас всегда есть двоичное дерево, а алгоритм поиска всегда берет log(n) в среднем (при условии, что у нас относительно хорошо сбалансированное дерево).

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

Answer 1

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

Предположим, прямоугольный набор данных с равномерно распределенными точками между -1,000 а также 1,000 во всех направлениях. Если вы сортируете по x, то запрос, который должен вернуть все точки с (-900 < x < 900) && (1 < y < 10) возможно, придется сканировать почти все дерево. log(n) поиск будет работать только если ваш запрос ограничивает x и не yт.е. (1<x<10) && (-inf<y<+inf),