222
правки
Изменения
м
Нет описания правки
'''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике.
Строится это дерево следующим образом: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее (раз считаембудем считать, что <tex>k = 2</tex>(случай бОльших размерностей обрабатывается аналогично), то поэтому на следующем уровне вновь будем разбивать вертикальными прямыми).
''Замечание: проблемы могут возникнуть, если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим {{---}} не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbers, то есть сравнивая ещё и по другой (другим) координате.''
Реализовывать построение можно рекурсивно с помощью функции <tex>BuildKdTree(P, Depth)</tex>, принимающей множество точек и глубину. В зависимости от остатка при делении на размерность (рассмотрим при <tex> k = 2 </tex>, в таком случае от чётности размерности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод:
<code>
