U ovom uputstvu naučit ćete o strukturi podataka stabla. Također ćete naučiti o različitim vrstama stabala i terminologijama koje se koriste u drvetu.
Stablo je nelinearna hijerarhijska struktura podataka koja se sastoji od čvorova povezanih rubovima.
Stablo
Zašto struktura podataka o stablu?
Ostale strukture podataka kao što su nizovi, povezani popis, stog i red su linearne strukture podataka koje sekvencijalno pohranjuju podatke. Da bi se izvela bilo koja operacija u linearnoj strukturi podataka, vremenska složenost raste s povećanjem veličine podataka. Ali, to nije prihvatljivo u današnjem računalnom svijetu.
Različite strukture podataka stabla omogućuju brži i lakši pristup podacima jer je riječ o nelinearnoj strukturi podataka.
Terminologije stabla
Čvor
Čvor je entitet koji sadrži ključ ili vrijednost i pokazuje na svoje podređene čvorove.
Posljednji čvorovi svake staze nazivaju se čvorovi listova ili vanjski čvorovi koji ne sadrže vezu / pokazivač na podređene čvorove.
Čvor koji ima barem podređeni čvor naziva se internim čvorom .
Rub
To je veza između bilo koja dva čvora.
Čvorovi i rubovi stabla
Korijen
To je najviši čvor stabla.
Visina čvora
Visina čvora je broj rubova od čvora do najdubljeg lista (tj. Najduža staza od čvora do čvora lista).
Dubina čvora
Dubina čvora je broj bridova od korijena do čvora.
Visina stabla
Visina stabla je visina korijenskog čvora ili dubina najdubljeg čvora.
Visina i dubina svakog čvora u drvetu
Stupanj čvora
Stupanj čvora je ukupan broj grana tog čvora.
Šuma
Zbirka razdvojenih stabala naziva se šuma.
Stvaranje šume od drveta
Šumu možete stvoriti rezanjem korijena drveta.
Vrste stabla
- Binarno stablo
- Binarno stablo pretraživanja
- AVL stablo
- B-drvo
Prelazak stabla
Da biste izveli bilo koju operaciju na stablu, morate doći do određenog čvora. Algoritam zaokretanja stabla pomaže u posjećivanju potrebnog čvora na stablu.
Da biste saznali više, posjetite obilazak drveta.
Primjene na drvetu
- Binarna stabla za pretraživanje (BST) koriste se za brzu provjeru je li element prisutan u skupu ili ne.
- Hrpa je vrsta drveta koje se koristi za sortiranje hrpe.
- Izmjenjena verzija stabla nazvana Tries koristi se u modernim usmjerivačima za pohranu podataka o usmjeravanju.
- Najpopularnije baze podataka koriste B-drveće i T-drveće, koje su inačice strukture stabla koje smo gore naučili za pohranu njihovih podataka
- Prevoditelji koriste stablo sintakse za provjeru sintakse svakog programa koji napišete.
