Opgaven werkcollege 11

DS werkcollege
opgaven 76–84
DS werkcollege 11
OPGAVE 76 ([CLRS3, 12.2-2]). Geef recursieve algoritmen voor Tree-Minimum en TreeMaximum.
OPGAVE 77. Beschouw de zoekboom van figuur 12.3 op pagina 295, inclusief de knoop
met key 13. Teken de bomen die ontstaan door achtereenvolgens de knopen met keys 13, 12
en 15 te verwijderen, waarbij je het Tree-Delete algoritme volgt (zie p. 296 voor uitleg
over de delete procedure).
OPGAVE 78 ([CLRS3, 12.3-1]). Geef een recursieve versie van Tree-Insert uit [CLRS3]
blz 294.
OPGAVE 79 ([CLRS3, 12.3-4]). Maakt de volgorde waarin elementen verwijderd worden
uit een zoekboom uit? Als we twee nodes x en y in een zoekboom hebben, is dan de boom
die ontstaat door eerst x en daarna y te verwijderen altijd hetzelfde als de boom die we
krijgen bij het verwijderen van y en daarna x? (Voor het verwijderen volgen we het algoritme
Tree-Delete.) Zo ja, geef een bewijs; zo nee, een tegenvoorbeeld.
OPGAVE 80. In deze opgave beschouwen we volle binaire bomen met in de interne knopen
integers als key. De bomen zijn dus niet noodzakelijkerwijs zoekbomen. Geef een volle binaire
boom T met 7 interne knopen die aan de volgende twee eigenschappen voldoet:
1. Voor elke interne knoop v geldt (voorzover het linker- en rechterkind van v bestaan)
dat v.lef t.key ≤ v.key ≤ v.right.key.
2. T is geen binaire zoekboom.
OPGAVE 81. Geef een O(n)-tijd recursief algoritme dat van een fully binary tree T met n
items, bepaalt of T de zoekboom eigenschap heeft. Je algoritme mag niet de parent pointers
x.parent gebruiken.
OPGAVE 82 ([CLRS3, B.5-3]). Bewijs met inductie dat in elke proper binary tree het
aantal interne knopen ´e´en minder is dan het aantal bladeren.
Doe hetzelfde voor elke fully binary tree.
OPGAVE 83. Geef een O(n) tijd algoritme dat een geordende array van n integers neemt
en een binaire zoekboom bouwt van deze n integers. De zoekboom moet hoogte O(log n)
hebben, en je algoritme moet in tijd O(n) werken. Bewijs dat je algoritme aan de gestelde
eisen voldoet. Hint: Gebruik een recursieve aanpak. Om te zorgen dat de hoogte van de
boom O(log n) wordt wil je dat de linker- en rechter deelboom van de wortel allebei ongeveer
evenveel knopen bevatten. Daarom is het misschien handig om als wortel van de boom een
key te nemen ongeveer halverwege de gesorteerde array.
Verdieping
1
DS werkcollege
opgaven 76–84
OPGAVE 84 ([GT4, C-7.22]). Zij T een nette (proper) binaire boom met n knopen en van
hoogte h. Zij dv de diepte van knoop v in T . We defini¨eren de afstand distance(v, w) van
twee knopen v en w in T als:
distance(v, w) = dv + dw − 2du
waarbij u de laagste gemeenschappelijk voorouder van v en w is, oftewel de knoop u met de
grootste diepte zodat v en w beiden afstammelingen van u zijn. We defini¨eren de diameter
diam(T ) van de boom T als
diam(T ) = max{distance(v, w) : v en w knopen in T }
Geef een efficient algoritme dat de diameter van een nette binaire boom T bepaalt. Geef een
zo goed mogelijke tijdgrens van je algoritme (in termen van grote O van een functie in n en/of
h).
Referenties
[CLRS3] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd
edition, The MIT Press, McGraw-Hill Book Company, 2009.
[GT4] M.T. Goodrich, R. Tamassia, Data Structures and Algorithms in Java, 4th edition,
John Wiley & Sons, Inc. 2006.
2

Download Report