Thread View: be.comp.programming
2 messages
2 total messages
Started by Ivan Van den Bossche
Mon, 15 Dec 2003 20:15
Red-Black tree
Author: Ivan Van den Bossche
Date: Mon, 15 Dec 2003 20:15
Date: Mon, 15 Dec 2003 20:15
8 lines
1133 bytes
1133 bytes
Hi, 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? Alvast bedankt Ivan
Re: Red-Black tree
Author: Pieter Philippaerts
Date: Tue, 16 Dec 2003 00:53
Date: Tue, 16 Dec 2003 00:53
29 lines
2603 bytes
2603 bytes
"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
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads