Garantie de satisfaction à 100% Disponible immédiatement après paiement En ligne et en PDF Tu n'es attaché à rien
logo-home
Recherché précédemment par vous
Recherché précédemment par vous
logo
Gevorderde Algoritmen Samenvatting Theorie en Artikel Inverted Files $17.30
Ajouter au panier
Accédez rapidement à
Aperçu
  2.  
  3. Universiteit Gent (UGent)
  4.  
  5. Industriële Wetenschappen
  6.  
  7. Gevorderde Algoritmen (E765015)

Resume

Gevorderde Algoritmen Samenvatting Theorie en Artikel Inverted Files
 2 fois vendu
  • Cours
  • Gevorderde Algoritmen (E765015)
  • Établissement
  • Universiteit Gent (UGent)

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

Aperçu 4 sur 115  pages

Infos sur le Document

  • 26 décembre 2019
  • 115
  • 2019/2020
  • Resume

Sujets

  • gevorderde algoritmen
  • theorie
  • informatica
  • algoritmen ii
  • algoritmen 2
  • master
  • industrieel
  • artikel inverted files

École, étude et sujet

  • Universiteit Gent (UGent)
  • Industriële wetenschappen
  • Gevorderde Algoritmen (E765015)
Tous les documents sur ce sujet (1)

Vendeur

avatar-seller
KrekelMan

Aperçu du contenu

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

Les avantages d'acheter des résumés chez Stuvia:

Qualité garantie par les avis des clients

Qualité garantie par les avis des clients

Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.

L’achat facile et rapide

L’achat facile et rapide

Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.

Focus sur l’essentiel

Focus sur l’essentiel

Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.

Foire aux questions

Qu'est-ce que j'obtiens en achetant ce document ?

Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.

Garantie de remboursement : comment ça marche ?

Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.

Auprès de qui est-ce que j'achète ce résumé ?

Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur KrekelMan. Stuvia facilite les paiements au vendeur.

Est-ce que j'aurai un abonnement?

Non, vous n'achetez ce résumé que pour $17.30. Vous n'êtes lié à rien après votre achat.

Peut-on faire confiance à Stuvia ?

4.6 étoiles sur Google & Trustpilot (+1000 avis)

64419 résumés ont été vendus ces 30 derniers jours

Fondée en 2010, la référence pour acheter des résumés depuis déjà 15 ans

Commencez à vendre!

Récemment vu par vous

Resume ·

(1)

Praktische verloskunde samenvatting adhv Leerdoelen

Resume ·

(1)

Huidtherapie jaar 2 Blok A2 Uitwerking/Samenvatting College 1,2, 3 Zwachtelen

Dissertation ·

(0)

Unit 2 Assignment D – Review personal development of a scientific skill for laboratory work

Resume ·

(33)

Samenvatting / Summary International Business Management [Organization & Management, an international approach]

Study guide ·

(1)

Med-Surg nursing midterm study guide

$17.30  2x  vendu
  • (0)
Ajouter au panier
Ajouté