| Operation | Genomsnitt | Värsta fall |
|---|
* amorterad: genomsnitt över en lång följd av operationer
Datastrukturvisualisering
En datastruktur är ett sätt att lagra data så att de frågor man ställer oftast går snabbt att besvara. Välj en av elva klassiska strukturer, från stacken till det rödsvarta trädet, skriv ett värde och tryck på en operation. Varje steg spelas upp på skärmen: vilken nod som jämförs, vilken länk som ändras, varför ett träd roterar eller ett värde stiger, med en mening som säger vad som händer. Rutorna räknar arbetet i varje operation och en tabell visar dess körtid. Välj en struktur, skriv ett värde och tryck på en operation. Varje operation spelas upp steg för steg: de markerade noderna visar vad som jämförs, flyttas eller ändras, och raden under bilden säger vad som händer och varför. Bakåt, Steg, Spela upp och Slut går igenom stegen igen. Fyll slumpmässigt och Rensa börjar om, och Ångra tar tillbaka en operation. Rutorna visar storleken, höjden på träd, arbetet i den senaste operationen (jämförelser, sonderingar eller följda föräldralänkar) och ett tal som är viktigt för strukturen; tabellen visar körtiden för varje operation.
Hur det fungerar
- Välj en struktur, till exempel ett binärt sökträd, en hashtabell eller en trie. Den börjar med slumpmässigt innehåll; Fyll slumpmässigt och Rensa börjar om.
- Skriv ett värde och tryck på en operation: push, ställ i kö, sätt in, ta bort, sök, en genomgång, union eller find. Stegen spelas upp av sig själva; Bakåt, Steg, Spela upp och Slut går igenom dem igen.
- Läs på raden under bilden vad varje steg gör, följ storleken, höjden och arbetet i den senaste operationen i rutorna och jämför körtiderna i tabellen.
Listor, stackar och köer
De enklaste strukturerna håller elementen på rad. En stack arbetar bara i ena änden, så det element som kom in sist kommer ut först, som en trave tallrikar; en kö lägger till baktill och tar ut framtill, som en kö vid en disk. Kön här ligger i en ringbuffert: fram- och bakänden går runt i en fast array och börjar om efter slutet, och när den är full kopieras elementen till en som är dubbelt så stor. En länkad lista binder ihop noder med pekare, så att sätta in vid huvudet kostar inget, men för att hitta svansen eller ett index måste man följa länkarna en i taget.
Träd, heapar, hashtabeller och mängder
Ett binärt sökträd håller mindre värden till vänster och större till höger, så en sökning halverar kandidaterna i varje steg, så länge trädet är buskigt. AVL- och rödsvarta träd ser till det med rotationer som du kan följa och som är uppkallade efter sitt fall. En heap håller bara det minsta eller största värdet överst, och mer än så behöver inte en prioritetskö. En hashtabell hoppar direkt till en hink som räknas ut från nyckeln och måste hantera krockar; en trie delar ordens prefix; union-find avgör på nästan konstant tid om två element hör till samma mängd.
Ofta ställda frågor
Vilken datastruktur ska jag använda?
Det beror på vilka frågor du ställer oftast. En stack eller en kö när elementen hanteras i den ordning de kommer eller tvärtom; en hashtabell för att slå upp en nyckel; ett balanserat sökträd som ett AVL- eller rödsvart träd när du också behöver nycklarna i ordning eller den närmaste nyckeln; en heap när du bara behöver det minsta eller största elementet; en trie för ord och prefix; union-find för att hålla reda på grupper som slås ihop.
Vad är skillnaden mellan ett AVL-träd och ett rödsvart träd?
Båda håller ett binärt sökträd grunt, så att varje sökning, insättning och borttagning tar tid proportionell mot log n. Ett AVL-träd är strängare balanserat, med höjderna på varje nods två sidor högst ett ifrån varandra, så uppslag går lite snabbare. Ett rödsvart träd tillåter mer spelrum och behöver färre rotationer när det ändras, och därför använder många standardbibliotek det för sina sorterade maps och sets.
Varför kan en hashtabell vara långsam i värsta fall?
Om många nycklar hamnar i samma hink måste ett uppslag kontrollera dem en i taget, precis som i en lista. En bra hashfunktion sprider nycklarna jämnt och tabellen växer innan den blir för full, så ett uppslag tar i genomsnitt konstant tid. Prova en tabellstorlek på 10 med tal som slutar på samma siffra, eller ord som är anagram av varandra, och se krockarna hopa sig.
Vad betyder talen bredvid AVL-noderna?
De är balansfaktorer: höjden på en nods vänstra delträd minus höjden på dess högra delträd. I ett AVL-träd måste varje balansfaktor vara −1, 0 eller +1. När en insättning eller borttagning gör en av dem till +2 eller −2 roterar trädet vid den noden; fallet (LL, RR, LR eller RL) säger åt vilket håll den extra höjden lutar och avgör om det behövs en eller två rotationer.
Skickas något till en server?
Nej. Varje operation körs i din webbläsare, och innehållet i varje struktur sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor