Datastrukturer forklaret

Ethvert program gemmer data et sted, og hvordan det gør det, afgør, hvad der er hurtigt, og hvad der er langsomt. En liste med en million navne kan gennemsøges navn for navn eller ordnes, så tyve sammenligninger finder et hvilket som helst navn. Datastrukturer er den slags ordninger: en håndfuld idéer, de fleste ældre end pc'en, som findes i enhver database, ethvert styresystem, enhver browser og ethvert spil.

Et binært søgetræ med rød-sort-farvning, en stak af kasser, en række hashspande med en kæde af kolliderende nøgler og pile, der forbinder knuderne i en liste
Et binært søgetræ med rød-sort-farvning, en stak af kasser, en række hashspande med en kæde af kolliderende nøgler og pile, der forbinder knuderne i en liste

Hvad en datastruktur skal bruges til

En datastruktur vælges efter de spørgsmål, den skal besvare. En telefons opkaldsliste skal have det seneste opkald først, en printers job det ældste først, en ordbog betydningen af ét ord blandt hundrede tusind, en ruteplanlægger det nærmeste ubesøgte vejkryds. Hver struktur gør nogle operationer hurtige ved at opgive andre, og store O-notation beskriver byttehandlen: O(1) betyder, at tiden ikke vokser med antallet af elementer n, O(log n), at en fordobling af n koster ét trin mere, og O(n), at tiden vokser proportionalt med n.

Stakke, køer og deques

En stak tilføjer og fjerner i samme ende: sidst ind, først ud. Fortrydhistorikker, tilbageknappen og kaldene i et kørende program er stakke. En kø tilføjer bagerst og fjerner forrest: først ind, først ud, som tastetryk eller en udskriftskø. En deque tillader begge dele i begge ender. Alle tre tager konstant tid pr. operation. En kø ligger ofte i en ringbuffer, et fast array, hvor forende og bagende løber rundt efter den sidste plads; når den er fuld, kopieres elementerne over i et array, der er dobbelt så stort. Kopieringen koster O(n), men sker så sjældent, at hver operation i gennemsnit stadig koster O(1), hvad man kalder en amortiseret grænse.

Kædede lister

En kædet liste gemmer hver værdi i en knude med en pointer til den næste knude. Indsættelse eller sletning bøjer kun en eller to pointere om, intet skal flyttes, men man kan ikke springe til den tiende knude: man følger henvisningerne fra hovedet. En liste, der kun kender sit hoved, når halen på O(n) trin; rigtige lister har som regel også en halepointer, og dobbeltkædede lister en pointer tilbage, og sådan bygges en browserhistorik eller en LRU-cache.

Binære søgetræer

Et binært søgetræ holder ved hver knude mindre værdier i det venstre undertræ og større i det højre. En søgning sammenligner og går til venstre eller højre, og et in-order-gennemløb læser værdierne sorteret. At slette et blad er bare at fjerne det, en knude med ét barn erstattes af dette barn, og en knude med to børn af sin in-order-efterfølger, den mindste værdi i dens højre undertræ. Alt dette tager tid proportional med træets højde: omkring log n, når træet er busket, men n, når værdierne kommer i sorteret rækkefølge, og træet udarter til en liste.

AVL- og rød-sort-træer

Selvbalancerende træer reparerer deres form efter hver ændring. Et AVL-træ, opfundet af Adelson-Velsky og Landis i 1962, holder højderne af hver knudes to undertræer højst én fra hinanden; når en knudes balancefaktor når ±2, genopretter én rotation (tilfældene LL og RR) eller to (LR og RL) balancen. Et rød-sort-træ farver sine knuder, så roden er sort, ingen rød knude har et rødt barn, og hver vej nedad passerer lige mange sorte knuder, hvilket holder den længste vej højst dobbelt så lang som den korteste. Det reparerer sig selv ved omfarvning og højst nogle få rotationer, og det er træet i Javas TreeMap, C++'s std::map og Linux' skemalægger.

