Vaje 12. 1. (Optimalna iskalna drevesa)

Odprto: ponedeljek, 10 januar 2022, 00:00 AM
Rok za oddajo: petek, 21 januar 2022, 20:00 PM
Na vajah bomo na tablo rešili nekaj primerov računanja tabele optimalnih cen in korenov ter gradnje optimalnega drevesa.

1. Izračunajte tabelo cen in korenov za elemente z naslednjimi pogostostmi iskanja:

i         |  1     2     3
element   |  a     b     c
pogostost | 30    20    10
Kolikšna je cena tega optimalnega drevesa?

2. S pomočjo tabele korenov iz prejšnje naloge rekonstruirajte optimalno dvojiško iskalno drevo.
Izračunajte pričakovan čas iskanja za to drevo in ga primerjajte z izračunano ceno.

3. Rekonstruirajte drevo z naslednjimi elementi in pripadajočimi pogostosti s pomočjo tabele optimalnih cen in korenov.

i         |   1     2     3     4     5     6     7
element   |  10    19    26    33    37    42    48
pogostost |  22    18    20     5    25     2     8

Poročilo

Za priznane vaje oddajte fotografijo/scan/posnetek zaslona na roke rešenih primerov.