| Operation | Gennemsnit | Værste tilfælde |
|---|
* amortiseret: gennemsnit over en lang række operationer
Datastruktur-visualisering
En datastruktur er en måde at gemme data på, så de spørgsmål, man stiller oftest, hurtigt kan besvares. Vælg en af elleve klassiske strukturer, fra stakken til rød-sort-træet, skriv en værdi, og tryk på en operation. Hvert trin vises på skærmen: hvilken knude der sammenlignes, hvilken henvisning der ændres, hvorfor et træ roterer eller en værdi stiger, med en sætning, der siger, hvad der sker. Felterne tæller arbejdet i hver operation, og en tabel viser dens køretid. Vælg en struktur, skriv en værdi, og tryk på en operation. Hver operation afspilles trin for trin: de fremhævede knuder viser, hvad der sammenlignes, flyttes eller ændres, og linjen under billedet fortæller, hvad der sker og hvorfor. Tilbage, Trin, Afspil og Slut gennemgår trinene igen. Fyld tilfældigt og Ryd begynder forfra, og Fortryd tager en operation tilbage. Felterne viser størrelsen, højden af træer, arbejdet i den sidste operation (sammenligninger, prøvninger eller fulgte forælderhenvisninger) og ét tal, der betyder noget for strukturen; tabellen viser køretiden for hver operation.
Sådan virker det
- Vælg en struktur, fx et binært søgetræ, en hashtabel eller en trie. Den starter med tilfældigt indhold; Fyld tilfældigt og Ryd begynder forfra.
- Skriv en værdi, og tryk på en operation: push, stil i kø, indsæt, slet, søg, et gennemløb, union eller find. Trinene afspilles af sig selv; Tilbage, Trin, Afspil og Slut gennemgår dem igen.
- Læs i linjen under billedet, hvad hvert trin gør, følg størrelsen, højden og arbejdet i den sidste operation i felterne, og sammenlign køretiderne i tabellen.
Lister, stakke og køer
De enkleste strukturer holder elementerne på række. En stak arbejder kun i den ene ende, så det sidste element, der kom ind, kommer først ud, som en stak tallerkener; en kø tilføjer bagerst og tager ud forrest, som en kø ved en skranke. Køen her ligger i en ringbuffer: forenden og bagenden løber rundt i et fast array og starter forfra efter enden, og når den er fuld, kopieres elementerne over i en, der er dobbelt så stor. En kædet liste forbinder knuder med pointere, så indsættelse ved hovedet koster intet, men for at finde halen eller et indeks skal man følge henvisningerne én ad gangen.
Træer, hobe, hashtabeller og mængder
Et binært søgetræ holder mindre værdier til venstre og større til højre, så en søgning halverer kandidaterne i hvert trin, så længe træet forbliver busket. AVL- og rød-sort-træer sørger for det med rotationer, som man kan se, og som er opkaldt efter deres tilfælde. En hob holder kun den mindste eller største værdi øverst, og mere har en prioritetskø ikke brug for. En hashtabel springer direkte til en spand, der beregnes ud fra nøglen, og må håndtere kollisioner; en trie deler ordenes præfikser; union-find fortæller i næsten konstant tid, om to elementer hører til samme mængde.
Ofte stillede spørgsmål
Hvilken datastruktur skal jeg bruge?
Det afhænger af de spørgsmål, du stiller oftest. En stak eller en kø, når elementer behandles i den rækkefølge, de kommer, eller omvendt; en hashtabel til at slå en nøgle op; et balanceret søgetræ som et AVL- eller rød-sort-træ, når du også skal bruge nøglerne i rækkefølge eller den nærmeste nøgle; en hob, når du kun nogensinde skal bruge det mindste eller største element; en trie til ord og præfikser; union-find til at holde styr på grupper, der smelter sammen.
Hvad er forskellen på et AVL-træ og et rød-sort-træ?
Begge holder et binært søgetræ lavt, så hver søgning, indsættelse og sletning tager tid proportional med log n. Et AVL-træ er strengere balanceret, med højderne på hver knudes to sider højst én fra hinanden, så opslag er en smule hurtigere. Et rød-sort-træ tillader mere slør og kræver færre rotationer, når det ændres, og derfor bruger mange standardbiblioteker det til deres sorterede maps og sets.
Hvorfor kan en hashtabel være langsom i værste fald?
Hvis mange nøgler lander i samme spand, må et opslag kontrollere dem én ad gangen, præcis som i en liste. En god hashfunktion fordeler nøglerne jævnt, og tabellen vokser, før den bliver for fuld, så et opslag i gennemsnit tager konstant tid. Prøv en tabelstørrelse på 10 med tal, der ender på samme ciffer, eller ord, der er anagrammer af hinanden, og se kollisionerne hobe sig op.
Hvad betyder tallene ved AVL-knuderne?
Det er balancefaktorer: højden af en knudes venstre undertræ minus højden af dens højre undertræ. I et AVL-træ skal hver balancefaktor være −1, 0 eller +1. Når en indsættelse eller sletning gør en af dem til +2 eller −2, roterer træet ved den knude; tilfældet (LL, RR, LR eller RL) fortæller, hvilken vej den ekstra højde hælder, og afgør, om der skal én eller to rotationer til.
Sendes der noget til en server?
Nej. Hver operation kører i din browser, og indholdet af hver struktur gemmes i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor