Ternärt sökträd
| Ternärt sökträd (TST) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Typ | träd | ||||||||||||
| Tidskomplexitet i stor O-notation | |||||||||||||
| |||||||||||||
Inom datavetenskap är ett ternärt sökträd en typ av försök (kallas ibland ett prefixträd ) där noder är ordnade på ett sätt som liknar ett binärt sökträd , men med upp till tre barn snarare än det binära trädets gräns på två. Liksom andra prefixträd kan ett ternärt sökträd användas som en associativ kartstruktur med möjlighet till inkrementell strängsökning . Däremot är ternära sökträd mer utrymmeseffektiva jämfört med standardprefixträd, till priset av hastighet. Vanliga applikationer för ternära sökträd inkluderar stavningskontroll och automatisk komplettering .
Beskrivning
Varje nod i ett ternärt sökträd lagrar ett enstaka tecken , ett objekt (eller en pekare till ett objekt beroende på implementering) och pekare till dess tre barn som konventionellt kallas equal kid , lo kid och hi kid , som också kan refereras till som respektive mitten (barn) , lägre (barn) och högre (barn) . En nod kan också ha en pekare till sin överordnade nod såväl som en indikator på huruvida noden markerar slutet på ett ord eller inte. Lo kid- pekaren måste peka på en nod vars teckenvärde är mindre än den aktuella noden . Hi kid- pekaren måste peka på en nod vars karaktär är större än den aktuella noden . Den lika ungen pekar på nästa tecken i ordet. Bilden nedan visar ett ternärt sökträd med strängarna "söt","kopp","at","som","han","oss" och "i":
c / | \ åh | | | \ tteu / / | / | speis
Som med andra försöksdatastrukturer representerar varje nod i ett ternärt sökträd ett prefix för de lagrade strängarna. Alla strängar i det mellersta underträdet av en nod börjar med det prefixet.
Operationer
Införande
Att infoga ett värde i en ternär sökning kan definieras rekursivt eller iterativt mycket som uppslagningar definieras. Denna rekursiva metod anropas ständigt på noder i trädet med en nyckel som blir allt kortare genom att beskära tecken från framsidan av nyckeln. Om den här metoden når en nod som inte har skapats, skapar den noden och tilldelar den teckenvärdet för det första tecknet i nyckeln. Oavsett om en ny nod skapas eller inte, kontrollerar metoden om det första tecknet i strängen är större än eller mindre än teckenvärdet i noden och gör ett rekursivt anrop på lämplig nod som i uppslagsoperationen. Om emellertid nyckelns första tecken är lika med nodens värde, anropas insättningsproceduren på lika barn och nyckelns första tecken beskärs bort. Liksom binära sökträd och andra datastrukturer kan ternära sökträd bli degenererade beroende på nycklarnas ordning. [ självpublicerad källa? ] Att infoga nycklar i alfabetisk ordning är ett sätt att uppnå det värsta möjliga degenererade trädet. Att sätta in nycklarna i slumpmässig ordning ger ofta ett välbalanserat träd.
0
funktionsinsättning ( strängnyckel ) är nod p := rot //initialiserad för att vara lika om root är noll nod sist := rot int idx : = medan p inte är null gör //recurse på korrekt underträd om nyckel [ idx ] < sid . splitchar sedan sist := p p := p . vänster annars om tangent [ idx ] > p . splitchar sedan sist := p p := p . right else : //-tangenten finns redan i vårt träd om idx == längd ( nyckel ) returnerar sedan //trim-tecken från vår nyckel idx := idx + 1 sista := p p := p . mid p := node () //lägg till p som ett underordnat av den sista icke-nullnoden (eller roten om root är null) om root == null sedan roten := p annat om sist . splitchar < nyckel [ idx ] sedan sist . höger := p annat om sist . splitchar > nyckel [ idx ] sedan sist . vänster := p annat sist . mitten := p p . splitchar := nyckel [ idx ] idx := idx + 1 // Infoga resten av nyckel medan idx < length ( key ) do p . mid := nod () p . mitten . splitchar := nyckel [ idx ] idx += 1
Sök
För att slå upp en viss nod eller data som är associerade med en nod, behövs en strängnyckel. En uppslagsprocedur börjar med att kontrollera trädets rotnod och fastställa vilket av följande tillstånd som har inträffat. Om det första tecknet i strängen är mindre än tecknet i rotnoden, kan en rekursiv sökning anropas på trädet vars rot är lo kid för den aktuella roten. På liknande sätt, om det första tecknet är större än den aktuella noden i trädet, kan ett rekursivt anrop göras till trädet vars rot är hi kid för den aktuella noden. Som ett sista fall, om det första tecknet i strängen är lika med tecknet i den aktuella noden, returnerar funktionen noden om det inte finns fler tecken i nyckeln. Om det finns fler tecken i nyckeln måste det första tecknet i nyckeln tas bort och ett rekursivt anrop görs givet den lika barnnoden och den modifierade nyckeln. Detta kan också skrivas på ett icke-rekursivt sätt genom att använda en pekare till den aktuella noden och en pekare till tangentens aktuella tecken.
Pseudokod
0
funktionssökning ( strängfråga ) är om is_empty ( fråga ) returnerar sedan falsk nod p : = rot int idx : = medan p inte är null gör om fråga [ idx ] < p . splitchar sedan p := p . left else if query [ idx ] > p . splitchar sedan p := p . rätt ; annars om idx = längd ( fråga ) returnerar sann idx := idx + 1 p : = p . mitten returnerar falskt
Radering
Raderingsoperationen består av att söka efter en nyckelsträng i sökträdet och hitta en nod, kallad firstMid i nedanstående pseudokod, så att sökvägen från mitten av firstMid till slutet av sökvägen för nyckelsträngen inte har någon kvar eller rätt barn. Detta skulle representera ett unikt suffix i det ternära trädet som motsvarar nyckelsträngen. Om det inte finns någon sådan sökväg betyder det att nyckelsträngen antingen är helt innesluten som ett prefix till en annan sträng eller inte finns i sökträdet. Många implementeringar använder sig av ett strängslutstecken för att säkerställa att endast det senare fallet inträffar. Sökvägen raderas sedan från firstMid.mid till slutet av sökvägen. I fallet att firstMid är roten måste nyckelsträngen ha varit den sista strängen i trädet, och därmed sätts roten till null efter raderingen.
0
funktionen delete ( strängnyckel ) är om is_empty ( nyckel ) returnera nod p : = rot int idx : = nod firstMid := null medan p inte är null gör om nyckel [ idx ] < p . splitchar sedan firstMid := null p := p . vänster annars om tangent [ idx ] > p . splitchar sedan firstMid := null p := p . right else firstMid := p medan p inte är null och nyckel [ idx ] == p . splitchar till idx := idx + 1 p := p . mid if firstMid == null returnera sedan // Inget unikt strängsuffix // Vid denna punkt pekar firstMid på noden innan strängarnas unika suffix inträffar nod q := firstMid . mittnod p : = q firstMid . mid := null // koppla bort suffix från träd medan q inte är null gör //gå ner för suffixbanan och ta bort noder p := q q := q . mid delete ( p ) // ledigt minne associerat med nod p om firstMid == root sedan radera ( root ) //delete hela trädroten : = null
Traversering
[ förtydligande behövs ] [ exempel behövs ]
Sökning med partiell matchning
[ förtydligande behövs ] [ exempel behövs ]
Nära granne letar
[ förtydligande behövs ] [ exempel behövs ]
Körtid
Körtiden för ternära sökträd varierar avsevärt med inmatningen. Ternära sökträd fungerar bäst när de ges flera liknande strängar , särskilt när dessa strängar har ett gemensamt prefix . Alternativt är ternära sökträd effektiva när du lagrar ett stort antal relativt korta strängar (som ord i en ordbok ). Körtider för ternära sökträd liknar binära sökträd genom att de vanligtvis körs i logaritmisk tid, men kan köras i linjär tid i det degenererade (värsta) fallet. Vidare måste storleken på strängarna också hållas i åtanke när man överväger körtid. Till exempel, i sökvägen för en sträng med längden k , kommer det att finnas k genomgångar nedåt mitten av barnen i trädet, såväl som ett logaritmiskt antal genomgångar nedåt vänster och höger barn i trädet. I ett ternärt sökträd på ett litet antal mycket stora strängar kan alltså längderna på strängarna dominera körtiden.
Tidskomplexitet för operationer i ternära sökträd:
| Genomsnittlig körtid | I värsta fall körtid | |
|---|---|---|
| Slå upp | O (log n + k ) | O ( n + k ) |
| Införande | O (log n + k ) | O ( n + k ) |
| Radera | O (log n + k ) | O ( n + k ) |
Jämförelse med andra datastrukturer
Försöker
Även om de är långsammare än andra prefixträd , kan ternära sökträd vara bättre lämpade för större datamängder på grund av deras utrymmeseffektivitet.
Hash-kartor
Hashtabeller kan också användas i stället för ternära sökträd för att mappa strängar till värden. Men hash-kartor använder ofta mer minne än ternära sökträd (men inte lika mycket som försök). Dessutom är hashkartor vanligtvis långsammare när det gäller att rapportera en sträng som inte finns i samma datastruktur, eftersom den måste jämföra hela strängen snarare än bara de första tecknen. Det finns några bevis som visar att ternära sökträd kör snabbare än hashkartor. Dessutom tillåter inte hash-kartor många av användningarna av ternära sökträd, som sökningar nära grannar .
DAFSA ( deterministisk acyklisk finita tillståndsautomat )
Om lagring av ordboksord är allt som krävs (dvs. lagring av hjälpinformation till varje ord krävs inte), skulle en minimal deterministisk acyklisk finita tillståndsautomat (DAFSA) använda mindre utrymme än ett försök eller ett ternärt sökträd. Detta beror på att en DAFSA kan komprimera identiska grenar från försöket som motsvarar samma suffix (eller delar) av olika ord som lagras.
Används
Ternära sökträd kan användas för att lösa många problem där ett stort antal strängar måste lagras och hämtas i en godtycklig ordning. Några av de vanligaste eller mest användbara av dessa är nedan:
- När som helst ett försök kan användas men en mindre minneskrävande struktur är att föredra.
- En snabb och utrymmesbesparande datastruktur för att mappa strängar till andra data.
- För att implementera automatisk komplettering . [ självpublicerad källa? ]
- Som en stavningskontroll .
- Nära grannesökning (varav stavningskontroll är ett specialfall).
- Som databas är särskilt önskvärt när indexering av flera icke-nyckelfält är önskvärd.
- I stället för en hashtabell .
Se även
externa länkar
- med ternära sökträd med artiklar (av Jon Bentley och Robert Sedgewick) om ternära sökträd och algoritmer för "sortering och sökning av strängar"
- Ternary Search Tries – en video av Robert Sedgewick
- TST.java.html Implementering i Java av en TST av Robert Sedgewick och Kevin Wayne