Mes skaitome linijines duomenų struktūras, pvz., masyvą, susietą sąrašą, krūvą ir eilę, kurioje visi elementai yra išdėstyti nuosekliai. Skirtingoms duomenų rūšims naudojamos skirtingos duomenų struktūros.

kaip atidaryti paslėptas programas android

Renkantis duomenų struktūrą atsižvelgiama į kai kuriuos veiksnius:

Kokio tipo duomenis reikia saugoti?: Gali būti, kad tam tikra duomenų struktūra geriausiai tiktų tam tikriems duomenims.Operacijų kaina:Jei norime kuo labiau sumažinti operacijų išlaidas dažniausiai atliekamoms operacijoms. Pavyzdžiui, turime paprastą sąrašą, kuriame turime atlikti paieškos operaciją; tada galime sukurti masyvą, kuriame elementai saugomi surūšiuota tvarka, kad atliktume dvejetainė paieška . Dvejetainė paieška paprastame sąraše veikia labai greitai, nes padalija paieškos erdvę į pusę.Atminties naudojimas:Kartais norime duomenų struktūros, kuri naudoja mažiau atminties.

Medis taip pat yra viena iš duomenų struktūrų, vaizduojančių hierarchinius duomenis. Tarkime, kad norime parodyti darbuotojus ir jų pareigas hierarchine forma, tada ją galima pavaizduoti taip, kaip parodyta žemiau:

Aukščiau pateiktas medis rodo organizacijos hierarchija kokios nors įmonės. Aukščiau pateiktoje struktūroje jonas yra generalinis direktorius įmonės, o Jonas turi dvi tiesiogines ataskaitas, pavadintas kaip Steve'as ir Rohanas . Steve'as turi tris tiesioginius pranešimus Lee, Bobas, Ella kur Steve'as yra vadybininkas. Bobas turi du tiesioginius pranešimus Turi ir Ema . Ema turi dvi tiesiogines ataskaitas Tomas ir Raj . Tomas turi vieną tiesioginį pranešimą Bill . Ši ypatinga loginė struktūra žinoma kaip a Medis . Jo struktūra panaši į tikrojo medžio, todėl jis pavadintas a Medis . Šioje struktūroje šaknis yra viršuje, o jo šakos juda žemyn. Todėl galime teigti, kad medžio duomenų struktūra yra efektyvus būdas saugoti duomenis hierarchiniu būdu.

Supraskime kai kuriuos pagrindinius medžio duomenų struktūros punktus.

• Medžio duomenų struktūra apibrėžiama kaip objektų arba objektų, žinomų kaip mazgai, rinkinys, kuris yra susietas, kad atspindėtų arba imituotų hierarchiją.
• Medžio duomenų struktūra yra nelinijinė duomenų struktūra, nes ji nesaugoma nuosekliai. Tai hierarchinė struktūra, nes medžio elementai yra išdėstyti keliais lygiais.
• Medžio duomenų struktūroje aukščiausias mazgas žinomas kaip šakninis mazgas. Kiekviename mazge yra tam tikrų duomenų, o duomenys gali būti bet kokio tipo. Aukščiau pateiktoje medžio struktūroje mazge yra darbuotojo vardas, todėl duomenų tipas būtų eilutė.
• Kiekviename mazge yra tam tikri duomenys ir nuoroda arba nuoroda į kitus mazgus, kurie gali būti vadinami vaikais.

Kai kurie pagrindiniai medžio duomenų struktūroje vartojami terminai.

Apsvarstykite medžio struktūrą, kuri parodyta žemiau:

Aukščiau pateiktoje struktūroje kiekvienas mazgas pažymėtas tam tikru skaičiumi. Kiekviena rodyklė, parodyta aukščiau esančiame paveikslėlyje, yra žinoma kaip a nuoroda tarp dviejų mazgų.

Šaknis:Šakninis mazgas yra aukščiausias medžio hierarchijos mazgas. Kitaip tariant, šakninis mazgas yra tas, kuris neturi pirminio. Aukščiau pateiktoje struktūroje mazgas sunumeruotas 1 medžio šaknies mazgas. Jei mazgas yra tiesiogiai susietas su kitu mazgu, jis būtų vadinamas tėvų ir vaikų ryšiu.Antrinis mazgas:Jei mazgas yra bet kurio mazgo palikuonis, tada mazgas žinomas kaip antrinis mazgas.Tėvas:Jei mazge yra bet kuris pomazgas, tai tas mazgas laikomas pirminiu to pomazgo.Sesuo:Mazgai, turintys tą patį tėvą, yra žinomi kaip broliai ir seserys.Lapo mazgas: -Medžio mazgas, kuriame nėra antrinio mazgo, vadinamas lapo mazgu. Lapo mazgas yra apačioje esantis medžio mazgas. Bendrame medyje gali būti bet koks lapų mazgų skaičius. Lapų mazgai taip pat gali būti vadinami išoriniais mazgais.Vidiniai mazgai:Mazgas turi bent vieną antrinį mazgą, žinomą kaip an vidinis Protėvio mazgas: -Mazgo protėvis yra bet koks pirmtakas, esantis kelyje nuo šaknies iki to mazgo. Šakninis mazgas neturi protėvių. Aukščiau esančiame paveikslėlyje parodytame medyje 1, 2 ir 5 mazgai yra 10 mazgo protėviai.Palikuonis:Tiesioginis nurodyto mazgo įpėdinis yra žinomas kaip mazgo palikuonis. Aukščiau pateiktame paveikslėlyje 10 yra 5 mazgo palikuonis.

