В информатике дерево приоритетного поиска — это древовидная структура данных для хранения точек в двух измерениях. Первоначально он был представлен Эдвардом М. МакКрайтом . [1] По сути, это расширение приоритетной очереди с целью улучшения времени поиска с O( n ) до O( s + log n ), где n — количество точек в дереве, а s — число точек, возвращаемых поиском.
Дерево приоритетного поиска используется для хранения набора двумерных точек, упорядоченных по приоритету и значению ключа. Это достигается путем создания гибрида очереди с приоритетами и двоичного дерева поиска .
В результате получается дерево, в котором каждый узел представляет точку исходного набора данных. Точка, содержащаяся в узле, имеет наименьший приоритет. Кроме того, каждый узел также содержит значение ключа, используемое для разделения оставшихся точек (обычно медианы ключей, исключая точку узла) на левое и правое поддерево. Точки делятся путем сравнения их ключевых значений с ключом узла, делегируя точки с меньшими ключами в левое поддерево, а те, которые строго больше, в правое поддерево. [2]
Построение дерева требует времени O( n log n ) и пространства O( n ). Алгоритм построения предложен ниже:
Дерево приоритетного поиска может быть эффективно запрошено для ключа в закрытом интервале и для максимального значения приоритета. То есть можно указать интервал [ min_key , max_key ] и другой интервал [- ∞ , max_priority ] и вернуть точки, содержащиеся в нем. Это проиллюстрировано в следующем псевдокоде: