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