Cesko.wiki Prioritní vyhledávací strom
Author
Albert FloresPrioritní vyhledávací strom je datová struktura používaná v informatice pro uchovávání a vyhledávání dat. Je to stromová struktura, ve které je každý uzel ohodnocen prioritou a procházení probíhá podle těchto priorit. Prioritní vyhledávací strom je obvykle implementován jako binární strom, kde každý uzel má dva syny - levého a pravého potomka. Podle ohodnocení priorit se rozhoduje, do kterého syna se při procházení stromu bude pokračovat. Tento strom se často používá ve vyhledávacích algoritmech, jako například prioritní fronta, kde se prvky řadí podle priority. Prioritní vyhledávací strom se také používá v databázích a operačních systémech pro rychlý přístup a vyhledávání dat.
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
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