Datastrukturer förklarade

Varje program lagrar data någonstans, och hur det gör det avgör vad som går snabbt och vad som går långsamt. En lista med en miljon namn kan genomsökas namn för namn, eller ordnas så att tjugo jämförelser hittar vilket namn som helst. Datastrukturer är sådana ordningar: en handfull idéer, de flesta äldre än persondatorn, som finns i varje databas, operativsystem, webbläsare och spel.

Ett binärt sökträd med rödsvart färgning, en stapel lådor, en rad hashhinkar med en kedja av krockande nycklar och pilar som binder ihop noderna i en lista
Ett binärt sökträd med rödsvart färgning, en stapel lådor, en rad hashhinkar med en kedja av krockande nycklar och pilar som binder ihop noderna i en lista

Vad en datastruktur är till för

En datastruktur väljs efter de frågor den ska besvara. En telefons samtalslista vill ha det senaste samtalet först, en skrivares jobb det äldsta först, en ordbok betydelsen av ett ord bland hundra tusen, en ruttplanerare den närmaste obesökta korsningen. Varje struktur gör vissa operationer snabba genom att ge upp andra, och ordonotationen beskriver bytet: O(1) betyder att tiden inte växer med antalet element n, O(log n) att en fördubbling av n kostar ett steg till, och O(n) att tiden växer proportionellt mot n.

Stackar, köer och deques

En stack lägger till och tar bort i samma ände: sist in, först ut. Ångra-historik, bakåtknappen och anropen i ett körande program är stackar. En kö lägger till baktill och tar bort framtill: först in, först ut, som tangenttryck eller en utskriftskö. En deque tillåter båda i båda ändar. Alla tre tar konstant tid per operation. En kö ligger ofta i en ringbuffert, en fast array där fram- och bakänden går runt efter sista platsen; när den blir full kopieras elementen till en array som är dubbelt så stor. Kopieringen kostar O(n), men sker så sällan att varje operation ändå kostar O(1) i genomsnitt, vilket kallas en amorterad gräns.

Länkade listor

En länkad lista lagrar varje värde i en nod med en pekare till nästa nod. Insättning eller borttagning ändrar bara en eller två pekare, inget behöver flyttas, men man kan inte hoppa till den tionde noden: man följer länkarna från huvudet. En lista som bara känner sitt huvud når svansen på O(n) steg; riktiga listor har oftast också en svanspekare, och dubbellänkade listor en pekare bakåt, och så byggs en webbläsarhistorik eller en LRU-cache.

Binära sökträd

Ett binärt sökträd håller vid varje nod mindre värden i det vänstra delträdet och större i det högra. En sökning jämför och går åt vänster eller höger, och en in-order-genomgång läser värdena sorterat. Att ta bort ett löv är bara att ta bort det, en nod med ett barn ersätts av det barnet, och en nod med två barn av sin in-order-efterföljare, det minsta värdet i dess högra delträd. Allt detta tar tid proportionell mot trädets höjd: ungefär log n när trädet är buskigt, men n när värdena kommer i sorterad ordning och trädet urartar till en lista.

AVL- och rödsvarta träd

Självbalanserande träd lagar sin form efter varje ändring. Ett AVL-träd, uppfunnet av Adelson-Velskij och Landis 1962, håller höjderna på varje nods två delträd högst ett ifrån varandra; när en nods balansfaktor når ±2 återställer en rotation (fallen LL och RR) eller två (LR och RL) balansen. Ett rödsvart träd färgar sina noder så att roten är svart, ingen röd nod har ett rött barn och varje väg nedåt passerar lika många svarta noder, vilket håller den längsta vägen högst dubbelt så lång som den kortaste. Det lagar sig genom omfärgning och högst några få rotationer, och det är trädet i Javas TreeMap, C++:s std::map och Linux schemaläggare.

Heapar och prioritetsköer

En binär heap är ett komplett binärt träd som lagras i en array utan pekare: barnen till position i ligger på 2i + 1 och 2i + 2. I en min-heap är varje förälder högst lika stor som sina barn, så det minsta värdet står alltid i roten. Ett nytt värde läggs sist och stiger förbi större föräldrar; när roten tas ut flyttas det sista värdet upp och sjunker. Båda kostar O(log n), och en hel array kan göras till en heap på O(n). Heapar driver prioritetsköerna i Dijkstras kortaste vägar, händelsesimuleringar och operativsystemens schemaläggare, och de ger heapsort.

Hashtabeller

En hashtabell gör en nyckel till ett arrayindex med en hashfunktion och går direkt dit. Olika nycklar kan hamna på samma index: en krock. Kedjning håller en liten lista i varje hink; öppen adressering, som linjär sondering, provar nästa platser tills den hittar en ledig och måste lämna en gravsten när en nyckel tas bort, så att senare sökningar fortsätter sondera. Med en bra hashfunktion och en låg fyllnadsgrad (nycklar per hink), som hålls nere genom att tabellen växer, kostar insättning, sökning och borttagning i genomsnitt O(1). En dålig funktion, som att lägga ihop teckenkoderna i ett ord, skickar anagram till samma hink. Hashtabeller finns bakom Pythons dict, JavaScript-objekt och databasindex.

Tries och union-find

En trie, eller ett prefixträd, lagrar strängar med ett tecken per nivå, så att ord med samma början delar väg och en nod markerar var ett ord slutar. Att hitta ett ord med längden L tar L steg, oavsett hur många ord som är lagrade, och alla ord med ett visst prefix ligger i ett och samma delträd, så fungerar autokomplettering och stavningskontroll. Union-find håller element i disjunkta mängder, var och en ett träd vars rot namnger mängden. Find följer föräldralänkarna upp till roten; union hänger en rot under en annan. Med union efter rang och vägkomprimering kostar en lång följd av operationer nästan konstant tid per operation, den inversa Ackermannfunktionen α(n), som är högst 4 för varje realistiskt n. Kruskals algoritm för minsta uppspännande träd bygger på den.

Ofta ställda frågor

Vad är skillnaden mellan en array och en länkad lista?

En array håller sina element bredvid varandra i minnet, så varje position nås direkt, men att sätta in i mitten innebär att allt bakom måste flyttas. En länkad lista kan sätta in var som helst genom att ändra pekare, men att nå en position innebär att gå från huvudet. Arrayer utnyttjar dessutom processorns cache mycket bättre, och därför är de i praktiken oftast snabbare.

Vad betyder amorterad tid?

Den genomsnittliga kostnaden per operation över en lång följd, även om en enskild operation ibland är dyr. En ringbuffert som fördubblas när den är full kopierar då och då alla n element, men eftersom kopieringarna blir allt ovanligare ju större bufferten blir, kostar n tillägg totalt O(n), alltså O(1) styck i genomsnitt.

Är en heap samma sak som ett binärt sökträd?

Nej. Ett binärt sökträd placerar varje vänster delträd före sin nod och varje höger delträd efter, så det kan lista alla värden i ordning och snabbt hitta vilket värde som helst. En heap lovar bara att varje förälder kommer före sina barn, vilket räcker för att genast hitta minimum eller maximum, men inte för att söka efter ett godtyckligt värde.

Hur vet union-find om två element hänger ihop?

Den följer föräldralänkarna från varje element upp till roten i dess träd. Om båda når samma rot är de i samma mängd. Vägkomprimeringen får sedan varje nod på vägen att peka direkt på roten, så nästa fråga om dem tar ett enda steg.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Öppna datastrukturvisualiseringen