Računalništvo 1

Naloge o dvojiških iskalnih drevesih:

1. Sestavi funkcijo, ki sprejme dvojiško iskalno drevo in vrne drevo enake oblike, ki ima v vozliščih shranjene vsote vseh ključev drevesa, ki so večji ali enaki ključu v izvornem vozlišču.
2. Sestavi funkcijo, ki sprejme dvojiško iskalno drevo in interval ter iz drevesa odstrani vozlišča, katerih vrednost je zunaj danega intervala.
3. Sestavi funkcijo, ki sprejme dvojiško iskalno drevo in število, vrne pa par vozlišč, katerih vsota ključev je enaka danemu številu. Če takih vozlišč ni, naj vrne None.
4. Sestavi funkcijo, ki sprejme dvojiško drevo (ne nujno iskalno) in vrne iskalno drevo z enako množico vozlišč in enake oblike kot dano drevo.
5. Poišči k-ti največji element v dvojiškem iskalnem drevesu. / Poišči k-ti najmanjši element v dvojiškem iskalnem drevesu.
6. Zbriši dano vozlišče iz dvojiškega iskalnega drevesa. Če ima to vozlišče dve poddrevesi, ga zamenjaj z naslednikom. / Zbriši dano vozlišče iz dvojiškega iskalnega drevesa. Če ima to vozlišče dve poddrevesi, ga zamenjaj s predhodnikom.
7. Poišči naslednika danega vozlišča v dvojiškem iskalnem drevesu. / Poišči predhodnika danega vozlišča v dvojiškem iskalnem drevesu.
8. Poišči največji ključ, ki je manjši ali enak danemu številu n (število n se ne nahaja nujno v drevesu). /  Poišči najmanjši ključ, ki je večji ali enak danemu številu n (število n se ne nahaja nujno v drevesu).

Nekatere od zgornjih nalog imajo dve verziji, kjer je mišljeno, da izberete eno. Za naloge uporabljajte implementacijo dvojiškega drevesa in predpostavite, da bo vhod vedno oblike dvojiškega iskalnega drevesa (torej se ne obremenjujte z drevesi, ki niso iskalna). Implementacijo lahko po želji dopolnite, vendar jo v tem primeru tudi oddajte.

Za uspešno opravljene vaje morate nabrati 6 točk, kjer velja:

• Dve podnalogi na projektu Tomo v sklopu Dvojiško Drevo II sta vredni po 1 točko, pri nalogi Rekonstrukcije dreves iz pregledov pa za vsako podnalogo dobite 1 točko.
  
• Zgornje naloge o dvojiških iskalnih drevesih so vredne po 2 točki. Oddajte python datoteko, ki naj vsebuje vsaj 3 teste.
• Poročilo o nalogi o dvojiških iskalnih drevesih je vredno 2 točki. Naloga naj tedaj vsebuje vsaj 5 testov. Oddajte markdown datoteko.

Kot primer: izberete lahko dve nalogi na Tomotu, rešite nalogo 6 (druga opcija s predhodniki) in o nalogi 6 napišete poročilo.