Izpitno vprašanje DIRI2005 11200

Iz MaFiRaWiki

Vprašanje

Naj tabela

40

18

15

9

x

11

15

y

1

6

3

11

5

predstavlja max kopico celih števil (x in y seveda nista tiskarski napaki, ampak ustrezni celi števili). Katere (celoštevilske) vrednosti lahko zavzameta x in y?

Odgovor

Max kopica je levo poravnano dvojiško drevo, kjer vrednost v očetu ni manjša od vrednosti v sinovih. Zaradi leve poravnanosti jo lahko predstavimo v tabeli brez praznih mest. Če elemente v tabele indeksiramo od 1 naprej, velja:

  • 1. element je koren (največji element v max kopici)
  • če je i-ti element v tabeli oče, ima za svojega levega sina (2*i)-ti element in za svojega desnega sina (2*i+1)-ti element

Dana tabela ima 13 elementov, ki so v kopici razporejeni po naslednjih nivojih od leve proti desni:

1. nivo: 40
2. nivo: 18, 15
3. nivo: 9, x, 11, 15
4. nivo: y, 1, 6, 3, 11, 5

Element x ima v tabeli indeks 5, torej je desni sin elementa z indeksom 2, to je 18. Ker gre za max kopico, mora biti x18. Po drugi strani pa ima x tudi dva sinova in sicer levega sina na 10. mestu, to je 6, in desnega sina na 11. mestu v tabeli, to je 3. Ker oče ne sme biti manjši od svojih sinov, mora biti x6.
Od tod sledi: 6x18.

Element y ima v dani tabeli indeks 8, torej je levi sin elementa z indeksom 4, to je 9. Ker gre za max kopico, mora biti y9. To je tudi edini pogoj za y, saj nima sinov.

Osebna orodja