Ternární vyhledávací strom - Ternary search tree

tento článek vyžaduje pozornost odborníka na toto téma. Specifický problém je: „Chybějící popis několika, ale v tomto případě velmi důležitých operací. Chybějící pseudokód všech operací (včetně právě zmíněných chybějících). Pseudokód výrazně zlepšuje pochopení operací. Chybějící přísná matematická analýza složitosti běhu.“ . Při umisťování této značky zvažte přidružení této žádosti s WikiProject. (Září 2016)

v počítačová věda, a ternární vyhledávací strom je typ trie (někdy nazývané a strom předpony) kde jsou uzly uspořádány podobným způsobem jako a binární vyhledávací strom, ale až se třemi dětmi, spíše než s limitem binárního stromu na dvě. Stejně jako ostatní stromy s předponami lze i ternární vyhledávací strom použít jako asociativní mapa struktura se schopností přírůstkové vyhledávání řetězců. Ternární vyhledávací stromy jsou však za cenu rychlosti efektivnější ve srovnání se standardními předponovými stromy. Mezi běžné aplikace pro ternární vyhledávací stromy patří kontrola pravopisu a automatické dokončování.

Popis

Každý uzel ternárního vyhledávacího stromu ukládá jeden charakter, an objekt (nebo a ukazatel na objekt v závislosti na implementaci) a odkazy na jeho tři podřízené názvy stejné dítě, lo dítě a ahoj kluku, které lze také označit jako prostřední dítě), nižší (dítě) a vyšší (dítě).^[1] Uzel může mít také ukazatel na nadřazený uzel a také indikátor, zda uzel označuje konec slova nebo ne.^[2] The lo dítě ukazatel musí ukazovat na uzel, jehož znaková hodnota je menší než aktuální uzel. The ahoj kluku ukazatel musí ukazovat na uzel, jehož charakter je větší než aktuální uzel.^[1] The stejné dítě ukazuje na další znak ve slově. Na následujícím obrázku je zobrazen ternární vyhledávací strom s řetězci „roztomilý“, „pohár“, „zavináč“, „jako“, „on“, „nás“ a „i“:

          c / |  a u h | | |  t t e u / / | / | s p e i s

Stejně jako u jiných struktur trie dat, každý uzel v ternárním vyhledávacím stromu představuje předponu uložených řetězců. Všechny řetězce ve středním podstromu uzlu začínají touto předponou.

Operace

Vložení

^{[potřebný příklad ]}

Vkládání hodnoty do ternárního vyhledávání lze definovat rekurzivně stejně, jako jsou definována vyhledávání. Tato rekurzivní metoda se nepřetržitě volá na uzlech stromu, kterému je dán klíč, který se postupně zkracuje ořezáváním znaků z přední strany klíče. Pokud tato metoda dosáhne uzlu, který nebyl vytvořen, vytvoří uzel a přiřadí mu hodnotu znaku prvního znaku v klíči. Ať už je nový uzel vytvořen nebo ne, metoda zkontroluje, zda je první znak v řetězci větší než nebo menší než hodnota znaku v uzlu a provede rekurzivní volání na příslušném uzlu jako v operaci vyhledávání. Pokud je však první znak klíče roven hodnotě uzlu, pak je procedura vložení volána u stejného dítěte a první znak klíče je odříznut.^[1] Jako binární vyhledávací stromy a další datové struktury, ternární vyhledávací stromy se mohou zdegenerovat v závislosti na pořadí klíčů.^{[3][self-publikoval zdroj? ]} Vkládání klíčů v abecedním pořadí je jedním ze způsobů, jak dosáhnout toho nejhoršího zdegenerovaného stromu.^[1] Vložení klíčů v náhodném pořadí často vytváří vyvážený strom.^[1]

Vyhledávání

^{[potřebný příklad ]}

K vyhledání konkrétního uzlu nebo dat přidružených k uzlu je potřeba řetězcový klíč. Procedura vyhledávání začíná kontrolou kořenového uzlu stromu a určením, která z následujících podmínek nastala. Pokud je první znak řetězce menší než znak v kořenovém uzlu, lze volat rekurzivní vyhledávání na stromě, jehož kořen je lo aktuálního kořene. Podobně, pokud je první znak větší než aktuální uzel ve stromu, lze provést rekurzivní volání do stromu, jehož kořen je hi kid aktuálního uzlu.^[1]Jako poslední případ, pokud se první znak řetězce rovná znaku aktuálního uzlu, vrátí funkce uzel, pokud v klíči nejsou žádné další znaky. Pokud je v klíči více znaků, musí být první znak klíče odstraněn a je provedeno rekurzivní volání s ohledem na stejný uzel dítěte a upravený klíč.^[1]To lze také zapsat nerekurzivním způsobem pomocí ukazatele na aktuální uzel a ukazatele na aktuální znak klíče.^[1]

