Binaire zoekbomen
Een gebalanceerde binaire zoekboom met 1023 sleutels vindt elke sleutel in hoogstens 10 vergelijkingen; opgebouwd uit gesorteerde invoer kunnen dezelfde sleutels er 1023 vragen.
Binair zoeken ingebouwd in de vorm
Binair zoeken in een gesorteerde array vindt een sleutel in ongeveer log₂ n controles, maar invoegen verplaatst waarden. Een hashtabel voegt snel in maar vergeet de volgorde: hij kan niet eenvoudig de kleinste sleutel of de volgende na 40 geven. Een binaire zoekboom (BST) probeert beide te bieden. Hij bestaat uit knopen, zoals een gelinkte lijst, maar elke knoop heeft twee verwijzingen, left en right. De bovenste knoop is de wortel; een knoop zonder kinderen is een blad.
Eén regel maakt er een zoekboom van: bij elke knoop zijn alle sleutels in de linkerdeelboom kleiner en alle in de rechterdeelboom groter. Begin voor zoeken bij de wortel en vergelijk. Gelijk betekent gevonden. Kleiner betekent links, groter rechts. Elke vergelijking sluit een hele deelboom uit, zoals binair zoeken een halve lijst uitsluit. Zoeken naar 60 in de boom 50, 30, 70, 20, 40, 60, 80 vergelijkt met 50, dan 70 en dan 60: 3 vergelijkingen.
Invoegen volgt hetzelfde pad. Ga links of rechts tot de benodigde verwijzing leeg is en hang daar de nieuwe knoop. 45 invoegen vergelijkt met 50 (links), 30 (rechts) en 40 (rechts). 40 heeft geen rechterkind, dus 45 wordt dat. Een knoop verwijderen die geen blad is vraagt nog één idee: de MIT-notities verwisselen het item met de volgende of vorige sleutel op volgorde en verwijderen daar. In het lab tel je één vergelijking per knoop op het pad.
Sleep om te draaien. Scroll of knijp om te zoomen.
Hoogte bepaalt alles
Hoeveel vergelijkingen kan zoeken kosten? Hoogstens één per niveau, dus de kosten hangen af van de hoogte van de boom, het aantal kanten op het langste pad van wortel naar blad. De MIT-notities zeggen het zo: boombewerkingen hebben looptijd O(h). De boom 50, 30, 70, 20, 40, 60, 80 heeft hoogte 2, dus geen zoekactie heeft meer dan 3 vergelijkingen nodig. Een perfect gebalanceerde boom met 1023 knopen heeft hoogte 9 en vraagt er hoogstens 10.
Maar de vorm hangt af van de invoegvolgorde. Voeg 10, 20, 30, 40, 50, 60, 70 gesorteerd in en elke sleutel is groter dan alle voorgaande, dus elke nieuwe knoop komt rechts van de laatste. De boom wordt een keten met hoogte 6 en zoeken naar 70 kost 7 vergelijkingen: een gelinkte lijst met extra verwijzingen. Met 1023 gesorteerde sleutels kost het slechtste zoeken 1023 vergelijkingen in plaats van 10.
Gebalanceerde bomen herstellen dit door zichzelf na elke invoeging of verwijdering te vervormen. Het eerste schema was de AVL-boom van Georgy Adelson-Velsky en Evgenii Landis uit 1962, behandeld in MIT-college 7. Bij elke knoop houdt hij de hoogten van de deelbomen op een verschil van hoogstens 1 en herstelt afwijkingen met kleine lokale bewegingen, rotaties. Zo blijft de hoogte O(log n) en blijven zoeken, invoegen en verwijderen O(log n), ongeacht de aankomstvolgorde van de sleutels.
Sleutels gratis op volgorde
Een BST bewaart meer dan alleen lidmaatschap. Bezoek recursief eerst de linkerdeelboom, dan de knoop en dan de rechterdeelboom en de sleutels komen gesorteerd tevoorschijn. Met deze in-order-doorloop (MIT noemt het traversal order) beantwoordt een BST ‘kleinste sleutel’, ‘grootste sleutel’ en ‘volgende sleutel na 40’: de volgordebewerkingen van de Set-interface van MIT die een hashtabel niet snel kan doen.
| Wortel en blad | De wortel is de bovenste knoop; een blad heeft geen kinderen. |
| BST-eigenschap | Bij elke knoop zijn sleutels links kleiner en rechts groter. |
| Hoogte | Kanten op het langste wortel-bladpad. Zoeken kost hoogstens hoogte + 1 vergelijkingen. |
| AVL-boom | Een gebalanceerde BST (1962): deelboomhoogten verschillen hoogstens 1, hersteld door rotaties. |
| In-order-doorloop | Links, knoop, rechts: somt de sleutels gesorteerd op. |
- Welke uitspraak is de eigenschap van een binaire zoekboom?
- Elke knoop heeft precies twee kinderen
- Bij elke knoop zijn de sleutels in de linkerdeelboom kleiner en in de rechterdeelboom groter
- Sleutels worden in invoegvolgorde opgeslagen
- De wortel is de kleinste sleutel
- Boom opgebouwd uit 50, 30, 70, 20, 40, 60, 80. Hoeveel vergelijkingen kost zoeken naar 60?
- Dezelfde boom: hoeveel vergelijkingen kost zoeken naar de ontbrekende 45?
- Voeg 45 in die boom in. Waar komt die?
- Linkerkind van 50
- Rechterkind van 40
- Linkerkind van 60
- Rechterkind van 30
- Wat is de hoogte van de boom 50, 30, 70, 20, 40, 60, 80?
- Voeg 10, 20, 30, 40, 50, 60, 70 in die volgorde in. Hoeveel vergelijkingen kost zoeken naar 70?
- Een perfect gebalanceerde BST heeft 1023 knopen (hoogte 9). Hoeveel vergelijkingen kan zoeken maximaal kosten?
- Zet de sleutels van de boom 50, 30, 70, 20, 40 op de bezoekvolgorde van een in-order-doorloop.
- Wie stelde het eerste schema voor een gebalanceerde boom voor en wanneer?
- Adelson-Velsky en Landis, 1962
- Luhn, 1953
- Bauer en Samelson, 1957
- Knuth, 1998
- Welke vraag kan een BST snel beantwoorden maar een gewone hashtabel niet?
- Is 40 opgeslagen?
- Wat is de volgende sleutel na 40?
- Hoeveel buckets zijn er?
- Wat is 40 mod 7?
- In een BST gaan kleinere sleutels bij elke knoop naar links en grotere naar rechts.
- Zoeken en invoegen volgen één pad: hoogstens hoogte + 1 vergelijkingen.
- Gesorteerde invoer maakt een keten (7 sleutels, hoogte 6); gebalanceerde bomen zoals AVL (1962) houden de hoogte O(log n).
- Een in-order-doorloop somt de sleutels gesorteerd op.
Bronnen van deze cursus (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
Geraadpleegd: 2026-10-18