Datastructuren uitgelegd
Elk programma bewaart gegevens ergens, en hoe het dat doet, bepaalt wat snel is en wat traag. Een lijst van een miljoen namen kun je naam voor naam doorzoeken, of zo ordenen dat twintig vergelijkingen elke naam vinden. Datastructuren zijn die ordeningen: een handvol ideeën, de meeste ouder dan de pc, die in elke database, elk besturingssysteem, elke browser en elk spel zitten.
Waar een datastructuur voor dient
Een datastructuur kies je op de vragen die ze moet beantwoorden. Het belregister van een telefoon wil het laatste gesprek eerst, de wachtrij van een printer de oudste opdracht eerst, een woordenboek de betekenis van één woord uit honderdduizend, een routeplanner het dichtstbijzijnde nog niet bezochte kruispunt. Elke structuur maakt sommige bewerkingen snel door andere op te geven, en de grote-O-notatie beschrijft die ruil: O(1) betekent dat de tijd niet groeit met het aantal elementen n, O(log n) dat een verdubbeling van n één stap extra kost, en O(n) dat de tijd evenredig met n groeit.
Stapels, wachtrijen en deques
Een stapel voegt toe en haalt weg aan dezelfde kant: laatst erin, eerst eruit. Geschiedenissen van ongedaan maken, de terugknop en de aanroepen van een draaiend programma zijn stapels. Een wachtrij voegt achteraan toe en haalt vooraan weg: eerst erin, eerst eruit, zoals toetsaanslagen of een afdrukwachtrij. Een deque kan beide aan beide kanten. Alle drie kosten constante tijd per bewerking. Een wachtrij staat vaak in een ringbuffer, een vaste array waarin voor- en achterkant na het einde weer rondlopen; als hij vol is, worden de elementen gekopieerd naar een array die twee keer zo groot is. Kopiëren kost O(n), maar gebeurt zo zelden dat elke bewerking gemiddeld toch O(1) kost, wat een geamortiseerde grens heet.
Gekoppelde lijsten
Een gekoppelde lijst bewaart elke waarde in een knoop met een pointer naar de volgende knoop. Invoegen of verwijderen buigt alleen een of twee pointers om, er hoeft niets te schuiven, maar je kunt niet naar de tiende knoop springen: je volgt de verwijzingen vanaf de kop. Een lijst die alleen zijn kop kent, bereikt de staart in O(n) stappen; echte lijsten houden meestal ook een staartpointer bij, en dubbel gekoppelde lijsten een pointer terug, zo worden een browsergeschiedenis of een LRU-cache gebouwd.
Binaire zoekbomen
Een binaire zoekboom houdt bij elke knoop kleinere waarden in de linkersubboom en grotere in de rechter. Een zoekactie vergelijkt en gaat naar links of rechts, en een in-order-doorloop leest de waarden gesorteerd. Een blad verwijderen is het gewoon weghalen, een knoop met één kind wordt door dat kind vervangen, en een knoop met twee kinderen door zijn in-order-opvolger, de kleinste waarde in zijn rechtersubboom. Dit alles kost tijd evenredig met de hoogte van de boom: ongeveer log n als de boom breed is, maar n als de waarden gesorteerd binnenkomen en de boom ontaardt in een lijst.
AVL- en rood-zwartbomen
Zelfbalancerende bomen herstellen hun vorm na elke wijziging. Een AVL-boom, in 1962 bedacht door Adelson-Velsky en Landis, houdt de hoogtes van de twee subbomen van elke knoop hooguit één uit elkaar; bereikt de balansfactor van een knoop ±2, dan herstellen één rotatie (de gevallen LL en RR) of twee (LR en RL) het evenwicht. Een rood-zwartboom kleurt zijn knopen zo dat de wortel zwart is, geen rode knoop een rood kind heeft en elk pad omlaag evenveel zwarte knopen passeert, waardoor het langste pad hooguit twee keer zo lang is als het kortste. Hij herstelt zich door opnieuw te kleuren en hooguit enkele rotaties, en het is de boom in Java's TreeMap, std::map in C++ en de Linux-scheduler.
Heaps en prioriteitswachtrijen
Een binaire heap is een complete binaire boom die zonder pointers in een array staat: de kinderen van positie i staan op 2i + 1 en 2i + 2. In een min-heap is elke ouder hooguit zo groot als zijn kinderen, dus de kleinste waarde staat altijd in de wortel. Een nieuwe waarde komt achteraan en stijgt langs grotere ouders omhoog; bij het eruit halen van de wortel gaat de laatste waarde naar boven en zakt weg. Beide kosten O(log n), en een hele array kan in O(n) een heap worden. Heaps drijven de prioriteitswachtrijen aan van Dijkstra's kortste paden, gebeurtenissimulaties en schedulers van besturingssystemen, en ze leveren heapsort op.
Hashtabellen
Een hashtabel maakt met een hashfunctie van een sleutel een array-index en gaat daar direct heen. Verschillende sleutels kunnen op dezelfde index uitkomen: een botsing. Ketenen houdt in elke bucket een kleine lijst bij; open adressering, zoals lineair proberen, probeert de volgende plaatsen tot er een vrij is en moet bij het verwijderen van een sleutel een grafsteen achterlaten, zodat latere zoekacties blijven proberen. Met een goede hashfunctie en een lage bezettingsgraad (sleutels per bucket), die je bewaakt door de tabel te laten groeien, kosten invoegen, zoeken en verwijderen gemiddeld O(1). Een zwakke functie, zoals het optellen van de tekencodes van een woord, stuurt anagrammen naar dezelfde bucket. Hashtabellen zitten achter Pythons dict, JavaScript-objecten en database-indexen.
Tries en union-find
Een trie of prefixboom slaat strings op met één teken per niveau, zodat woorden met hetzelfde begin een pad delen en een knoop aangeeft waar een woord eindigt. Een woord van lengte L vinden kost L stappen, hoeveel woorden er ook in staan, en alle woorden met een bepaald prefix zitten in één subboom, zo werken automatisch aanvullen en spellingcontrole. Union-find houdt elementen in disjuncte verzamelingen bij, elk een boom waarvan de wortel de verzameling benoemt. Find volgt de ouderverwijzingen tot de wortel; union hangt een wortel onder een andere. Met vereniging op rang en padcompressie kost een lange reeks bewerkingen per bewerking bijna constante tijd, de inverse Ackermannfunctie α(n), die voor elke realistische n hooguit 4 is. Het algoritme van Kruskal voor minimale opspannende bomen leunt erop.
Veelgestelde vragen
Wat is het verschil tussen een array en een gekoppelde lijst?
Een array houdt zijn elementen naast elkaar in het geheugen, dus elke positie is meteen bereikbaar, maar invoegen in het midden betekent alles erachter opschuiven. Een gekoppelde lijst kan overal invoegen door pointers te veranderen, maar een positie bereiken betekent vanaf de kop lopen. Arrays benutten ook de cache van de processor veel beter, en daarom zijn ze in de praktijk meestal sneller.
Wat betekent geamortiseerde tijd?
De gemiddelde kosten per bewerking over een lange reeks, ook al is één bewerking soms duur. Een ringbuffer die verdubbelt als hij vol is, kopieert af en toe alle n elementen, maar omdat de kopieën zeldzamer worden naarmate de buffer groeit, kosten n toevoegingen samen O(n), dus gemiddeld O(1) per stuk.
Is een heap hetzelfde als een binaire zoekboom?
Nee. Een binaire zoekboom zet elke linkersubboom vóór zijn knoop en elke rechtersubboom erna, dus hij kan alle waarden gesorteerd opsommen en elke waarde snel vinden. Een heap belooft alleen dat elke ouder vóór zijn kinderen komt, wat genoeg is om het minimum of maximum meteen te vinden, maar niet om een willekeurige waarde te zoeken.
Hoe weet union-find of twee elementen verbonden zijn?
Het volgt vanaf elk element de ouderverwijzingen tot de wortel van zijn boom. Komen beide bij dezelfde wortel uit, dan zitten ze in dezelfde verzameling. Padcompressie laat daarna elke knoop op de weg rechtstreeks naar de wortel wijzen, zodat de volgende vraag over hen één stap kost.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Open de datastructuur-visualisatie