Дерево приоритетного поиска

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

Описание

Дерево приоритетного поиска используется для хранения набора двумерных точек, упорядоченных по приоритету и значению ключа. Это достигается путем создания гибрида очереди с приоритетами и двоичного дерева поиска .

В результате получается дерево, в котором каждый узел представляет точку исходного набора данных. Точка, содержащаяся в узле, имеет наименьший приоритет. Кроме того, каждый узел также содержит значение ключа, используемое для разделения оставшихся точек (обычно медианы ключей, исключая точку узла) на левое и правое поддерево. Точки делятся путем сравнения их ключевых значений с ключом узла, делегируя точки с меньшими ключами левому поддереву, а те, которые строго больше, - правому поддереву. ^[2]

Операции

Строительство

Построение дерева требует времени O( n log n ) и пространства O( n ). Алгоритм построения предложен ниже:

tree construct_tree(data) {
    if length(data) > 1 {
        node_point = find_point_with_minimum_priority(data) // Select the point with the lowest priority
        reduced_data = remove_point_from_data(data, node_point)
        node_key = calculate_median(reduced_data) // calculate median, excluding the selected point
        
        // Divide the points 
        left_data = []
        right_data = []        
     
        for (point in reduced_data) {
            if point.key <= node_key
                left_data.append(point)
            else
                right_data.append(point)
        }

        left_subtree = construct_tree(left_data)
        right_subtree = construct_tree(right_data)

        return node // Node containing the node_key, node_point and the left and right subtrees
    } else if length(data) == 1 {
         return leaf node // Leaf node containing the single remaining data point
    } else if length(data) == 0 {
        return null // This node is empty
    }
}

Поиск по обоснованному диапазону

Дерево поиска приоритетов может быть эффективно запрошено для ключа в закрытом интервале и для максимального значения приоритета. То есть можно указать интервал [ min_key , max_key ] и другой интервал [- $\infty$ , max_priority ] и вернуть точки, содержащиеся в нем. Это проиллюстрировано в следующем псевдокоде:

points search_tree(tree, min_key, max_key, max_priority) {
    root = get_root_node(tree) 
    result = []

    if get_child_count(root) > 0 {
        if get_point_priority(root) > max_priority
            return null // Nothing interesting will exist in this branch. Return

        if min_key <= get_point_key(root) <= max_key // is the root point one of interest?
            result.append(get_point(node))
     
        if min_key < get_node_key(root) // Should we search left subtree?
            result.append(search_tree(root.left_sub_tree, min_key, max_key, max_priority))

        if get_node_key(root) < max_key // Should we search right subtree?
            result.append(search_tree(root.right_sub_tree, min_key, max_key, max_priority))
            
        return result
    else { // This is a leaf node
        if get_point_priority(root) < max_priority and min_key <= get_point_key(root) <= max_key // is leaf point of interest?
            result.append(get_point(node))
    }
}

См. также

Дерево диапазона

Ссылки

^ МакКрайт, Эдвард (май 1985 г.). «Деревья приоритетного поиска». Журнал SIAM по научным вычислениям . 14 (2): 257–276. дои : 10.1137/0214021 .
^ Ли, DT (2005). Справочник по структурам данных и приложениям . Лондон: Чепмен и Холл/CRC. стр. 18–21. ISBN 1-58488-435-5 .

[1] МакКрайт, Эдвард (май 1985 г.). «Деревья приоритетного поиска». Журнал SIAM по научным вычислениям . 14 (2): 257–276. дои : 10.1137/0214021 .

[2] Ли, DT (2005). Справочник по структурам данных и приложениям . Лондон: Чепмен и Холл/CRC. стр. 18–21. ISBN 1-58488-435-5 .

[1]

[2]