Rozsah strom - Range tree

Rozsah strom
Typ	strom
Vynalezeno	1979
Vynalezl	Jon Louis Bentley
Časová složitost v velká O notace
Algoritmus Průměrný Nejhorší případ Prostor ${displaystyle O (nlog ^ {d-1} n)}$ ${displaystyle O (nlog ^ {d-1} n)}$ Vyhledávání ${displaystyle O (log ^ {d} n + k)}$ ${displaystyle O (log ^ {d} n + k)}$

v počítačová věda, a rozsah strom je objednaný strom datová struktura držet seznam bodů. Umožňuje, aby byly všechny body v daném rozsahu hlášeno efektivně a obvykle se používá ve dvou nebo vyšších rozměrech. Range stromy byly zavedeny Jon Louis Bentley v roce 1979.^[1] Podobné datové struktury objevil Lueker nezávisle,^[2] Lee a Wong,^[3] a Willard.^[4]Strom rozsahu je alternativou k k-d strom. Ve srovnání s k-d stromy, rozsahové stromy nabízejí rychlejší časy dotazů (v Velká O notace ) ${displaystyle O (log ^ {d} n + k)}$ ale horší skladování ${displaystyle O (nlog ^ {d-1} n)}$, kde n je počet bodů uložených ve stromu, d je rozměr každého bodu a k je počet bodů hlášených daným dotazem.

Bernard Chazelle vylepšil to na čas dotazu ${displaystyle O (log ^ {d-1} n + k)}$ a prostorová složitost ${displaystyle Oleft (nleft ({frac {log n} {log log n}} ight) ^ {d-1} ight)}$.^[5][6]

Datová struktura

Příklad jednorozměrného stromu rozsahu. Každý uzel, který není listem, ukládá maximální hodnotu do svého levého podstromu.

Strom rozsahu na sadě 1rozměrných bodů je vyvážený binární vyhledávací strom v těchto bodech. Body uložené ve stromu jsou uloženy v listech stromu; každý vnitřní uzel ukládá největší hodnotu obsaženou v jeho levém podstromu. Strom rozsahu na množině bodů v d-dimensions je a rekurzivně definované víceúrovňový binární vyhledávací strom. Každá úroveň datové struktury je binární vyhledávací strom na jedné z d-dimensions.The first level is a binary search tree on the first of the d-souřadnice. Každý vrchol proti tohoto stromu obsahuje přidruženou strukturu, která je (d-1) -rozměrný strom rozsahu na posledním (d−1) - souřadnice bodů uložených v podstromu proti.

Operace

Konstrukce

Jednorozměrný strom rozsahu na sadě n points je binární vyhledávací strom, ve kterém lze vytvořit ${displaystyle O (nlog n)}$ čas. Stromy rozsahu ve vyšších dimenzích jsou konstruovány rekurzivně konstrukcí vyváženého binárního vyhledávacího stromu na první souřadnici bodů a poté pro každý vrchol proti v tomto stromu budování (d-1) -rozměrný strom rozsahu v bodech obsažených v podstromu proti. Konstrukce stromu rozsahu tímto způsobem by vyžadovala ${displaystyle O (nlog ^ {d} n)}$ čas.

Tuto konstrukční dobu lze u stromů s 2-dimenzionálním rozsahem zlepšit na ${displaystyle O (nlog n)}$.^[7]Nechat S být soubor n 2-rozměrné body. Li S obsahuje pouze jeden bod, vrací list obsahující tento bod. Jinak vytvořte přidruženou strukturu S, jednorozměrný strom rozsahu na y- souřadnice bodů v S. Nechat X_m být mediánem X- souřadnice bodů. Nechat S_L být množina bodů s X-coordinate less than or equal to X_m a nechte S_R být množina bodů s X-souřadnice větší než X_m. Rekurzivně konstrukt proti_L, dvourozměrný strom rozsahu S_L, a proti_R, dvourozměrný strom rozsahu S_R. Vytvořte vrchol proti s levým dítětem proti_L a pravé dítě proti_RPokud seřadíme body podle jejich y-coordinates at the start of the algorithm, and keep this ordering when splitting the points by their X-coordinate, we can construct the associated structures of each subtree in linear time. Snižuje to čas na konstrukci 2-dimenzionálního stromu rozsahu na ${displaystyle O (nlog n)}$, a také zkracuje čas na konstrukci a d-dimenzionální strom rozsahu do ${displaystyle O (nlog ^ {d-1} n)}$.

Rozsahové dotazy

Jednorozměrný dotaz na rozsah [X₁, X₂]. Budou hlášeny body uložené v podstromech šedě stínovaných. nalézt(X₁) a najít(X₂) budou hlášeny, pokud jsou uvnitř intervalu dotazu.

A rozsah dotazu na stromě rozsahu hlásí množinu bodů, které leží uvnitř daného intervalu. Chcete-li nahlásit body, které leží v intervalu [X₁, X₂], začneme hledáním X₁ a X₂. U nějakého vrcholu ve stromu vyhledávací cesty k X₁ a X₂ se rozcházejí. Nechat proti_rozdělit být posledním vrcholem, který mají tyto dvě cesty hledání společné. Pro každý vrchol proti ve vyhledávací cestě z proti_rozdělit na X₁, pokud je hodnota uložena na proti je větší než X₁, nahlásit každý bod v pravém podstromu proti. Li proti je list, uveďte hodnotu uloženou v proti pokud je uvnitř intervalu dotazu. Podobně hlášení všech bodů uložených v levých podstromech vrcholů s hodnotami menšími než X₂ podél vyhledávací cesty z proti_rozdělit na X₂a nahlásit list této cesty, pokud leží v intervalu dotazu.

Vzhledem k tomu, že rozsahový strom je vyvážený binární strom, vyhledávací cesty k X₁ a X₂ mít délku ${displaystyle O (log n)}$. Hlášení všech bodů uložených v podstromu vrcholu lze provádět v lineárním čase pomocí libovolného traversal strom algoritmus. Z toho vyplývá, že čas na provedení dotazu na rozsah je ${displaystyle O (log n + k)}$, kde k je počet bodů v intervalu dotazu.

Rozsah dotazů v d-rozměry jsou podobné. Místo hlášení všech bodů uložených v podstromech vyhledávacích cest proveďte (d-1) -rozměrový dotaz rozsahu na přidruženou strukturu každého podstromu. Nakonec bude proveden 1-rozměrný rozsahový dotaz a budou hlášeny správné body. Protože a d-dimenzionální dotaz se skládá z ${displaystyle O (log n)}$ (d-1) -dimenzionální dotazy na rozsah, z toho vyplývá, že čas potřebný k provedení a d-dimenzionální rozsah dotazu je ${displaystyle O (log ^ {d} n + k)}$, kde k je počet bodů v intervalu dotazu. To lze snížit na ${displaystyle O (log ^ {d-1} n + k)}$ pomocí varianty částečné kaskádování.^[2][4][7]

Viz také

• k-d strom
• Segmentový strom
• Hledání rozsahu

Reference

externí odkazy

• Rozsahové a segmentové stromy v CGAL, Knihovna algoritmů výpočetní geometrie.
• Přednáška 8: Range Trees Marc van Kreveld.
• Range stromy použitím PAM, paralelní rozšířená knihovna map.