Tölvunarfræði 2 - Vor 2012
Verkefni 11
Lausnum skal skilað til viðkomandi dæmakennara (sjá lista yfir dæmatíma).
Reynið að skrifa stutt, skýr og hnitmiðuð forrit. Notið réttan inndrátt og gætið þess að forritin ykkar séu læsileg.
Skiladagur: þriðjudaginn 27. mars fyrir kl 16:00
Dæmi 1 (2 stig) - Innsetning í 2-3 tré
Leysið dæmi 3.3.1 í bókinni.
Draw the 2-3 tree that results when you insert the keys E A S Y Q U T I O N in that order into an initially empty tree.
Dæmi 2 (1 stig) - Rauð-svört tré
Leysið dæmi 3.3.9 í bókinni.
Which of the following are red-black BSTs?
Dæmi 3 (2 stig) - Innsetning í rautt-svart tré
Leysið dæmi 3.3.10 í bókinni.
Draw the red-black BST that results when you insert items with the keys E A S Y Q U T I O N in that order into an initially empty tree
Dæmi 4 (2 stig) - Word frequency counter
Skrifið forrit sem les orð af aðalinntaki og prentar út á aðalúttak hversu oft hvert orð kemur fyrir í inntakinu.
Notið rautt-svart tré (RedBlackBST) til að halda utan um talninguna.
Dæmi 5 (3 stig) - File index
Skrifið forrit í C eða Java sem tekur inn lista af skrám sem viðföng í skipanalínu og býr til flýtivísi þ.a. það sé hægt að fletta hratt upp öllum skránum sem innihalda gefið orð.
Forritið á að lesa orð af aðalinntaki og prenta út lista yfir allar skrár (af þeim sem voru gefnar upp á skipanalínu sem viðföng) sem innihalda viðkomandi orð.
Notið rautt-svart tré til að geyma flýtivísinn. Lyklarnir í trénu eiga að vera orð og gildin eiga að vera listi af skrám sem innihalda viðkomandi orð.
Þið megið nota java.util.TreeSet tilvik sem gildi í trénu.