Šioje pamokoje sužinosite apie medžio duomenų struktūrą. Taip pat sužinosite apie skirtingus medžių tipus ir terminus, naudojamus medžiuose.
Medis yra netiesinė hierarchinė duomenų struktūra, susidedanti iš kraštais sujungtų mazgų.
Medis
Kodėl medžio duomenų struktūra?
Kitos duomenų struktūros, tokios kaip masyvai, susietas sąrašas, kaminas ir eilė, yra linijinės duomenų struktūros, kurios nuosekliai kaupia duomenis. Norint atlikti bet kokią operaciją tiesinėje duomenų struktūroje, laiko sudėtingumas didėja didėjant duomenų dydžiui. Bet tai nepriimtina šiandieniniame skaičiavimo pasaulyje.
Skirtingos medžio duomenų struktūros leidžia greičiau ir lengviau pasiekti duomenis, nes tai yra nelinijinė duomenų struktūra.
Medžių terminijos
Mazgas
Mazgas yra subjektas, kuriame yra raktas arba reikšmė ir nurodymai į antrinius mazgus.
Paskutiniai kiekvieno kelio mazgai vadinami lapų mazgais arba išoriniais mazgais , kuriuose nėra nuorodos / rodyklės su antriniais mazgais.
Mazgas, turintis bent antrinį mazgą, vadinamas vidiniu mazgu .
Briauna
Tai yra ryšys tarp bet kurių dviejų mazgų.
Medžio mazgai ir kraštai
Šaknis
Tai aukščiausias medžio mazgas.
Mazgo aukštis
Mazgo aukštis yra kraštų skaičius nuo mazgo iki giliausio lapo (t. Y. Ilgiausias kelias nuo mazgo iki lapo mazgo).
Mazgo gylis
Mazgo gylis yra kraštų skaičius nuo šaknies iki mazgo.
Medžio aukštis
Medžio aukštis yra šaknies mazgo aukštis arba giliausio mazgo gylis.
Kiekvieno medžio mazgo aukštis ir gylis
Mazgo laipsnis
Mazgo laipsnis yra bendras to mazgo šakų skaičius.
Miškas
Nesusijusių medžių kolekcija vadinama mišku.
Miško kūrimas iš medžio
Galite sukurti mišką, nupjaudami medžio šaknį.
Medžių rūšys
- Dvejetainis medis
- Dvejetainis paieškos medis
- AVL medis
- B medis
Medžių perėjimas
Norėdami atlikti bet kokią operaciją su medžiu, turite pasiekti konkretų mazgą. Medžio perėjimo algoritmas padeda aplankyti reikalingą medžio mazgą.
Norėdami sužinoti daugiau, apsilankykite medžių perėjime.
Medžių programos
- Dvejetainiai paieškos medžiai (BST) naudojami norint greitai patikrinti, ar elementas yra rinkinyje, ar ne.
- Krūva yra tam tikras medis, kuris naudojamas rūšiuoti.
- Modifikuota medžio versija, vadinama „Tries“, naudojama šiuolaikiniuose maršrutizatoriuose, kad būtų saugoma maršruto parinkimo informacija.
- Populiariausiose duomenų bazėse naudojami „B-Trees“ ir „T-Trees“, kurie yra medžių struktūros variantai, kuriuos sužinojome aukščiau, kad išsaugotume jų duomenis
- Kompiliatoriai naudoja sintaksės medį, kad patvirtintų kiekvienos jūsų parašytos programos sintaksę.
