Nederlands
Menu

Wat is Binaire zoekboom (binary search tree)?

Binaire boom waarin voor elke knoop alle waarden in de linkerdeelboom kleiner en alle waarden in de rechterdeelboom groter zijn dan de knoop. Zoeken, invoegen en verwijderen kosten tijd die evenredig is met de hoogte van de boom, en een in-orderdoorloop bezoekt de waarden in oplopende volgorde.

Japanse benaming: 二分探索木

“Binaire zoekboom (binary search tree)” komt voor in 4 oefenvragen uit 1 onderwerpen, bijv. Datastructuren en algoritmen.

Vakgebied: Datastructuren en algoritmen

Zoeken, invoegen en verwijderen

Een zoekactie begint bij de wortel en gaat naar het linkerkind als de gezochte waarde kleiner is dan de knoop, of naar het rechterkind als ze groter is, en herhaalt dat tot ze een overeenkomst vindt of er geen kinderen meer zijn. Invoegen zoekt eerst en hangt een nieuwe knoop op de plaats waar de zoekactie geen kinderen meer vond. Verwijderen haalt een knoop met nul of één kind weg en verbindt het kind opnieuw; een knoop met twee kinderen wordt vervangen door de kleinste waarde in zijn rechterdeelboom (of de grootste in zijn linkerdeelboom), en die knoop wordt in plaats daarvan verwijderd. Elke bewerking kost tijd die evenredig is met het aantal niveaus van de wortel tot een blad (de hoogte van de boom).

Scheve bomen en zelfbalancerende bomen

Een binaire zoekboom met n knopen heeft een hoogte van ongeveer log₂ n als hij gebalanceerd is, maar waarden invoegen in gesorteerde volgorde, zoals 1, 2, 3, …, levert één keten op die naar één kant groeit, met hoogte n−1. Zoeken kost dan O(n), net als bij een gelinkte lijst. AVL-bomen en rood-zwartbomen zijn zelfbalancerende binaire zoekbomen die hun vorm bij elke invoeging en verwijdering aanpassen met bewerkingen die rotaties heten, en zo de hoogte op O(log n) houden; ze worden gebruikt voor de geordende dictionary's en sets van veel programmeertalen.

Doorloopvolgorden

Manieren om elke knoop van een boom te bezoeken zijn pre-order, dat elke knoop eerst bezoekt; in-order, dat de linkerdeelboom, de knoop en dan de rechterdeelboom bezoekt; post-order, dat eerst de kinderen bezoekt; en breedte-eerst (level-order), dat de boom niveau voor niveau bezoekt. Een in-orderdoorloop van een binaire zoekboom somt de waarden in oplopende volgorde op en levert zo een gesorteerde lijst. Een post-orderdoorloop van een expressieboom geeft omgekeerde Poolse notatie.

Nu oefenen: vragen over Binaire zoekboom (binary search tree)

Een binaire zoekboom wordt in in-order doorlopen (symmetrische volgorde: eerst de linkerdeelboom, dan de knoop zelf, dan de rechterdeelboom). In welke volgorde staan de waarden van de bezochte knopen? Neem aan dat alle waarden verschillend zijn.

  1. AIn oplopende volgorde (kleinste eerst)
  2. BIn de volgorde waarin ze zijn ingevoegd
  3. CIn volgorde van afstand tot de wortel (minst diep eerst)
Antwoord en toelichting tonen

Antwoord: A. In oplopende volgorde (kleinste eerst)

In een binaire zoekboom zijn voor elke knoop alle waarden in de linkerdeelboom kleiner dan de knoop en alle waarden in de rechterdeelboom groter. Wie eerst de linkerdeelboom, dan de knoop en dan de rechterdeelboom bezoekt, bezoekt de waarden dus van klein naar groot, en het resultaat is oplopend. Knopen bezoeken in volgorde van afstand tot de wortel is een breedte-eerst doorloop (level-order), die per niveau van links naar rechts gaat. De invoegvolgorde bepaalt de vorm van de boom, maar komt niet overeen met de volgorde van een doorloop.

De waarden 50, 30, 70, 20, 40, 60, 80 worden in deze volgorde ingevoegd in een lege binaire zoekboom. In welke volgorde worden de knopen bezocht als de boom in post-order wordt doorlopen (eerst de linkerdeelboom, dan de rechterdeelboom, dan de knoop zelf)?

  1. A50, 30, 20, 40, 70, 60, 80
  2. B20, 40, 30, 60, 80, 70, 50
  3. C20, 30, 40, 50, 60, 70, 80
Antwoord en toelichting tonen

Antwoord: B. 20, 40, 30, 60, 80, 70, 50

De wortel is 50; het linkerkind is 30 (met kinderen 20 en 40) en het rechterkind is 70 (met kinderen 60 en 80). Post-order bezoekt de linkerdeelboom als 20, 40, 30 en de rechterdeelboom als 60, 80, 70, en pas daarna de wortel 50. 50, 30, 20, 40, 70, 60, 80 is het resultaat van pre-order, dat elke knoop als eerste bezoekt, en 20, 30, 40, … dat van in-order. Post-order wordt gebruikt als kinderen eerst moeten worden verwerkt, bijvoorbeeld bij het verwijderen van een boom of bij het maken van postfixnotatie uit een expressieboom.

Veelgestelde vragen

Wat is het verschil tussen een binaire zoekboom en een heap?

Een binaire zoekboom volgt de regel „kleiner links, groter rechts”, dus hij kan elke waarde zoeken en waarden op volgorde opsommen. Een binaire heap volgt alleen de regel „een ouder is groter (of kleiner) dan zijn kinderen”, dus hij kan snel het maximum (of minimum) verwijderen, maar is niet geschikt om willekeurige waarden te zoeken.

Wanneer gebruik je een binaire zoekboom en wanneer een B-boom?

In het geheugen worden zelfbalancerende binaire zoekbomen gebruikt; voor opslag die in blokken wordt gelezen, zoals schijven en SSD's, worden B-bomen (B+-bomen) gebruikt, die de boom laag houden door veel sleutels in elke knoop te zetten.

“Binaire zoekboom (binary search tree)” in de toelichting

Vragen met “Binaire zoekboom (binary search tree)” (4)

  1. Een binaire zoekboom wordt in in-order doorlopen (symmetrische volgorde: eerst de linkerdeelboom, dan de knoop zelf, dan de rechterdeelboom). In welke volgorde staan de waarden van de bezochte knopen? Neem aan dat alle waarden verschillend zijn.
  2. De waarden 50, 30, 70, 20, 40, 60, 80 worden in deze volgorde ingevoegd in een lege binaire zoekboom. In welke volgorde worden de knopen bezocht als de boom in post-order wordt doorlopen (eerst de linkerdeelboom, dan de rechterdeelboom, dan de knoop zelf)?
  3. De waarden 1, 2, 3, …, 1000 worden in deze volgorde ingevoegd in een lege binaire zoekboom (zonder herbalancering). Met hoeveel knopen wordt, vanaf de wortel, vergeleken voordat 1000 wordt gevonden?
  4. Wat is de belangrijkste reden dat voor indexen in databases en bestandssystemen vaak B-bomen (inclusief B+-bomen) worden gebruikt in plaats van binaire zoekbomen?

Verwante termen

Gelinkte lijst (linked list) Algoritme van Dijkstra Binair zoeken (binary search) Binaire heap (binary heap) Breedte-eerst zoeken (breadth-first search) Diepte-eerst zoeken (depth-first search) Dynamisch programmeren (dynamic programming) Gretig algoritme (greedy algorithm) Hashtabel (hash table) Recursie

Naar de woordenlijst