170
правок
Изменения
Нет описания правки
{{ptready}}
== Определение и построение ==
[[Файл:Kd-tree.png | 500px | thumb | Пример]]
'''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике.
''Примечание: в книжке описывается двумерный вариант, и на лекциях, кажется, только он был, поэтому далее считается, что <tex>k = 2</tex>. Обобщение на большую размерность достаточно просто додумать при необходимости. Местами будет упомянут и случай <tex>k > 2</tex>.''
Строится это дерево следующим образом: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее (раз считаем, что <tex>k = 2</tex>, то на следующем уровне вновь будем разбивать вертикальными прямыми).
''Замечание: проблемы могут возникнуть, если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим {{---}} не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbers, то есть сравнивая ещё и по другой (другим) координате. Не думаю, что об этом нужно много писать.''
<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> памяти.
}}
== Запрос ==
Ы
== Ссылки ==
