Strom prioritního vyhledávání - Priority search tree

v počítačová věda, a strom prioritního vyhledávání je stromová datová struktura pro ukládání bodů ve dvou rozměrech. To bylo původně představeno Edward McCreight.[1] Je to efektivně rozšíření prioritní fronta za účelem zlepšení doby vyhledávání z O (n) také(s + log n) čas, kde n je počet bodů ve stromu a s je počet bodů vrácených vyhledáváním.

Popis

Strom pro vyhledávání priorit se používá k uložení sady 2-dimenzionálních bodů seřazených podle priority a podle hodnoty klíče. Toho je dosaženo vytvořením hybridu a prioritní fronta a a binární vyhledávací strom.

Výsledkem je strom, kde každý uzel představuje bod v původní datové sadě. Bod obsažený v uzlu je bod s nejnižší prioritou. Kromě toho každý uzel také obsahuje klíčovou hodnotu používanou k rozdělení zbývajících bodů (obvykle medián klíčů, s výjimkou bodu uzlu) na levý a pravý podstrom. Body jsou rozděleny porovnáním jejich hodnot klíče s klíčem uzlu, delegováním těch s nižšími klávesami do levého podstromu a těch, které jsou přísně větší do pravého podstromu.[2]

Operace

Konstrukce

Konstrukce stromu vyžaduje O (n log n) čas a O (n) prostor. Níže je navržen konstrukční algoritmus:

strom konstrukt_strom(data) {  -li délka(data) > 1 {      uzel_bod = find_point_with_minimum_priority(data) // Vyberte bod s nejnižší prioritou        redukované údaje = remove_point_from_data(data, uzel_bod)    uzel_key = vypočítat_medián(redukované_data) // výpočet mediánu, s výjimkou vybraného bodu        // Rozdělte body     left_data = []    right_data = []           pro (směřovat v redukované_data) {      -li směřovat.klíč <= uzel_key         left_data.připojit(směřovat)      jiný         right_data.připojit(směřovat)    }    left_subtree = konstrukt_strom(left_data)    pravý podstrom = konstrukt_strom(right_data)    vrátit se uzel // Uzel obsahující uzel_klíč, uzel_bod a levý a pravý podstrom  } jiný -li délka(data) == 1 {     vrátit se list uzel // Uzel listu obsahující jediný zbývající datový bod  } jiný -li délka(data) == 0 {    vrátit se nula // Tento uzel je prázdný  }}

Hledání uzemněného rozsahu

Strom vyhledávání priorit lze efektivně dotazovat na klíč v uzavřeném intervalu a na maximální hodnotu priority. To znamená, že lze určit interval [min_key, max_key] a další interval [-∞, max_priority] a vrátit body v něm obsažené. To je znázorněno v následujícím pseudokódu:

bodů vyhledávací_strom(strom, min_key, max_key, max_priority) {  vykořenit = get_root_node(strom)   výsledek = []    -li get_child_count(vykořenit) > 0 {          -li get_point_priority(vykořenit) > max_priority      vrátit se nula // V této větvi nebude nic zajímavého. Vrátit se    -li min_key <= get_point_key(vykořenit) <= max_key // je kořenový bod zajímavý?       výsledek.připojit(get_point(uzel))       -li min_key < get_node_key(vykořenit) // Měli bychom hledat levý podstrom?        výsledek.připojit(vyhledávací_strom(vykořenit.left_sub_tree, min_key, max_key, max_priority))    -li get_node_key(vykořenit) < max_key // Měli bychom hledat pravý podstrom?        výsledek.připojit(vyhledávací_strom(vykořenit.right_sub_tree, min_key, max_key, max_priority))          vrátit se výsledek  jiný { // Toto je uzel listu    -li get_point_priority(vykořenit) < max_priority a min_key <= get_point_key(vykořenit) <= max_key // je listový bod zájmu?       výsledek.připojit(get_point(uzel))  }}

Viz také

Reference

  1. ^ McCreight, Edward (květen 1985). ""Stromy prioritního vyhledávání"". SIAM Journal on Scientific Computing. 14 (2): 257–276. doi:10.1137/0214021.
  2. ^ Lee, D.T (2005). Příručka datových struktur a aplikací. London: Chapman & Hall / CRC. s. 18–21. ISBN  1-58488-435-5.