Algoritmen II
Deel 1: Gegevensstructuren II
Hoofdstuk 1: Efficiente Zoekbomen
1.1 Inleiding
De uitvoeringstijd van de meeste operaties op een binaire zoekboom met hoogte h is O(h)
maar kan in het slechtste geval O(n) zijn, in dat geval is het een soort van gelinkte lijst.
Methodes om de efficiëntie van zoekbomen te verbeteren:
● Elke operatie steeds efficiënt maken:
- AVL-bomen (de eerste evenwichtige bomen), bij deze bomen mag het
hoogteverschil tussen de 2 deelbomen van elke knoop nooit groter dan 1 zijn,
men slaat in elke knoop zijn hoogte op. Toevoegen of verwijderen kan het
evenwicht van de boom verstoren, zodat er structuurwijzigingen moeten
gebeuren om dat te herstellen, zonder de fundamentele eigenschap van een
zoekboom aan te raken
- 2-3 bomen, later uitgevonden, waarvan elke inwendige knoop 2 of drie
kinderen heeft, en alle bladeren dezelfde diepte hebben Bij toevoegen of
verwijderen wordt dit ideale evenwicht behouden door het aantal kinderen van
de knopen te manipuleren. Deze bomen zijn tevens de voorlopers van de
‘B-trees’ . Analoog definieert men ‘2-3-4-bomen’, waarop de operaties wat
eenvoudiger uitvallen, omdat de drie soorten knopen meer flexibiliteit bieden.
Knopen van verschillende soorten gebruiken, die bovendien van soort kunnen
veranderen, geeft praktische problemen bij implementatie
● Elke reeks operaties steeds efficiënt maken:
- Bij splay trees wordt de vorm van de boom meermaals aangepast, zodat die
nooit slecht blijft. Met als gevolg dat elke reeks opeenvolgende operaties
gegarandeerd efficënt is. Uitgemiddeld over de reeks is de performantie per
operatie goed, ook in het slechtste geval
● De gemiddelde efficiëntie onafhankelijk maken van de operatievolgorde
- Door gebruik van een random generator zorgen ‘randomized search trees’
ervoor dat de boom random blijft, waardoor de verwachtingswaarde van
operaties steed O(lg n) is. Eenvoudigste zoekboom uit deze familie is een
‘treap’
1
,1.2 Rood-Zwarte bomen
Rood Zwarte bomen
1.2.1 Definitie en eigenschappen
Definitie: Een binaire zoekboom die een 2-3-4 boom simuleert, waar men een 3 knoop
vervangt door 2 en een 4 knoop door 3 binaire knopen en 2 soorten ouder-kind verbindingen
definieert. De originele verbindingen van de 2-3-4 boom noemt men zwart, de nieuwe
verbindingen rood. De hoogte van de boom wordt laag gehouden door beperkingen op te
leggen aan de manier waarop knopen op elke (dalende) weg vanuit de wortel gekleurd
kunnen worden.
Dezelfde knoopstructuur wordt gebruikt als bij een gewone binaire zoekboom, met een
nieuw veld voor de kleur. Ontbrekende kinderen worden voorgesteld door nullwijzers, die we
conceptueel beschouwen als wijzers naar virtuele knopen van de boom, die geen gegevens
bevatten maar wel kleur.
Alle gewone knopen worden dus inwendig
Een rood-zwarte boom wordt dan gedefinieerd als een binaire zoekboom, waarbij
bovendien:
(1) Elke knoop rood of zwart gekleurd is.
(2) Elke virtuele knoop zwart is.
(3) Een rode knoop steeds twee zwarte kinderen heeft. (Zijn er steeds twee?)
2
,(4) Elke mogelijke (rechtstreekse) weg vanuit een knoop naar een virtuele knoop evenveel
zwarte knopen heeft. Dat aantal noemt men de zwarte hoogte van de knoop. Daarbij wordt
de knoop zelf niet meegerekend (zoals bij de gewone hoogte), de (zwarte) virtuele knoop
echter wel. Elke echte knoop heeft dus zwarte diepte minstens 1.
(5) De wortel zwart is. Deze vereiste is niet strikt noodzakelijk, maar wel handig. Een rode
wortel kan trouwens zonder problemen zwart gemaakt worden.
Eigenschappen
Uit deze definitie kunnen we afleiden dat een deelboom met wortel w en zwarte hoogte z
tenminste 2z −1 inwendige knopen bevat.
(extra uitleg hierover p7)
- De hoogte van een rood-zwarte boom met n knopen is dus steeds O(lg n).
- De boom is nu slechts bij benadering evenwichtig
Zoeken
Kleur speelt geen rol,de hoogte is steed O(lg n), zoeken is dus altijd efficiënt en O(lg n)
Toevoegen en verwijderen
Men moet een rood zwarte boom blijven behouden
Bij toevoegen kan me 2 manieren toepassen:
● Eerst toevoegen zonder op de kleur te letten, zoals bij een gewone , daarna herstelt
men de rood-zwarte boom. Te beginnen bij de nieuwe knoop, en desnoods tot bij de
wortel. We dalen dus af, om nadien langs dezelfde weg weer te stijgen. Ouderwijzers
of een stapel zijn hiervoor vereist. Men spreekt van een ‘bottom-up’ rood-zwarte
boom.
● Ofwel wordt de boom reeds aangepast langs de dalende zoekweg. Deze variant heet
natuurlijk ‘top-down’, en blijkt in de praktijk efficienter zowel in tijd als in plaats, omdat
ouderwijzers noch stapel nodig zijn.
Ook verwijderen kan bottom-up en top down gebeuren
- De structuurwijzigingen gebeuren met rotaties
Rotaties
Rotaties wijzigen de vorm van de boom, maar behouden de inorder volgorde van de
sleutels. De kleur van de knopen blijft onveranderd. Een rotatie is een lokale operatie,
waarbij twee inwendige knopen betrokken zijn. De rotatie ‘draait’ rond de
ouder-kindverbinding. Er zijn twee soorten, een rotatie naar links voor een rechterkind en
een naar rechts voor een linkerkind.
3
, Bij een rotatie naar rechts van een ouder p en zijn linkerkind l bijvoorbeeld wordt het
rechterkind van l (als het bestaat) het linkerkind van p, de ouder van p (als die bestaat) wordt
de ouder van l, en p wordt het rechterkind van l. Een rotatie is dus O(1).
Bottom-up rood zwarte bomen
Toevoegen
Een knoop wordt op de gewone manier toegevoegd.
Voor de kleur: Een zwarte knoop kan de zwarte hoogte ontregelen van veel knopen, en een
rode knoop mag enkel als de ouder zwart is.
- We kiezen voor een rode knoop en proberen de storing weg te werken door rotaties
en kleurwijzigingen
Scenario:
- Aangezien de ouder p van de nieuwe knoop c rood is, kan hij geen wortel zijn. Er is
dus een grootouder g die zwart is. We krijgen 6 mogelijke gevallen die we in 2
groepen van 3 kunnen delen adhv of p een linker of rechterkind van g is.
Onderstel dat p een linkerkind is van g:
- We kunnen de rode ouder p elimineren, door hem zwart te maken ofwel door hem
weg te nemen via een rotatie naar rechts. Er zijn 2 hoofgevallen afhankelijk van de
kleur van de broer van b van p:
● (1) De broer b van p is rood. De ligging van c ten opzichte van p maakt niet
uit. p kan zwart worden als er aan dezelfde kant een zwarte knoop rood
wordt. We maken de grootouder rood en moeten we nu ook de rode broer b
zwart maken.
Als de rood geworden g een zwarte ouder heeft, of geen ouder, dan is het
probleem opgelost. Is deze overgrootouder echter rood, dan zijn er opnieuw
twee opeenvolgende rode knopen. Het probleem werd dus opgeschoven, in
de richting van de wortel. Ofwel wordt het dan opgelost door een van de
andere gevallen, ofwel wordt het verder omhoog geschoven. In het slechtste
geval gaat dat opschuiven door tot bij de wortel, die dan nog enkel (opnieuw)
zwart moet gemaakt worden.
● De broer b van p is zwart. Nu nemen we de rode ouder p weg via een rotatie
naar rechts, die de rechterdeelboom een extra knoop bezorgt. Omdat p nu
bovenaan komt, en dus invloed heeft op twee wegen, neemt die best de
zwarte kleur van g over. De overgebrachte knoop g moet dan rood worden
om de zwarte hoogte aan die kant niet te ontregelen.
Dit werkt echter enkel als c, p en g op e´en lijn liggen. (Ga eens na.) Er zijn
dus ´ nog twee mogelijkheden, naar gelang dat c een linker- of rechterkind is
van p:
○ Knoop c is een linkerkind van p, Hier liggen de 3 knopen op 1 lijn. We
roteren ouder p en grootouder g naar rechts, maken p zwart, en g
4
