Зачем нужно чередовать размерность в конструкции kd-дерева

Question

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

Предполагая, что у меня есть точки в плоскости, с координатой (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).