Datastructuren en algoritmen

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?

A10
B500
C1000

Antwoord en toelichting tonen

Antwoord: C. 1000

Bij invoegen in oplopende volgorde wordt elke nieuwe waarde het rechterkind van het vorige maximum, zodat de boom één keten wordt die alleen naar rechts groeit (hoogte 999). 1000 staat helemaal onderaan en wordt dus vergeleken met alle 1000 knopen 1, 2, …, 1000; dat is O(n), net als een gelinkte lijst vanaf het begin doorlopen. Een gebalanceerde boom zou maar ongeveer log₂ 1000 ≈ 10 niveaus hebben. Een zelfbalancerende binaire zoekboom, zoals een AVL-boom of een rood-zwartboom, die zijn vorm bij elke invoeging en verwijdering aanpast, houdt het slechtste geval daarom op O(log n).

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

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?
Wat is een geschikte manier om een ijle graaf, een graaf met weinig kanten in verhouding tot het aantal knopen, in het geheugen op te slaan, zoals een wegennet met ongeveer 1 miljoen knopen en 3 miljoen kanten?
In een graaf waarvan de kanten geen gewicht hebben, wil je vanaf een startknoop het kleinste aantal kanten naar elke andere knoop bepalen. Welke combinatie van zoekmethode en datastructuur is geschikt?
In een ongerichte graaf zijn de buren van elke knoop A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Diepte-eerst zoeken met recursie begint bij knoop A. De buren worden in de vermelde volgorde onderzocht, en zodra een nog niet bezochte knoop wordt gevonden, gaat de zoekactie daarheen. In welke volgorde worden de knopen bezocht?
In een ongerichte graaf zijn de gewichten (afstanden) van de kanten S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 en A−T: 6. Welk kortste pad van S naar T vindt het algoritme van Dijkstra, en wat is de lengte ervan?