172
правки
Изменения
→Сбалансированное дерево поиска
Переходим к двумерному случаю. Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.
Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве. Рассмотрим на примере:
[[Файл:ortog_search_tree.png|600px]]<br>
В такой структуре данных поиск точек в заданном прямоугольнике <tex>(x_{min}, x_{max}) \times (y_{min}, y_{max})</tex> будет выглядеть следующим образом:
