Binarna stabla i njihova svojstva

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Što predstavlja visina čvora u binarnom stablu?

Broj čvorova u stablu

Broj listova u stablu

Broj lukova od čvora do korijena (correct)

Broj lukova najdužeg puta od čvora do lista

Koja od navedenih karakteristika definira balansirano binarno stablo?

Svi čvorovi imaju samo jedno dijete

Visina lijevog i desnog podstabla se razlikuje za najviše 1 (correct)

Svaki čvor ima dva ili više djece

Visina lijevog i desnog podstabla se razlikuje za najviše 2

Koji od navedenih tipova binarnih stabala garantira da svaki list ima istu dubinu?

Kompletno binarno stablo (correct)

Balansirano binarno stablo

Skoro potpuno binarno stablo

Binarno stablo pretraživanja

Kako je organizirano stablo za binarno pretraživanje?

Manji elementi su lijevo, a veći desno od svakog čvora Signup and view all the answers

Što je višak u skoro potpuno binarnom stablu?

Posljednja razina ne mora biti do kraja popunjena Signup and view all the answers

Koja tvrdnja o binarnim stablima je točna?

Jedan skup podataka može imati više različitih stabala Signup and view all the answers

Kako se naziva binarno stablo gdje su visine lijevog i desnog podstabla ujednačene?

Balansirano binarno stablo Signup and view all the answers

Koji kriterij ne definira potpuno binarno stablo?

Sva stabla su balansirana Signup and view all the answers

Što je topologijsko sortiranje?

Uređivanje čvorova tako da svaki čvor dolazi prije svojih sljedbenika. Signup and view all the answers

Za koji tip grafova je definirano topologijsko sortiranje?

Usmjereni aciklični grafovi. Signup and view all the answers

Koji je prvi korak u algoritmu za topološko sortiranje?

Pozvati DFS za dobivanje završnih vremena. Signup and view all the answers

Koji od sljedećih koraka dolazi nakon dovršetka čvora u topološkom sortiranju?

Dodaje se na vrh povezane liste. Signup and view all the answers

Koju vremensku složenost ima algoritam za topološko sortiranje?

Θ(V + E) Signup and view all the answers

Kako se može koristiti topološko sortiranje u stvarnom svijetu?

Za planiranje i organizaciju aktivnosti sa ovisnostima. Signup and view all the answers

Što se događa ako graf koji se sortira topološki nije acikličan?

Topološko sortiranje neće biti moguće. Signup and view all the answers

Koja se oznaka koristi za čvorove u trenutku kada su otkriveni tijekom DFS-a?

SIVO Signup and view all the answers

Što je topološko sortiranje u kontekstu grafa?

Redoslijed čvorova u kojem se svaki čvor pojavljuje prije svojih nasljednika. Signup and view all the answers

Koje od sljedećih svojstava mora imati graf da bi se moglo primijeniti topološko sortiranje?

Graf mora biti usmjeren i acikličan. Signup and view all the answers

Koji postupak se koristi za provođenje topološkog sortiranja?

Određivanje čvorova bez ulaznih lukova i njihovo dodavanje u rezultat. Signup and view all the answers

Koja od sljedećih primjena koristi topološko sortiranje?

Planiranje zadataka gdje su neki zadaci ovisni o drugima. Signup and view all the answers

Koji algoritam je povezan s topološkim sortiranjem?

Algoritam za obilazak u dubinu (DFS). Signup and view all the answers

Što se događa ako graf sadrži cikluse prilikom pokušaja topološkog sortiranja?

Nema mogućnosti topološkog sortiranja. Signup and view all the answers

Kako se topološko sortiranje može primijeniti u računalstvu?

Za izvođenje zadaća u redoslijedu koji zadovoljava ovisnosti. Signup and view all the answers

Koji problem može nastati tijekom topološkog sortiranja?

Moguće je dobiti više od jednog rješenja koja su validna. Signup and view all the answers

U kojem slučaju topološko sortiranje neće biti moguće?

Kada graf sadrži cikluse. Signup and view all the answers

Kojoj vrsti grafova je topološko sortiranje primjenjivo?

Usmjereni aciklični grafovi. Signup and view all the answers

Study Notes

Graf - Struktura podataka

Graf je struktura podataka koja se sastoji od čvorova i lukova koji povezuju čvorove.
Čvorovi mogu biti samostalni.
Graf se koristi u raznim područjima STEM-a, uključujući računalne mreže, društvene mreže, kombinatornu optimizaciju i operacijska istraživanja.
Graf se također koristi kao model podataka u graf-bazama podataka.
Grafovi se mogu prikazati pomoću lista susjednih elemenata ili matrice susjednih elemenata, i mogu biti usmjereni ili neusmjereni, te ciklički ili aciklički.

Primjer grafova u Pythonu

Graf se može implementirati korištenjem rječnika (dictionary) u Pythonu.
Ključ rječnika predstavlja čvor, a vrijednost je lista susjednih čvorova.

Pretraživanje grafova

Postoje dva glavna načina pretraživanja grafova: pretraživanje u dubinu (DFS) i pretraživanje u širinu (BFS).

Vremenska složenost obilaska grafa

Vremenska složenost obilaska grafa, pretraživanja u dubinu i pretraživanja u širinu, ovisi o broju čvorova (V) i broju lukova (E) u grafu. Složenost je O(V + E).

Topologijsko sortiranje

Topologijsko sortiranje uređuje čvorove usmjerenog acikličkog grafa (DAG) tako da, ako postoji luk iz čvora u u čvor v, onda se u pojavljuje prije v u sortiranom redoslijedu.
Često se koristi za zadatke s ovisnostima među aktivnostima.
Postoje algoritmi za nalazenje topološkog sortiranja koristeći DFS.

Čvrsto povezane komponente

Čvrsto povezana komponenta grafa je maksimalni skup čvorova u grafu koji su međusobno povezani.
Čvorovi u jednoj čvrsto povezanoj komponenti su međusobno povezani putem puteva u grafu.
Ovaj pojam je bitan za usmjerene grafove.

Tablice raspršivanja (hash tables)

Tablice raspršivanja (Hash tables) generaliziraju tablice s direktnim adresiranjem.
Koriste se kada se ključevi ne moraju čuvati kao brojevi.
Izračunavanje indeksa pomoću funkcije raspršivanja (hash functions).
U većini implementacija funkcija raspršivanja vraća broj izrađen na osnovu ulaznog ključa.
Tablice raspršivanja su optimizirane za operacija dohvaćanja, dodavanja i brisanja elemenata, tako da u prosjeku postižu linearnu vremensku složenost O(1).
U slučajevima kolizija, tablice raspršivanja koriste različite tehnike za rješavanje kolizija, kao npr. ulančavanje ili otvoreno adresiranje.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Ovaj kviz ispituje tvoje znanje o binarnim stablima i njihovim karakteristikama. Odgovori na pitanja o visini čvorova, balansiranim stablima, te raznim tipovima binarnih stabala. Provjeri koliko znaš o organizaciji i svojstvima ovih važnih struktura podataka.