1632
правки
Изменения
м
''ПримечаниеСтроится это дерево следующим образом: в книжке описывается двумерный вариантразобьём все точки вертикальной прямой так, чтобы слева (нестрого) и на лекцияхсправа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, кажетсяно разбивать будем уже не вертикальной, только он был, поэтому а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее считается(будем считать, что <tex>k = 2</tex>. Обобщение (случай бОльших размерностей обрабатывается аналогично), поэтому на большую размерность достаточно просто додумать при необходимостиследующем уровне вновь будем разбивать вертикальными прямыми).''
Строится это дерево следующим образом''Замечание: разобьём все точки вертикальной прямой такпроблемы могут возникнуть, если много точек имеют одинаковую координату, чтобы слева (нестрого) и справа (строго) от неё было тогда разбить примерно поровну точек не получится (для этого посчитаем медиану первых координатпочти все точки будут лежать на медиане и попадут в левую часть). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже Лучший способ борьбы с этим {{---}} не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат)вспоминать о данной проблеме совсем. И так далее (раз считаемНо вообще с этим борются, что <tex>k = 2</tex>используя composite numbers, то на следующем уровне вновь будем разбивать вертикальными прямымиесть сравнивая ещё и по другой (другим)координате.''
''Замечание: проблемы могут возникнуть, если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим {{---}} не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbers, то есть сравнивая ещё и по другой (другим) координате. Не думаю, что об этом нужно много писать.'' Строить дерево будем Реализовывать построение можно рекурсивно с помощью функции <tex>BuildKdTree(P, Depth)</tex>, принимающей множество точек и глубину. В зависимости от остатка при делении на размерность (в нашем случае при <tex> k = 2 </tex> от чётностиразмерности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод:
rollbackEdits.php mass rollback
{{ptreadyready}}
== Определение и построение ==
[[Файл:Kd-tree.png | 500px | thumb | Пример]]
'''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике.
<code>
</code>
{{Лемма
|about=
О времени построения
|statement=
Построение выполняется за <tex>O(n \log n)</tex>.
|proof=
Время построения обозначим <tex>T(n)</tex>. Поиск медианы можно сделать за линейное время, поэтому достаточно очевидно, что:
<tex>T(n) = O(1)</tex> if <tex>n = 1</tex>.
<tex>T(n) = O(n) + 2 \cdot T(n / 2)</tex>, otherwise.
Решением этого является <tex>T(n) = O(n \log n)</tex>.
Также стоит отметить, что можно и не искать медиану за линейное время, а просто посортить все точки в самом начале и дальше использовать это. В реализации попроще, асимптотика та же.
}}
{{Лемма
|about=
О занимаемой памяти
|statement=
K-d дерево требует <tex>O(n)</tex> памяти.
|proof=
Высота дерева, очевидно, логарифмическая, а листьев всего <tex>O(n)</tex>. Поэтому будет <tex>O(n)</tex> вершин, каждая занимает <tex>O(1)</tex> памяти.
}}
By the way, если считать <tex>k</tex> константой, то и для случая большей размерности эти оценки будут такими же (доказывается аналогично).
== Запрос ==
Пусть нам поступил какой-то прямоугольник <tex>R</tex>. Нужно вернуть все точки, которые в нём лежат. Будем это делать рекурсивно, получая на вход корень дерева и сам прямоугольник <tex>R</tex>. Обозначим область, соответствующую вершине <tex>v</tex>, как <tex>region(v)</tex>. Она будет прямоугольником, одна или более границ которого могут быть на бесконечности. <tex>region(v)</tex> можно явно хранить в узлах, записав при построении, или же считать при рекурсивном спуске. Если корень дерева является листом, то просто проверяем одну точку и при необходимости репортим её. Если нет, то смотрим пересекают ли регионы детей прямоугольник <tex>R</tex>. Если да, то запускаемся рекурсивно от такого ребёнка. При этом, если регион полностью содержится в <tex>R</tex>, то можно репортить сразу все точки из него. Тем самым мы, очевидно, вернём все нужные точки и только их. Чтобы стало совсем понятно, приведём псевдокод:
<code>
SearchKdTree(v, R)
//Input. The root of (a subtree of) a kd-tree, and a range R.
//Output. All points at leaves below v that lie in the range.
if v is a leaf
Report the point stored at v if it lies in R.
else
if region(v.left) is fully contained in R
ReportSubtree(v.left)
else if region(v.left) intersects R
SearchKdTree(v.left, R)
if region(v.right) is fully contained in R
ReportSubtree(v.right)
else if region(v.right) intersects R
SearchKdTree(v.right, R)
</code>
Здесь <tex>ReportSubtree</tex> репортит все точки в поддереве.
By the way, точно так же можно перечислять точки в любом множестве, ведь нигде не используется, что <tex>R</tex> {{---}} прямоугольник.
{{Теорема
|about=
О времени на запрос
|statement=
Перечисление точек в прямоугольнике выполняется за <tex>O(\sqrt n + ans)</tex>, где <tex>ans</tex> {{---}} размер ответа.
|proof=
Сперва заметим, что все <tex>ReportSubtree</tex> суммарно выполняются за <tex>O(ans)</tex>. Поэтому достаточно доказать оценку для числа рекурсивных вызовов. А рекурсивные вызовы выполняются только для тех вершин, регионы которых пересекают <tex>R</tex>, но не содержатся в нём. Такие регионы обязательно пересекают хотя бы одну (axis-parallel) сторону заданного прямоугольника. Оценим количество регионов, которые могут пересекаться произвольной вертикальной прямой. Для горизонтальной прямой это будет аналогично.
Обозначим максимально возможное количество регионов, пересекаемых какой-либо вертикальной прямой, в дереве для <tex>n</tex> точек, у которого первое разбиение делается вертикальной прямой, как <tex>Q(n)</tex>. Рассмотрим произвольную вертикальную прямую <tex>l</tex>. Она будет пересекать регион корня и какого-то одного из его детей (например, левого). При этом ни один из регионов в другом (правом) поддереве пересекать она не может. Левая половина разбита ещё на 2 части горизонтальной прямой, в каждой из них примерно <tex>n / 4</tex> вершин, и они хранятся в поддереве, у которого первое разбиение делается вертикальной прямой. Это даёт нам следующее соотношение:
<tex>Q(n) = O(1)</tex> if <tex>n = 1</tex>.
<tex>Q(n) = 2 + 2 \cdot Q(n / 4)</tex>, otherwise.
Глубина дерева рекурсии равна <tex>\log_4 n = \frac{1}{2}\log_2 n</tex>
Следовательно, <tex>Q(n) = O(2^{\frac{1}{2}\log_2 n}) = O(\sqrt n)</tex> является решением. Принимая во внимание всё, что писалось выше, получаем требуемое.
}}
By the way, в общем случае время на запрос <tex>O(n^{1 - 1/k} + ans)</tex> из соотношения <tex>Q(n) = k + 2^{k - 1} \cdot Q(n / 2^k)</tex>.
== Ссылки ==
