🚀 go-pugleaf

"Ivan Van den Bossche" <ivan.van.den.bossche@pandora.be> wrote in message
> Is er iemand die weet of er een algoritme bestaat dat nog sneller is dan
het
> Red-Black tree algorithm om snel een waarde op te zoeken in een
> boomstructuur?

Als je een data structuur wil om zo snel mogelijk opzoekingen te doen, dan
moet je een perfect gebalanceerde binaire boom nemen; die heeft namelijk een
opzoek snelheid van log(n) waar n het aantal bladeren is in de boom [terwijl
rood/zwart in het slechtste geval een opzoek snelheid van 2*log(n+1) heeft].
Het probleem met perfect gebalanceerde bomen is dat het veel processortijd
vraagt om ze te updaten; het toevoegen van ��n blad kan namelijk een
verandering in de ganse boom veroorzaken. Het voordeel van rood-zwart bomen
is dat het toevoegen en verwijderen van entries over het algemeen veel
efficienter gaat.

Je moet je dus afvragen met welk type van probleem je te maken hebt. Als je
een hele boel statische data hebt waar nooit een entry bijkomt of weg gaat,
gebruik dan een binaire boom [en bereken de rangschikking van de elementen
in de boom op voorhand].
Als je data hebt waar vaak elementen bijkomen en weg gaan, blijf dan bij je
rood-zwart boom.

Een alternatief voor een rood-zwart boom kan een AVL boom. Ik ben
ondertussen vergeten wat het verschil tussen de twee is en welke de beste
is, maar je kan er ongetwijfeld heel wat online over vinden.

Mvg,
Pieter Philippaerts