Datastructuren, januari 2023

1. Wandelen met draden in een binaire boom, dus zonder recursie of externe stapel.
(Er wordt niet gevraagd naar een compleet wandelalgoritme.)

Voor jezelf een voorbeeld tekenen helpt, maar het moet wel een beetje verschillende gevallen bevatten (ontbrekende kinderen her en der). Drie knopen helpt niet.

a) == Inorde-eerste is de meest linkse knoop in de boom, dus herhaald linkerkind tot nil.
== Inorde-opvolger altijd via de rechter pointer.
- Is dat een tak, volg de tak en dan zoveel mogelijk links.
- Is dat een draad, volg de draad en we zijn in de opvolger.

b) == Preorde-eerste is de wortel van de boom
== Inorde-opvolger: linker-kind als dat bestaat,
- anders (linker pointer is nil) rechter-kind als dat bestaat,
- anders (rechter pointer is een draad) vinden we de eerste knoop die nog niet bezocht is door herhaald draden te volgen omhood, tot we de eerste rechter tak vinden die we volgen. 
Plaatje helpt.

c) == Postorder-eerste is het meest linkse blad in de boom. Volg herhaald linker-pointers én rechter-pointers (wanneer links nil). 
(Dus niet hetzelfde als bij Inorde.)
== Neem de wortel met een heel lang pad naar links. De opvolger van de laatste knoop op dat pad is de ouder van die knoop. Technisch gezien kunnen we die wel vinden (vanuit de wortel) maar het is niet elegant.


2. a) Geef een definitie, niet alleen intuitie (als: 'soort van B-boom', 'gebalanceerd'). De informatie moet genoeg zijn om een RZ-boom te kunnen herkennen. 

== Een RZ-boom is een *binaire zoekboom*, waar alle knopen zwart dan wel rood gekleurd zijn. 
Er zijn de volgende *structurele* voorwaarden.
- De wortel is zwart.
- Een rode knoop heeft geen rode kinderen.
- Elk pad van wortel naar blad heeft hetzelfde aantal zwarte knopen (zwart-diepte).

(Toevallig heeft de boom uit het plaatje afwisselend rode en zwarte nivo's, maar dat is per ongeluk.)

- Binaire zoekboom is een voorwaarde op de *ordening* van de knopen: alle knopen in de linker subboom van een knoop hebben eem kleinere waarde dan de knoop zelf. Rechts groter.
   
b) (i) Ja. Bij een flag-flip kan een zwarte grootouder van een knoop nieuw rood gekleurd worden. Die grootouder zou zelf weer een rode vader kunnen hebben. We moeten dan hoger in de boom weer herstructureren, en dat kan weer een flag-flip zijn. 
Zie hieronder bijvoorbeeld bij toevoegen van (2).

(ii) Nee. Na rotatie blijft de zwarte grootouder van de rood-rood combinatie zwart. Het proces stopt. Dit kan één enkele of dubbele rotatie zijn (die we als één tellen meestal).

Zie ook dictaat, of de korte versie op de slides:

  " >> insertion in red-black tree <<
  " Insert as red leaf. problem: red node with red parent, then:
  " -- if uncle is red: flag-flip. *continue* at grandparent.
  " -- if uncle is black: rotate (see AVL-trees), repaint and *stop*.
  " if the root has been coloured red, make it black

c) We plaatsen een waarde als rood blad op de juiste plek in de binaire zoekboom.
== (2) komt als linker kind van (3). rood-rood met rode oom. Flag-flip.
Dan wordt (6) ook rood. Weer flag-flip. (21) daarna zwart kleuren.

== (16) als linker kind van (18). rood-rood met zwarte oom (het nil blad telt als zwart). Rechts links, dus dubbele rotatie naar links. Knoop (16) wordt zwart, de twee kinderen (15) en (18) rood.
(Het opnieuw inkleuren van de knopen na rotatie noem ik geen flag-flip.)

== (28) als linker kind van (30). Dit keer enkele rotatie naar rechts.

d) De voor de hand liggende methode is om de voorganger (9) op de plek van (12) te zetten, zoals dat meestal in binaire zoekbomen gebeurt. Hier kloppen de kleuren ook meteen.
(Ik heb ook veel simpele alternatieven goed gerekend.)


3. De drie operaties van de ADT worden expliciet genoemd. Het is duidelijk een min-heap. 

