Изменения
→Запрос
{{ptreadyready}}
== Определение и построение ==
[[Файл:Kd-tree.png | 500px | thumb | Пример]]
'''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике.
<code>
<tex>T(n) = O(n) + 2 \cdot T(n / 2)</tex>, otherwise.
Также стоит отметить, что можно и не искать медиану за линейное время, а просто посортить все точки в самом начале и дальше использовать это. В реализации попроще, асимптотика та же.
Высота дерева, очевидно, логарифмическая, а листьев всего <tex>O(n)</tex>. Поэтому будет <tex>O(n)</tex> вершин, каждая занимает <tex>O(1)</tex> памяти.
}}
By the way, если считать <tex>k</tex> константой, то и для случая большей размерности эти оценки будут такими же (доказывается аналогично).
== Запрос ==
== Ссылки ==