Prioritní vyhledávací strom je datová struktura z oboru teoretické informatiky. Jedná se o strukturu k ukládání bodů dvourozměrných, tedy položek, která kromě hlavní hodnoty mají přiřazenou ještě „prioritu““. Samotná struktura je křížencem binárního vyhledávacího stromu a prioritní fronty.
V každém uzlu stromu je uložen jednak ten z bodů jím začínajícího podstromu, který má nejmenší prioritu, jednak hlavní hodnota (nejlépe medián všech hodnot podstromu), která podřazené body rozděluje do levého (menší nebo rovné hodnoty) a pravého (větší hodnoty) podstromu.
Vytvoření stromu tree construct_tree(data) { if length(data) > 1 {
node_point = find_point_with_minimum_priority(data) // nalezení bodu s nejnižší prioritou
reduced_data = remove_point_from_data(data, node_point) // jeho odstranění ze vstupu node_key = calculate_median(reduced_data) // výpočet mediánu ze zbytku vstupních bodů
// rozdělení dat podle mediánu 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 // vrácení podstromu
} else if length(data) == 1 { return leaf node // zbývající bod je vracíme jako list } else if length(data) == 0 { return null // prázdný
Vyhledávání v intervalu Typickou úlohou v prioritním vyhledávacím stromě je nalezení bodů s omezenou nejvyšší prioritou a spadajících do patřičného intervalu hodnot.
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 // v tomto podstromu výsledek nenajdeme
if min_key <= get_point_key(root) <= max_key // je jedním z kandidátů hodnota přímo v kořeni podstromu? result.append(get_point(node))
if min_key < get_node_key(root) // má smysl prohledávat levý podstrom? result.append(search_tree(root.left_sub_tree, min_key, max_key, max_priority))
if get_node_key(root) < max_key // má smysl prohledávat pravý podstrom? result.append(search_tree(root.right_sub_tree, min_key, max_key, max_priority))
return result
else { // jsme v listu if get_point_priority(root) < max_priority and min_key <= get_point_key(root) <= max_key // je bod v listu jedním z kandidátů? result.append(get_point(node))
Reference
Kategorie:Stromy (datové struktury)