V tej vadnici boste spoznali strukturo drevesnih podatkov. Spoznali boste tudi različne vrste dreves in terminologije, ki se uporabljajo v drevesu.
Drevo je nelinearna hierarhična podatkovna struktura, ki jo sestavljajo vozlišča, povezana z robovi.
Drevo
Zakaj struktura drevesnih podatkov?
Druge podatkovne strukture, kot so nizi, povezani seznam, sklad in čakalna vrsta, so linearne podatkovne strukture, ki zaporedno shranjujejo podatke. Da bi izvedli katero koli operacijo v linearni podatkovni strukturi, se časovna zapletenost povečuje s povečanjem velikosti podatkov. Toda v današnjem računalniškem svetu to ni sprejemljivo.
Različne drevesne strukture podatkov omogočajo hitrejši in enostavnejši dostop do podatkov, saj gre za nelinearno podatkovno strukturo.
Drevesne terminologije
Vozlišče
Vozlišče je entiteta, ki vsebuje ključ ali vrednost in kaže na svoja podrejena vozlišča.
Zadnja vozlišča vsake poti se imenujejo listna vozlišča ali zunanja vozlišča, ki ne vsebujejo povezave / kazalca na podrejena vozlišča.
Vozlišče, ki ima vsaj podrejeno vozlišče, se imenuje notranje vozlišče .
Rob
Je povezava med katerima koli vozliščema.
Vozlišča in robovi drevesa
Korenina
Je najvišje vozlišče drevesa.
Višina vozlišča
Višina vozlišča je število robov od vozlišča do najglobljega lista (tj. Najdaljša pot od vozlišča do listnega vozlišča).
Globina vozlišča
Globina vozlišča je število robov od korena do vozlišča.
Višina drevesa
Višina drevesa je višina korenskega vozlišča ali globina najglobljega vozlišča.
Višina in globina vsakega vozlišča v drevesu
Stopnja vozlišča
Stopnja vozlišča je skupno število vej tega vozlišča.
Gozd
Zbirka ločenih dreves se imenuje gozd.
Ustvarjanje gozda iz drevesa
Gozd lahko ustvarite z rezanjem korena drevesa.
Vrste dreves
- Binarno drevo
- Binarno drevo iskanja
- Drevo AVL
- B-Tree
Prehod dreves
Če želite izvesti katero koli operacijo na drevesu, morate doseči določeno vozlišče. Algoritem prečkanja drevesa pomaga pri obisku zahtevanega vozlišča v drevesu.
Če želite izvedeti več, obiščite drevesni prehod.
Drevesne aplikacije
- Drevesa binarnega iskanja (BST) se uporabljajo za hitro preverjanje, ali je element prisoten v nizu ali ne.
- Kup je nekakšno drevo, ki se uporablja za sortiranje kupa.
- Spremenjena različica drevesa, imenovano Tries, se v sodobnih usmerjevalnikih uporablja za shranjevanje informacij o usmerjanju.
- Večina priljubljenih baz podatkov uporablja B-drevesa in T-drevesa, ki so različice drevesne strukture, ki smo se je naučili zgoraj, za shranjevanje njihovih podatkov
- Prevajalniki uporabljajo sintaksno drevo za preverjanje skladnje vsakega programa, ki ga napišete.
