228
правок
Изменения
→Структура данных
*''Поисковая структура''
Поисковая структура(в дальнейшем <tex> D</tex>) предсталяет представляет из себя ацикличный ациклический граф с одним корнем и каждому трапецоиду в структре структуре соответствует один лист.
У каждого узла есль есть два ребенка и при этом узел может быть двух типов.
[[Файл:Trapezoidmapsearchstructureshagal.jpg|650px|thumb|right|навигация в трапецоидной карте]]
*Первый тип узла - точка, соответствующая концу отрезка.
*Второй тип узла - отрезок.
Во время запроса мы двигаемся по графу от его корня до момента, когда окажемся в листе, это и будет означать что точка находится внутри трапецоида.
