Izpitno vprašanje RAČ2PRA 11800

Iz MaFiRaWiki

Vprašanje

Idejo podatkovne strukture dvojiška kopica lahko naravno razširimo na pojem trojiške kopice. Namesto dveh ima sedaj vsako vozlišč največ 3 sinove. Tudi tu je drevo levo poravnano. Denimo, da trojiško kopico predstavimo v tabeli (v razredu Trojiska_Kopica imamo komponento tabela z n elementi, kjer je n število elementov v kopici) (v tabeli elementa z indeksom 0 NE izpustimo!). Opiši način predstavitve trojiške kopice, relacije med očetom in sinovi ...

Odgovor

Če elemente trojiške kopice predstavimo v tabeli in gledamo na vozlišče, ki ima v tabeli indeks i, velja naslednje (pri odgovoru smo zanemarili navodilo ... v tabeli elementa z indeksom 0 NE izpustimo! in v tabeli indeks 0 tudi izpustimo):

Oče vozlišča (i + 1) / 3
1.sin 3i - 1
2.sin 3i
3.sin 3i + 1

Pri tem mora prvo mesto tabele ostati prosto - koren drevesa pride na mesto z indeksom ena.

Če bi radi preverili ali je trojiška kopica, uporabimo sledečo metodo:

  1. public boolean testKopica(int[] elt){
  2. // ali je v tabeli elt trojiška kopica
  3. for(int i = 1; i < (elt.length() + 1)/3;i++)
  4. {
  5. if((elt[i] < elt[3 * i -1]) || //preverimo, če je prvi sin slučajno večji
  6. (elt[i] < elt[3 * i])|| // kaj pa drugi
  7. (elt[i]< elt[3 * i + 1])) // ali pa "zgago" dela (s tem da je prevelik) tretji sin
  8. return false; //v primeru, da je eden izmed sinov večji, vrnemo false
  9. }
  10. // tu še nekaj manjka - smo res pregledali vse?
  11. return true;// vse je OK
  12. }
Osebna orodja