Medžio duomenų struktūros ypatybės

Rekursyvi duomenų struktūra:Medis taip pat žinomas kaip a rekursinė duomenų struktūra . Medis gali būti apibrėžtas kaip rekursyvus, nes išskirtas mazgas medžio duomenų struktūroje yra žinomas kaip a šaknies mazgas . Medžio šakniniame mazge yra nuoroda į visas jo pomedžių šaknis. Kairysis pomedis žemiau esančiame paveikslėlyje parodytas geltona spalva, o dešinysis – raudona spalva. Kairysis pomedis gali būti toliau padalintas į pomedžius, rodomus trimis skirtingomis spalvomis. Rekursija reiškia ką nors sumažinti panašiu būdu. Taigi ši rekursinė medžio duomenų struktūros savybė yra įgyvendinama įvairiose programose.
Kraštų skaičius:Jei yra n mazgų, tada būtų n-1 briaunų. Kiekviena rodyklė struktūroje žymi nuorodą arba kelią. Kiekvienas mazgas, išskyrus šakninį mazgą, turės bent vieną įeinančią nuorodą, žinomą kaip briauna. Tėvų ir vaikų santykiams būtų viena nuoroda.Mazgo x gylis:Mazgo x gylis gali būti apibrėžtas kaip kelio ilgis nuo šaknies iki mazgo x. Vienas kraštas sudaro vieną kelio ilgio vienetą. Taigi, mazgo x gylis taip pat gali būti apibrėžtas kaip briaunų tarp šakninio mazgo ir mazgo x skaičius. Šakninio mazgo gylis yra 0.Mazgo x aukštis:Mazgo x aukštį galima apibrėžti kaip ilgiausią kelią nuo mazgo x iki lapo mazgo.

Remiantis medžio duomenų struktūros savybėmis, medžiai skirstomi į įvairias kategorijas.

Medžio įgyvendinimas

Medžio duomenų struktūrą galima sukurti dinamiškai kuriant mazgus rodyklėmis. Atmintyje esantis medis gali būti pavaizduotas taip, kaip parodyta žemiau:

Aukščiau pateiktame paveikslėlyje parodytas medžio duomenų struktūros vaizdas atmintyje. Aukščiau pateiktoje struktūroje mazge yra trys laukai. Antrame lauke saugomi duomenys; pirmame lauke saugomas kairiojo vaiko adresas, o trečiame lauke saugomas dešiniojo vaiko adresas.

Programuojant mazgo struktūrą galima apibrėžti taip:

burbulų rūšiavimas algoritme

 struct node { int data; struct node *left; struct node *right; } 

Pirmiau nurodytą struktūrą galima apibrėžti tik dvejetainiams medžiams, nes dvejetainis medis gali turėti daugiausiai du vaikus, o bendrieji medžiai gali turėti daugiau nei du vaikus. Bendrųjų medžių mazgo struktūra skirsis nuo dvejetainio medžio.

Medžių pritaikymas

Toliau pateikiami medžių pritaikymo būdai:

Natūraliai hierarchinių duomenų saugojimas:Medžiai naudojami duomenims saugoti hierarchinėje struktūroje. Pavyzdžiui, failų sistema. Disko įrenginyje saugoma failų sistema, failas ir aplankas yra natūraliai hierarchinių duomenų pavidalu ir saugomi medžių pavidalu.Sutvarkyti duomenis:Jis naudojamas duomenims tvarkyti, kad būtų galima efektyviai įterpti, ištrinti ir ieškoti. Pavyzdžiui, dvejetainis medis turi logN laiką elemento paieškai.Pabandykite:Tai speciali medžio rūšis, naudojama žodynui saugoti. Tai greitas ir efektyvus dinaminio rašybos tikrinimo būdas.Krūva:Tai taip pat medžio duomenų struktūra, įgyvendinta naudojant masyvus. Jis naudojamas prioritetinėms eilėms įgyvendinti.B medis ir B+ medis:B-Tree ir B+Tree yra medžio duomenų struktūros, naudojamos duomenų bazėse indeksuoti.Maršruto lentelė:Medžio duomenų struktūra taip pat naudojama duomenims saugoti maršruto parinkimo lentelėse maršrutizatoriuose.

Medžio duomenų struktūros tipai

Toliau pateikiami medžio duomenų struktūros tipai:

Bendras medis:Bendrasis medis yra vienas iš medžio duomenų struktūros tipų. Bendrajame medyje mazgas gali turėti 0 arba didžiausią n mazgų skaičių. Nėra jokių apribojimų mazgo laipsniui (mazgų, kuriuos gali turėti mazgas, skaičius). Viršutinis bendro medžio mazgas yra žinomas kaip šakninis mazgas. Pirminio mazgo vaikai žinomi kaip pomedžiai .

Ten gali būti n pomedžių skaičius bendrame medyje. Bendrajame medyje pomedžiai netvarkomi, nes pomedžio mazgai negali būti išdėstyti.
Kiekvienas netuščias medis turi kraštą žemyn, ir šie kraštai yra sujungti su mazgais, žinomais kaip vaiko mazgai . Šakninis mazgas pažymėtas 0 lygiu. Mazgai, turintys tą patį pirminį, yra žinomi kaip broliai ir seserys . Dvejetainis medis :Čia pats dvejetainis pavadinimas siūlo du skaičius, ty 0 ir 1. Dvejetainiame medyje kiekvienas medžio mazgas gali turėti daugiausiai du antrinius mazgus. Čia didžiausias reiškia, ar mazgas turi 0 mazgų, 1 mazgą ar 2 mazgus.

Norėdami sužinoti daugiau apie dvejetainį medį, spustelėkite toliau pateiktą nuorodą:
https://www.javatpoint.com/binary-tree Dvejetainės paieškos medis :Dvejetainis paieškos medis yra nelinijinė duomenų struktūra, kurioje yra prijungtas vienas mazgas n mazgų skaičius. Tai mazgu pagrįsta duomenų struktūra. Mazgas gali būti pavaizduotas dvejetainiame paieškos medyje su trimis laukais, t. y. duomenų dalimi, kairiuoju antruoju ir dešiniuoju antruoju. Mazgas gali būti prijungtas prie dviejų dviejų antrinių mazgų dvejetainiame paieškos medyje, todėl mazge yra du rodyklės (kairysis antrinis ir dešinysis antrinis).
Kiekviename kairiojo pomedžio mazge turi būti mažesnė reikšmė nei šakninio mazgo reikšmė, o kiekvieno dešiniojo pomedžio mazgo reikšmė turi būti didesnė už šakninio mazgo reikšmę.

Mazgas gali būti sukurtas naudojant vartotojo apibrėžtą duomenų tipą, žinomą kaip struktūra, kaip parodyta žemiau:

 struct node { int data; struct node *left; struct node *right; } 

Aukščiau pateikta mazgo struktūra su trimis laukais: duomenų laukas, antrasis laukas yra kairysis mazgo tipo rodyklė, o trečiasis laukas yra dešinioji mazgo tipo žymeklis.

Norėdami sužinoti daugiau apie dvejetainį paieškos medį, spustelėkite toliau pateiktą nuorodą:

pakeisti java eilutėje

https://www.javatpoint.com/binary-search-tree

AVL medis

Tai vienas iš dvejetainio medžio tipų, arba galime sakyti, kad tai yra dvejetainio paieškos medžio variantas. AVL medis atitinka savybę dvejetainis medis taip pat iš dvejetainis paieškos medis . Tai savaime balansuojantis dvejetainis paieškos medis, kurį išrado Adelsonas Velsky Lindas . Čia savaiminis balansavimas reiškia kairiojo pomedžio ir dešiniojo pomedžio aukščių balansavimą. Šis balansas matuojamas pagal balansavimo faktorius .

Mes galime laikyti medį AVL medžiu, jei medis paklūsta dvejetainiam paieškos medžiui ir balansavimo veiksniui. Balansavimo koeficientas gali būti apibrėžtas kaip skirtumas tarp kairiojo pomedžio aukščio ir dešiniojo pomedžio aukščio . Balansavimo koeficiento reikšmė turi būti 0, -1 arba 1; todėl kiekvieno AVL medžio mazgo balansavimo koeficiento reikšmė turėtų būti 0, -1 arba 1.

Norėdami sužinoti daugiau apie AVL medį, spustelėkite toliau pateiktą nuorodą:

https://www.javatpoint.com/avl-tree

Raudonas-Juodas medis

Raudonai juodas medis yra dvejetainis paieškos medis. Red-Black medžio būtina sąlyga yra tai, kad turėtume žinoti apie dvejetainį paieškos medį. Dvejetainiame paieškos medyje kairiojo pomedžio reikšmė turi būti mažesnė už to mazgo reikšmę, o dešiniojo pomedžio vertė turi būti didesnė už to mazgo reikšmę. Kaip žinome, dvejetainės paieškos laiko sudėtingumas vidutiniu atveju yra log₂n, geriausias atvejis yra O(1), o blogiausias – O(n).

kas yra linux failų sistema

Kai atliekama kokia nors operacija su medžiu, norime, kad mūsų medis būtų subalansuotas taip, kad visos operacijos, pvz., paieška, įterpimas, trynimas ir kt., užtruktų mažiau laiko, o visos šios operacijos būtų laiko sudėtingumo. žurnalas₂n.

Raudonai juodas medis yra savaime balansuojantis dvejetainis paieškos medis. AVL medis taip pat yra aukščio balansavimo dvejetainis paieškos medis kodėl mums reikia raudonai juodo medžio . AVL medyje mes nežinome, kiek apsisukimų reikėtų norint subalansuoti medį, tačiau raudonai juodame medyje medžiui subalansuoti reikia daugiausiai 2 apsisukimų. Jame yra vienas papildomas bitas, nurodantis raudoną arba juodą mazgo spalvą, kad būtų užtikrintas medžio balansas.

Slėgio medis

Skaičiavimo medžio duomenų struktūra taip pat yra dvejetainis paieškos medis, kuriame neseniai pasiektas elementas patalpinamas medžio šakninėje padėtyje, atliekant kai kurias sukimo operacijas. Čia svaidymasis reiškia neseniai pasiektą mazgą. Tai yra savibalansas dvejetainis paieškos medis, neturintis aiškios balanso sąlygos, pvz AVL medis.

Gali būti, kad skliauto medžio aukštis nėra subalansuotas, t. y. kairiojo ir dešiniojo pomedžio aukštis gali skirtis, tačiau operacijos medyje vyksta tokia tvarka. Ramus laikas kur n yra mazgų skaičius.

Pjaustymo medis yra subalansuotas medis, tačiau jo negalima laikyti subalansuotu medžiu, nes po kiekvienos operacijos atliekamas sukimas, kuris veda į subalansuotą medį.

Treap

Treap duomenų struktūra atsirado iš medžio ir krūvos duomenų struktūros. Taigi, jis apima tiek medžio, tiek krūvos duomenų struktūrų savybes. Dvejetainėje paieškos medyje kiekvienas kairiojo pomedžio mazgas turi būti lygus arba mažesnis už šakninio mazgo vertę, o kiekvienas dešiniojo submedžio mazgas turi būti lygus arba didesnis už šakninio mazgo reikšmę. Krūvos duomenų struktūroje tiek dešiniajame, tiek kairiajame pomedžiais yra didesni raktai nei šaknyje; todėl galime sakyti, kad šakniniame mazge yra mažiausia reikšmė.

Treap duomenų struktūroje kiekvienas mazgas turi abu Raktas ir prioritetas kur raktas gaunamas iš dvejetainio paieškos medžio, o prioritetas – iš krūvos duomenų struktūros.

linux komandos

The Treap duomenų struktūra atitinka dvi toliau pateiktas savybes:

• Dešinysis mazgo vaikas>=dabartinis mazgas ir kairysis mazgo vaikas<=current node (binary tree)< li>
• Bet kurio pomedžio vaikai turi būti didesni už mazgą (krūvą)

B-medis

B medis yra subalansuotas m-way medis kur m apibrėžia medžio tvarką. Iki šiol skaitėme, kad mazge yra tik vienas raktas, tačiau b-medis gali turėti daugiau nei vieną raktą ir daugiau nei 2 vaikus. Jis visada palaiko surūšiuotus duomenis. Dvejetainiame medyje gali būti, kad lapų mazgai gali būti skirtinguose lygiuose, tačiau b medyje visi lapų mazgai turi būti tame pačiame lygyje.

Jei tvarka yra m, mazgas turi šias savybes:

• Kiekvienas b-medžio mazgas gali turėti maksimumą m vaikai
• Mažiausiai vaikams lapo mazgas turi 0 vaikų, šaknies mazgas turi mažiausiai 2 vaikus, o vidinis mazgas turi ne mažiau kaip m/2 vaikų. Pavyzdžiui, m reikšmė yra 5, o tai reiškia, kad mazge gali būti 5 vaikai, o vidiniuose mazguose gali būti daugiausia 3 vaikai.
• Kiekvienas mazgas turi maksimalų (m-1) raktą.

Šakniniame mazge turi būti bent 1 raktas, o visuose kituose mazguose turi būti bent lubos m/2 minus 1 raktai.