a) (i) Een binary heap is een *complete binaire boom* die de *heap ordening* heeft.
Compleet is een *structurele* restrictie (alle nivo's tot de laatste helemaal gevuld, de laatste wordt van links af gevuld). Heap ordening een restrictie op *ordening*, de waardes in de knopen (ouder kleiner dan kinderen, want min-heap).

(Néé, niet het woord zoekboom gebruiken, dat is een andere ordening. Zucht.)

Je kunt als alternatief ook de beschrijving als array gebruiken. Leg dan uit waar de kinderen van knoop [i] zich bevinden, namelijk in [2*i] en [2*i+1]. Met de wortel in [1].

== Als waarde van een knoop kleiner wordt gemaakt, passen we TrickleDown toe. Zolang de waarde van de knoop kleiner is dan die van de ouder verwisselen we die herhaald met die van de ouder totdat weer de heap order geldt voor de knoop.

== Als waarde van een knoop groter wordt gemaakt, passen we BubbleUp toe. Als de waarde van de knoop groter is dan die van een van de kinderen verwisselen we de knoop met het kleinste kind totdat de heap order weer klopt.

(TrickleDown en BubbleUp worden gebruikt bij toevoegen en verwijderen, maar zijn ook in andere context nuttig. De namen van de operaties suggereren al dat er iets omhoog of omlaag beweegt in de boom. Het antwoord moet meer bevatten dan dat om compleet te zijn.)

(ii) == Insert: voeg de nieuwe waarde achteraan toe in de heap. BubbleUp. 
== FindMin: waarde in de wortel.
== DeleteMin: Plaats de laatste waarde uit de heap in de wortel. TrickleDown.

b) (i) Een leftist tree is een binaire boom waar in elke knoop de NPL van het rechter kind kleiner of gelijk is aan de NPL van het linker kind.
De *nil-path-length* NPL van een knoop is de afstand tot het dichstbijzijnde nil-blad.
De boom heeft ook de heap ordening als we er een priority queue van willen maken.

Zip neemt van twee leftist trees de knopen op hun paden naar rechts, en voegt deze knopen samen tot één pad naar rechts waarop de knopen van klein naar groot liggen. De deelbomen naar links toe blijven verbonden met hun knoop op het rechter pad. De recursieve definitie staat in het diktaat. Met een plaatje.

Na dit samenvoegen moet langs dat rechter pad de leftist eigenschap hersteld worden door waar nodig linker en rechter kind te verwisselen.

(ii) == Insert: plaats de nieuwe waarde in een boom met één knoop. Zip met de oorspronkelijke boom. 
== FindMin: waarde in de wortel.
== DeleteMin: Zip na het verwijderen van de wortel de twee bomen die onder de wortel hingen.

c) (i) De binary heap is een array. Plaats een array achter de andere. Maak opnieuw een heap met de operatie *heapify*. Dat is een vernuftige toepassing van BubbleUp, van achter naar voor.  
Verplaatsen van het ene array en heapify hebben beide lineaire complexiteit. O(n).
(Eén voor één de waardes toevoegen gebruikt ook BubbleUp, maar geeft een slechtere complexiteit.)

(ii) Zip de twee bomen. logaritmisch O(lg n).


4. a) Probeer een beetje precies te zijn met de beschrijving, maar inderdaad, een plaatje helpt. Het is niet nodig de algoritmes uit te leggen.

== Huffman. Een volle binaire boom. Elke knoop heeft twee takken (gelabeld met 0 en 1). Letters staan in de bladeren. De code van een letter wordt gevormd door de letters langs het pad naar het betreffende blad.

== ZLW. De boom heeft een trie structuur. Letters staan langs de takken. De wortel heeft alle letters als tak. De code van een string langs een pad naar een knoop wordt opgeslagen in die knoop.

b) O(n lg n). Niet lineair want hoewel er lineair vaak twee bomen worden samengevoegd moeten we steeds de kleinste frequentie bepalen. Of vooraf alle frequenties sorteren.

c) (i) Dat gaat wel lukken met behup van het diktaat, denk ik?
Eerst worden N en X samen gevoegd tot een boom van frequentie 15.
Dan heeft Huffman keuze: 14 kan met elk van de twee van 15 gecombineerd worden. 
Dat leidt tot twee verschillende bomen, die allebei goed zijn. 

(ii) Totaal 208 bits zijn nodig om de complete tekst te coderen. Sommeer de frequentie maal het aantal bits over alle zes letters.
(Rekenfouten werden niet bestraft, als de formule maar klopt.)

d) Huffman heeft de keuze die hierboven werd aangegeven, maar óók uit links en rechts bij het samenvoegen. Er is dus zeker geen uniek resultaat.
Máár de N en X staan altijd onder dezelfde ouder. Als er nog ergens een letter op dezelfde diepte in de boom staat kunnen we die met N of X verwisselen en krijgen dan een boom met dezelfde efficientie zonder dat Huffman die zou kunnen construeren.
(Als N en X helemaal onderaan hangen is er hoger in de boom een vergelijkbare situatie.)

2.3'23 HJH / versie 4.4'24