100% tevredenheidsgarantie Direct beschikbaar na je betaling Lees online óf als PDF Geen vaste maandelijkse kosten
logo-home
Eerder door jou gezocht
Eerder door jou gezocht
logo
Gevorderde Algoritmen Samenvatting Theorie en Artikel Inverted Files €15,49
In winkelwagen
Snel navigeren naar
Voorbeeld
  2.  
  3. Universiteit Gent (UGent)
  4.  
  5. Industriële Wetenschappen
  6.  
  7. Gevorderde Algoritmen (E765015)

Samenvatting

Gevorderde Algoritmen Samenvatting Theorie en Artikel Inverted Files
 2 keer verkocht

Bestand bestaat uit 115 pagina's. Bevat alle theorie soms filmpjes/afbeeldingen ter verduidelijking. Als je dit vanbuiten kent heb je minstens 16/20

Voorbeeld 4 van de 115  pagina's

Document informatie

  • 26 december 2019
  • 115
  • 2019/2020
  • Samenvatting

Onderwerpen

Geschreven voor

Alle documenten voor dit vak (1)

Verkoper

avatar-seller
KrekelMan

Voorbeeld van de inhoud

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

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, Bancontact of creditcard en je bent klaar. Geen abonnement nodig.

Focus op de essentie

Focus op de essentie

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper KrekelMan. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €15,49. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 64419 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Start met verkopen

Laatst bekeken door jou

Samenvatting ·

(1)

Samenvatting Sociologie, een inleiding door Elchardus, Spruyt en Vanroelen

Samenvatting ·

(0)

Samenvatting Publiek Recht - Jan Fiers
€15,49  2x  verkocht
  • (0)
In winkelwagen
Toegevoegd