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 20. mars fyrir kl 16:00
Leysið dæmi 3.2.1 í bókinni.
Draw the BST that results when you insert the keys E A S Y Q U E S T I O N, in that order (associating the value i with the ith key, as per the convention in the text) into an initially empty tree. How many compares are needed to build the tree?
Leysið dæmi 3.2.6 í bókinni.
Add to BST a method height() that computes the height of the tree. Develop two implementations: a recursive method (which takes linear time and space proportional to the height), and a method like size() that adds a field to each node in the tree (and takes linear space and constant time per query).
Beinagrind fyrir tvíleitartré: BST.java. Athugið að endurkvæm height() aðferð fylgir með beinagrindinni. Þið ættuð samt að reyna að skrifa ykkar eigin útgáfu frá grunni og skilja nákvæmlega hvernig hún virkar.
Leysið dæmi 2.4.5 í bókinni.
Give the heap that results when the keys E A S Y Q U E S T I O N are inserted in that order into an initially empty max-oriented heap.
Leysið dæmi 2.4.24 í bókinni.
Priority queue with explicit links. Implement a priority queue using a heap-ordered binary tree, but use a triply linked structure instead of an array. You will need three links per node: two to traverse down the tree and one to traverse up the tree. Your implementation should guarantee logarithmic running time per operation, even if no maximum priority-queue size is known ahead of time.
Skrifið notkunarlýsingu fyrir öll föll sem þið skrifið. Skrifið fastayrðingu gagna fyrir útfærslu ykkar á forgangsbiðröðinni. Skrifið fastayrðingu lykkju fyrir allar lykkjur sem þið skrifið.
Það er líka hægt að útfæra þetta án þess að geyma tilvísun á foreldri í hverjum hnút og ef þið gerið það þannig þá megið þið sleppa parent tilviksbreytunni og halda bara utan um tilvísun á vinstra og hægra undirtré.
Vísbending: þið getið geymt fjölda gilda í hverjum hnút (eins og size í BST) og notað það í innsetningu til að setja gildi á réttan stað í trénu þ.a. það fylli hverja hæð áður en það byrjar á næstu hæð.