Prioritní vyhledávací strom

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

V tomto článku byl použit překlad textu z článku Priority search tree na anglické Wikipedii.