Opgaven Zoekbomen Datastructuren, 15 juni 2016, Werkgroep. Gebruik deze opgaven, naast die uit het boek, om de stof te oefenen op het werkcollege. Cijfer: Op een toets krijg je meestal zes tot acht opgaven. 1. Boom tekenen: Boek Cormen, 12.1-1. Oplossing: Beoordeling/Toelichting: 2. Heap ordening: Boek Cormen, 12.1-2. Oplossing: In de min-heap ordening zijn de keys zowel in de linker- als in de rechterdeelboom groter dan in de root. Daardoor is er geen ordening bekend tussen de linker- en rechterdeelboom onderling. Omdat je een Heap in lineaire tijd kunt bouwen, maar keys niet in lineaire tijd kunt sorteren, is het onmogelijk om keys uit een heap in lineaire tijd geordend te enumereren. Beoordeling/Toelichting: De onmogelijkheid geldt natuurlijk onder restrictie van een vergelijkings-gebaseerde methode. 3. Iteratieve walk: Boek Cormen, 12.1-3. Oplossing: Om de boom te doorlopen, houd je bij als v waar je bent en als u waar je vandaan komt. Kom je in v vanuit de parent dan ga je naar links, kom je van links dan ga je naar rechts, kom je van rechts dan ga je naar boven. Ontbrekende deelbomen moet je overslaan; is de parent NIL dan ben je klaar (root). Voor een INorder traversal behandel je de key wanneer je van links komt, voordat je naar rechts gaat. Beoordeling/Toelichting: 4. Pre- en PostOrder Traversie: Boek Cormen, 12.1-4. Oplossing: Het enige verschil met Inorder is de plaatsing van print x.key; deze komt voor de beide recursieve aanroepen voor een preorder, en erna voor een postorder traversal. Beoordeling/Toelichting: Ook de iteratieve traversie uit 12.1-3 kun je gemakkelijk ombouwen op dezelfde manier. 5. Som van keys in zoekboom: Geef een methode die de som van de keys in een zoekboom berekent. Wat is de rekentijd? Oplossing: Een lege boom heeft geen keys dus som 0, voor een niet-lege neem je de sommen van de deelbomen plus de root: int som (Boom x) { if (x == null) return 0; return som(x.left) + x.key + som(x.right); } De rekentijd is Θ(n) net als voor Inorder traversal. Beoordeling/Toelichting: Je kunt ook de methode voor Inorder traversal pakken en de print statement vervangen door s += x.key;, met s een globale sommatievariabele.
6. Max van keys in zoekboom: Geef een methode die het maximum van de keys in een zoekboom berekent. Wat is de rekentijd? Oplossing: Als de rechterdeelboom leeg is, is de root key maximaal en anders zit de max key in de rechterdeelboom: int max (Boom x) { if (x.Right == null) return x.key; return max(x.right); } Een lege boom heeft geen keys, dus ga ervan uit dat max niet wordt aangeroepen op een blad. De rekentijd is lineair in de diepte van de meest rechte knoop. Beoordeling/Toelichting: Het is hier niet slim om de max te bepalen door alle keys te bekijken en te vergelijken.
7. Aantal bladen: Bewijs dat een binaire boom met n knopen, precies n + 1 bladen heeft. Oplossing: Gebruik inductie over de structuur van de boom. Als de boom een blad is, heeft hij 1 blad en 0 knopen, dus de bewering klopt met n = 0. Als de boom een knoop is met twee deelbomen: noem de aantallen knopen links en rechts nL en nR en de aantallen bladen bL en bR ; de inductiehypothese zegt dat bL = nL + 1 en bR = nR +1. Totaal heeft de boom n = nL +nR +1 knopen (tel de root mee) en b = bL +bR bladen (bladen zitten links of rechts). Dan is b = bL + bR = nL + 1 + nR + 1 = n + 1. Beoordeling/Toelichting:
8. Een boom bouwen: Boek Cormen 12.1-5. Oplossing: Gebruik de ondergrens van Ω(n lg n) voor het oplopend opleveren van keys. Omdat je de keys in lineaire tijd kunt opleveren als je ze eenmal in een zoekboom hebt staan, impliceert dit een ondergrens van Ω(n lg n) − O(n) = Ω(n lg n) voor het bouwen. Beoordeling/Toelichting: Dit is in primitieve vorm een reductie-argument.
9. Minimaal aantal keys: Bewijs, met inductie over de structuur van de boom, dat een boom met hoogte h, tenminste h + 1 keys bevat. Oplossing: Zoals ge¨eist gebruiken we inductie over de structuur. Een lege boom heeft hoogte −1 en bevat 0 keys, zodat het aantal keys exact h + 1 is. Stel B is een boom van hoogte h, die een wortel heeft en deelbomen L en R. Deze L en R hebben hoogte ≤ h − 1, maar minstens een van die bomen heeft hoogte gelijk aan h − 1. (Want als beide hoogtes strikt kleiner dan h − 1 zijn, heeft B hoogte h − 1 of minder.) Die deelboom heeft (IH) tenminste (h − 1) + 1 = h keys; samen met de key in de wortel levert dat al h + 1 keys. Beoordeling/Toelichting: Deze eigenschap impliceert dat de hoogte van een boom met n keys, maximaal n − 1 is. Helaas is de bewezen grens scherp, en deze afgeleide dus ook: een boom met n keys kan hoogte n − 1 hebben, dus lineair.
10. Overtreffer: Geef een methode die, voor key x, in een binaire zoekboom de kleinste waarde y vindt die grotergelijk x is. (Lever een pointer naar de knoop, of null als er geen key ≥ x is.) Oplossing: Dit kan recursief en zonder parent-pointers: Tree overtreffer(Tree t, key x): { if (t == null || t.key == x) return t; if (x > t.key) return overtreffer(t.right, x); Tree ol = overtreffer(t.left, x); if (ol == null) return t; else retun ol; } Beoordeling/Toelichting: Dit is een querie die je in een hashtabel niet kunt doen. 11. Zoek-sequences: Boek Cormen, 12.2-1. Oplossing: Reeks (c) kan niet, want als je bij 911 naar links gaat, kun je daarna geen 912 meer tegenkomen. Beoordeling/Toelichting: 12. Voorganger: Boek Cormen, 12.2-3. Oplossing: Beoordeling/Toelichting: 13. Ordening: Boek Cormen, 12.2-4. Oplossing: Beoordeling/Toelichting: Hoe kun je weten dat je voorbeeld het kleinst mogelijke is? 14. Ordening: Boek Cormen, 12.2-5. Oplossing: Als knoop x een rechterdeelboom heeft, dan is zijn successor de kleinste waarde in die rechterboom, dus een knoop y die onder x zit. Dan is x de predecessor van y, dus y heeft een predecessor die boven hem zit, wat alleen kan als y een lege linkerdeelboom heeft. Beoordeling/Toelichting: 15. Herhaalde Successor: Boek Cormen, 12.2-7. Oplossing: De tijd van TreeSuccessor bestaat, afgezien van een constant gedeelte, uit het volgen van ofwel pijlen naar links (treeMinimum van rechterdeelboom) danwel naar boven (tegen een rechterlink in). Het aantal stappen is precies het aantal links, via de boom, naar de successor. Als je met deze methode de hele boom door wandelt, passeer je elke link tweemaal, zodat de totale tijd lineair is. Beoordeling/Toelichting:
16. Tel de key: Schrijf een methode TelK(Tree t, key x) die telt hoevaak de key x voorkomt in de boom. De tijd moet Θ(a + h) zijn, waar a het uiteindelijke antwoord is en h de hoogte van de boom. Oplossing: Wanneer x groter (resp. kleiner) is dan de wortel, ga je alleen in recursie op reschts (resp. links): int TelK(Tree t, key x) { if (t == null) return 0; int r = (x = t.key ? 1 : 0); if (x <= t.key) r += TelK(t.left, x); if (x >= t.key) r += TelK(t.right, x); return r; } Beoordeling/Toelichting: Of gebruik TelR(t, k, k) uit opdracht Tel de Range.
17. Tel de Range: Schrijf een methode TelR(Tree t, key a, key b) die telt hoeveel keys tussen a en b voorkomen in de boom. De tijd moet Θ(a + h) zijn, waar a het uiteindelijke antwoord is en h de hoogte van de boom. Oplossing: Wanneer a groter (resp. b kleiner) is dan de wortel, ga je alleen in recursie op rechts (resp. links): int TelR(Tree t, key x) { if (t == null) return 0; int r = (a <= t.key && b >= t.key ? 1 : 0); if (b <= t.key) r += TelR(t.left, a, b); if (a >= t.key) r += TelR(t.right, a, b); return r; } Beoordeling/Toelichting: Nou nog bewijzen dat het de tijdgrens haalt....
18. Lengte zoekpad: Boek Cormen, 12.3-2. Oplossing: Als er geen Deletes plaatsvinden, blijft elke knoop altijd staan op de plek waar hij ooit is ingevoegd. Na het bekijken van een aantal keys (zoekpad) kwam de Insert methode uit bij null, waar de nieuwe node is ingevoegd. Bij een latere Search voor die key, bekijk je hetzelfde zoekpad plus de toen ingevoegde knoop. Beoordeling/Toelichting:
19. TreeSort: Boek Cormen, vraag 12.3-3. Oplossing: Deze sorteermethode werkt wel, maar is vrij slecht. Een situatie die heel veel tijd kost, is waar de keys al gesorteerd staan. Bij elke Insert wordt de key rechts onderin de boom geplaatst, wat een lange sliert van keys oplevert. Het invoegen van de ide key kost O(i) tijd, met een totaal van O(n2 ). Met iets meer geluk, ontstaat een boom die in balans is, en waarbij de paden O(lg n) lang zijn. Dan kost het in totaal O(n lg n). Omdat de hoogste i niveaus van de boom samen hoogstens 2i − 1 keys bevatten, zit zeker meer dan de helft van de keys op een diepte groter dan lg n − 2. Dit bewijst dat het beste geval toch ook Ω(n lg n) tijd neemt. Dus het slechtste geval is Θ(n2 ) en het beste geval is Θ(n lg n). Beoordeling/Toelichting: Over het uitlezen van de keys hoef je je geen zorgen te maken, want het doorlopen van de boom kost altijd Θ(n), onafhankelijk van de vorm van de boom. Het aantal vergelijkingen komt overeen met wat je doet in QuickSort. De eerste key geldt als pivot die de verzameling in een linker- en rechterdeel splitst. Toch werkt dit om twee redenen slechter dan QuickSort. Ten eerste omdat er geen randomisering zit in het kiezen van de pivot. Ten tweede omdat de vergelijkingen in een andere volgorde gebeuren. Bij QuickSort kies je een pivot en dan vergelijk je alle keys achter elkaar met die pivot. Hier is de pivot de eerste key, waarna je alle later binnenkomende keys vergelijkt met die, en vervolgens met andere keys die daaronder zitten in de boom. Dat geeft een veel slechter cache-gedrag.
20. Delete volgorde: Boek Cormen, vraag 12.3-4. Oplossing: Voorbeeld met vier knopen: Root A met linkerkind B en rechterkind C, en C heeft linkerkind D. Als ik eerst A delete en dan B: A heeft twee kinderen, dus vervang ik A door minimum van rechts ofwel D, dan verwijder B die geen kinderen heeft; resultaat is D met rechterkind C. Als ik eerst B delete en dan A: B heeft geen kinderen dus wordt weggeknikkerd, dan heeft A maar 1 kind dus wordt door die deelboom vervangen; resultaat is C met linkerkind D. Beoordeling/Toelichting: Het kleinst mogelijke voorbeeld begint met vier knopen. Begin je namelijk met drie, dan heb je er na twee Deletes maar een over, waarmee er slechts een boom mogelijk is.
21. Dictionary programmeren: Schrijf een programma dat een binaire zoekboom bijhoudt, en minstens de operaties Insert en Delete kan doen. Voor de updates geef je de pointers naar (deel)bomen mee als ref (Call-by-Reference). Implementeer ook de suggestie uit vraag 12.3-6; werkt het nu beter? Oplossing: Beoordeling/Toelichting: Je kunt de methoden bijna overkloppen uit de class notes, maar je moet er wel op letten in welke class je ze neer zet.
22. Hoogte in Tree bijhouden: Download het PILletje Tree. (a) Breid de Insert (en ExtracMin) zo uit, dat de hoogte van alle knopen wordt bijgehouden. (b) Schrijf een Delete (die de hoogtes ook goed bijhoudt). Oplossing: Beoordeling/Toelichting:
23. Wisselstrategie: Boek, Cormen vraag 12.3-6. Oplossing: Beoordeling/Toelichting:
24. ExtractMax in Tree: Schrijf een methode ExtractMax() die de grootste waarde uit een binaire zoekboom oplevert en verwijdert. Oplossing: Spiegel deze code voor ExMin: public Tree ExtractMin(ref Tree t) { if (t.left == null) { Tree r = t; t = t.right; return r.key; } else return ExtractMin(ref t.left); } Beoordeling/Toelichting: Dit werkt weer het gemakkelijkst als je de boom als ref meegeeft. Vergelijk eens een ref uitwerking met een iteratieve met trailing pointer!
25. Concatenatie van bomen: Schrijf een methode die twee binaire bomen S en T samenvoegt tot een boom. Gegeven is dat alle keys in S kleiner zijn dan alle keys in T . Het moet werken in tijd O(h). Oplossing: Als een van de bomen leeg is, lever je de andere op. Als T niet-leeg is, bepaal een knoop ExtractMin(T) en gebruik die als wortel, met S als linker- en (de gekrompen) T als rechterdeelboom. Beoordeling/Toelichting: Dit is natuurlijk veel lastiger wanneer het om gebalanceerde bomen gaat en ook de nieuwe boom weer gebalanceerd moet zijn. Want (bij bv. AVL bomen) de ene boom kan veel dieper zijn dan de andere. Als T minder diep is: haal het minimum uit T en daal in S af langs een pad naar rechts totdat je bij een knoop V komt die even hoog is als T . Vervang die knoop door de waarde die je uit T hebt gepeuterd, met rechterdeelboom T en linkerdeelboom V .