Hobe og prioritetskøer

En binær hob er et komplet binært træ gemt i et array uden pointere: børnene af position i ligger på 2i + 1 og 2i + 2. I en min-hob er hver forælder højst lige så stor som sine børn, så den mindste værdi står altid i roden. En ny værdi kommer bagerst og stiger forbi større forældre; når roden tages ud, flyttes den sidste værdi op og synker. Begge dele koster O(log n), og et helt array kan gøres til en hob på O(n). Hobe driver prioritetskøerne i Dijkstras korteste veje, hændelsessimuleringer og styresystemers skemalæggere, og de giver hobsortering.

Hashtabeller

En hashtabel gør en nøgle til et arrayindeks med en hashfunktion og går direkte derhen. Forskellige nøgler kan lande på samme indeks: en kollision. Kædning holder en lille liste i hver spand; åben adressering, som lineær prøvning, prøver de næste pladser, indtil den finder en ledig, og må efterlade en gravsten, når en nøgle slettes, så senere søgninger bliver ved med at prøve. Med en god hashfunktion og en lav fyldningsgrad (nøgler pr. spand), som holdes nede ved at lade tabellen vokse, koster indsættelse, søgning og sletning i gennemsnit O(1). En dårlig funktion, som at lægge tegnkoderne i et ord sammen, sender anagrammer i samme spand. Hashtabeller ligger bag Pythons dict, JavaScript-objekter og databaseindekser.

Tries og union-find

En trie, eller et præfikstræ, gemmer strenge med ét tegn pr. niveau, så ord med samme begyndelse deler en vej, og en knude markerer, hvor et ord slutter. At finde et ord med længden L tager L trin, uanset hvor mange ord der er gemt, og alle ord med et givet præfiks ligger i ét undertræ, sådan virker autofuldførelse og stavekontrol. Union-find holder elementer i disjunkte mængder, hver et træ, hvis rod navngiver mængden. Find følger forælderhenvisningerne op til roden; union hænger en rod ind under en anden. Med forening efter rang og stikomprimering koster en lang række operationer næsten konstant tid pr. operation, den inverse Ackermann-funktion α(n), som er højst 4 for ethvert realistisk n. Kruskals algoritme for minimale udspændende træer bygger på den.

Ofte stillede spørgsmål

Hvad er forskellen på et array og en kædet liste?

Et array holder sine elementer side om side i hukommelsen, så enhver position kan nås med det samme, men indsættelse i midten betyder, at alt bagved skal flyttes. En kædet liste kan indsætte hvor som helst ved at ændre pointere, men at nå en position betyder at gå fra hovedet. Arrays udnytter også processorens cache langt bedre, og derfor er de i praksis som regel hurtigere.

Hvad betyder amortiseret tid?

Den gennemsnitlige omkostning pr. operation over en lang række, selv om en enkelt operation af og til er dyr. En ringbuffer, der fordobles, når den er fuld, kopierer en gang imellem alle n elementer, men fordi kopierne bliver sjældnere, jo større bufferen bliver, koster n tilføjelser i alt O(n), altså O(1) stykket i gennemsnit.

Er en hob det samme som et binært søgetræ?

Nej. Et binært søgetræ placerer hvert venstre undertræ før sin knude og hvert højre undertræ efter, så det kan liste alle værdier i rækkefølge og finde enhver værdi hurtigt. En hob lover kun, at hver forælder kommer før sine børn, hvilket er nok til straks at finde minimum eller maksimum, men ikke til at søge efter en vilkårlig værdi.

Hvordan ved union-find, om to elementer er forbundet?

Den følger forælderhenvisningerne fra hvert element op til roden af dets træ. Hvis begge når samme rod, er de i samme mængde. Stikomprimering får derefter hver knude på vejen til at pege direkte på roden, så det næste spørgsmål om dem kun tager ét trin.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Åbn datastruktur-visualiseringen