Pseudo kód

funkce hledat (řetězec dotaz) je    -li je prázdný(dotaz) pak        vrátit se falešný uzel p : = kořen. int idx := 0    zatímco p není null dělat        -li dotaz[idx] < p.plékář pak            p := p.vlevo, odjet jiný -li dotaz[idx] > p.plékář pak            p := p.že jo; jiný            -li idx = last_valid_index (dotaz) pak                vrátit se skutečný idx := idx + 1            p := p.centrum vrátit se Nepravdivé

Vymazání

^{[je zapotřebí objasnění ][potřebný příklad ]}

Traverz

^{[je zapotřebí objasnění ][potřebný příklad ]}

Hledání částečné shody

^{[je zapotřebí objasnění ][potřebný příklad ]}

Hledání blízkého souseda

^{[je zapotřebí objasnění ][potřebný příklad ]}

Provozní doba

Doba provozu ternárních vyhledávacích stromů se významně liší podle vstupu. Ternární vyhledávací stromy běží nejlépe, když jich je několik podobné řetězce, zvláště když ty struny sdílet společnou předponu. Alternativně jsou ternární vyhledávací stromy účinné při ukládání velkého počtu relativně krátké struny (například slova v a slovník ).^[1]Doby provozu pro ternární vyhledávací stromy jsou podobné binární vyhledávací stromy, v tom, že obvykle běží v logaritmickém čase, ale mohou běžet v lineárním čase v degenerovaném (nejhorším) případě.

Časová složitost pro operace ternárního vyhledávacího stromu:^[1]

Srovnání s jinými datovými strukturami

Zkouší

I když je pomalejší než ostatní prefixové stromy, ternární vyhledávací stromy mohou být díky své prostorové efektivnosti vhodnější pro větší soubory dat.^[1]

Hašovací mapy

Hashtables lze také použít namísto ternárních vyhledávacích stromů pro mapování řetězců na hodnoty. Hašovací mapy však také často využívají více paměti než ternární vyhledávací stromy (ale ne tolik jako pokusy). Navíc hash mapy jsou obvykle pomalejší při hlášení řetězce, který není ve stejné datové struktuře, protože musí porovnávat celý řetězec, nikoli jen prvních pár znaků. Existují důkazy, které ukazují, že ternární vyhledávací stromy běží rychleji než hash mapy.^[1] Navíc hash mapy neumožňují mnoho využití ternárních vyhledávacích stromů, například vyhledávání blízkých sousedů.

DAFSA (deterministický acyklický automat konečného stavu )

Pokud je zapotřebí pouze ukládání slovníkových slov (tj. Ukládání pomocných informací ke každému slovu se nevyžaduje), minimální deterministický acyklický automat konečného stavu (DAFSA) by používal méně prostoru než trie nebo ternární vyhledávací strom. Je to proto, že DAFSA může komprimovat identické větve z trie, které odpovídají stejným příponám (nebo částem) různých uložených slov.

Použití

Ternární vyhledávací stromy lze použít k řešení mnoha problémů, ve kterých musí být uloženo a načteno velké množství řetězců v libovolném pořadí. Níže uvádíme některé z nejběžnějších nebo nejužitečnějších z nich:

• Kdykoli trie lze použít, ale dává se přednost méně náročné na paměťovou strukturu.^[1]
• Rychlá a prostorově úsporná datová struktura pro mapování řetězce k jiným datům.^[3]
• Provádět automatické dokončování.^{[2][self-publikoval zdroj? ]}
• Jako Kontrola pravopisu.^[4]
• Hledání blízkého souseda (z nichž kontrola pravopisu je zvláštní případ).^[1]
• Jako databáze zvláště když je žádoucí indexování podle několika neklíčových polí.^[4]
• Namísto a hash tabulka.^[4]

Viz také

• Třícestný radix quicksort
• Trie
• Binární vyhledávací strom
• Hashtable

Reference

externí odkazy

• Ternární vyhledávací stromy stránka s příspěvky (Jon Bentley a Robert Sedgewick) o ternárních vyhledávacích stromech a algoritmech pro „třídění a hledání řetězců“
• Ternární pokusy o hledání - video od Roberta Sedgewicka
• TST.java.html Implementace TST v Javě od Robert Sedgewick a Kevin Wayne