Grootte
Vergelijkingen

Bewerking Gemiddeld Slechtste geval

Meer informatie over datastructuren

Datastructuur-visualisatie

Een datastructuur is een manier om gegevens zo op te slaan dat de vragen die je het vaakst stelt snel beantwoord zijn. Kies een van elf klassieke structuren, van de stapel tot de rood-zwartboom, typ een waarde en druk op een bewerking. Elke stap speelt zich af op het scherm: welke knoop wordt vergeleken, welke verwijzing verandert, waarom een boom roteert of een waarde stijgt, met een zin die benoemt wat er gebeurt. De tegels tellen het werk van elke bewerking, en een tabel geeft de looptijd. Kies een structuur, typ een waarde en druk op een bewerking. Elke bewerking speelt stap voor stap af: de gemarkeerde knopen tonen wat er wordt vergeleken, verplaatst of veranderd, en de regel onder het plaatje zegt wat er gebeurt en waarom. Met Terug, Stap, Afspelen en Einde loop je de stappen opnieuw door. Willekeurig vullen en Wissen beginnen opnieuw, en Ongedaan maken draait een bewerking terug. De tegels tonen de grootte, de hoogte van bomen, het werk van de laatste bewerking (vergelijkingen, probes of gevolgde ouderverwijzingen) en één getal dat voor de structuur telt; de tabel geeft de looptijd van elke bewerking.

Hoe het werkt

  1. Kies een structuur, zoals een binaire zoekboom, een hashtabel of een trie. Hij begint met willekeurige inhoud; Willekeurig vullen en Wissen beginnen opnieuw.
  2. Typ een waarde en druk op een bewerking: push, aansluiten, invoegen, verwijderen, zoeken, een doorloop, union of find. De stappen spelen vanzelf af; Terug, Stap, Afspelen en Einde lopen ze opnieuw door.
  3. Lees in de regel onder het plaatje wat elke stap doet, volg in de tegels de grootte, de hoogte en het werk van de laatste bewerking, en vergelijk de looptijden in de tabel.

Lijsten, stapels en wachtrijen

De eenvoudigste structuren houden elementen op een rij. Een stapel werkt maar aan één kant, dus wat er het laatst in ging, komt er het eerst uit, zoals bij een stapel borden; een wachtrij voegt achteraan toe en haalt vooraan weg, zoals een rij bij een loket. De wachtrij hier staat in een ringbuffer: voor- en achterkant schuiven rond een vaste array en beginnen na het einde weer vooraan, en als hij vol is, worden de elementen gekopieerd naar een buffer die twee keer zo groot is. Een gekoppelde lijst verbindt knopen met pointers, dus invoegen aan de kop kost niets, maar om de staart of een index te vinden, volg je de verwijzingen één voor één.

Bomen, heaps, hashtabellen en verzamelingen

Een binaire zoekboom houdt kleinere waarden links en grotere rechts, zodat een zoekactie de kandidaten bij elke stap halveert, zolang de boom breed blijft. AVL- en rood-zwartbomen zorgen daarvoor, met rotaties die je kunt bekijken en die naar hun geval zijn genoemd. Een heap houdt alleen de kleinste of grootste waarde bovenaan, meer heeft een prioriteitswachtrij niet nodig. Een hashtabel springt rechtstreeks naar een bucket die uit de sleutel wordt berekend en moet met botsingen omgaan; een trie deelt de prefixen van woorden; union-find zegt in vrijwel constante tijd of twee elementen tot dezelfde verzameling horen.

Veelgestelde vragen

Welke datastructuur moet ik gebruiken?

Dat hangt af van de vragen die je het vaakst stelt. Een stapel of een wachtrij als elementen worden afgehandeld in de volgorde waarin ze binnenkomen of juist andersom; een hashtabel om een sleutel op te zoeken; een gebalanceerde zoekboom zoals een AVL- of rood-zwartboom als je de sleutels ook gesorteerd nodig hebt of de dichtstbijzijnde sleutel; een heap als je alleen ooit het kleinste of grootste element nodig hebt; een trie voor woorden en prefixen; union-find om groepen bij te houden die samensmelten.

Wat is het verschil tussen een AVL-boom en een rood-zwartboom?

Beide houden een binaire zoekboom ondiep, zodat elke zoekactie, invoeging en verwijdering tijd kost die evenredig is met log n. Een AVL-boom is strenger in balans, met de hoogtes van de twee kanten van elke knoop hooguit één uit elkaar, dus zoeken gaat iets sneller. Een rood-zwartboom laat meer speling toe en heeft minder rotaties nodig bij een wijziging, en daarom gebruiken veel standaardbibliotheken hem voor hun gesorteerde maps en sets.

Waarom kan een hashtabel in het slechtste geval traag zijn?

Als veel sleutels in dezelfde bucket terechtkomen, moet een zoekactie ze één voor één nalopen, net als bij een lijst. Een goede hashfunctie verdeelt de sleutels gelijkmatig en de tabel groeit voordat hij te vol raakt, zodat een zoekactie gemiddeld constante tijd kost. Probeer een tabelgrootte van 10 met getallen die op hetzelfde cijfer eindigen, of woorden die anagrammen van elkaar zijn, en zie de botsingen zich opstapelen.

Wat betekenen de getallen naast de AVL-knopen?

Het zijn balansfactoren: de hoogte van de linkersubboom van een knoop min de hoogte van zijn rechtersubboom. In een AVL-boom moet elke balansfactor −1, 0 of +1 zijn. Als invoegen of verwijderen er een +2 of −2 maakt, roteert de boom bij die knoop; het geval (LL, RR, LR of RL) zegt naar welke kant de extra hoogte helt en beslist tussen één en twee rotaties.

Wordt er iets naar een server gestuurd?

Nee. Elke bewerking draait in je browser, en de inhoud van elke structuur wordt bewaard in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor