3 pažangios duomenų struktūros, kurias turėtų žinoti kiekvienas programuotojas

Pamatysite, kad duomenų struktūrų naudojimas yra gana dažnas programuotojo atvejis, todėl norint sėkmingai dirbti, labai svarbu mokėti dirbti su pagrindinėmis duomenų struktūromis, tokiomis kaip dvejetainiai medžiai, krūvos ir eilės.

Bet jei norite patobulinti savo įgūdžius ir išsiskirti iš minios, taip pat norėsite susipažinti su pažangiomis duomenų struktūromis.

Išplėstinės duomenų struktūros yra esminis duomenų mokslo komponentas, padedantis išvalyti neefektyvų valdymą ir saugoti didelius duomenų rinkinius. Programinės įrangos inžinieriai ir duomenų mokslininkai nuolat naudoja pažangias duomenų struktūras kurdami algoritmus ir programinę įrangą.

Skaitykite toliau, kai aptariame pažangias duomenų struktūras, apie kurias turėtų žinoti kiekvienas kūrėjas.

1. Fibonačio krūva

Jei jau skyrėte laiko mokytis duomenų struktūrų, turite būti susipažinę su dvejetainėmis krūvomis. Fibonačio krūvos yra gana panašios, ir tai seka min-krūva arba maksimalus krūvas savybių. Galite galvoti apie Fibonačio krūvą kaip medžių rinkinį, kuriame minimalios arba didžiausios vertės mazgas visada yra šaknyje.

Krūva taip pat atitinka Fibonačio savybę, kad mazgas n turės bent F(n+2) mazgai. Fibonačio krūvoje kiekvieno mazgo šaknys yra susietos, paprastai per apskritą dvigubai susietą sąrašą. Tai leidžia ištrinti mazgą ir sujungti du sąrašus tik per O (1) laiką.

Susijęs: Eilių ir prioritetinių eilių supratimo vadovas pradedančiajam

Fibonačio krūvos yra daug lankstesnės nei dvejetainės ir dvinarios krūvos, todėl jos yra naudingos įvairiose srityse. Dijkstra algoritme jos dažniausiai naudojamos kaip prioritetinės eilės, siekiant žymiai pagerinti algoritmo veikimo laiką.

2. AVL medis

AVL (Adelson-Velsky ir Landis) medžiai yra savaime balansuojantys dvejetainiai paieškos medžiai. Standartiniai dvejetainiai paieškos medžiai gali būti iškreipti ir jų laiko sudėtingumas blogiausiu atveju yra O(n), todėl jie yra neveiksmingi realaus pasaulio programoms. Savaime balansuojantys medžiai automatiškai pakeičia savo struktūrą, kai pažeidžiama balansavimo savybė.

AVL medyje kiekviename mazge yra papildomas atributas, kuriame yra jo balansavimo koeficientas. Pusiausvyros koeficientas yra vertė, gauta atėmus kairiojo pomedžio aukštį iš dešiniojo pomedžio tame mazge. AVL medžio savaiminio balansavimo savybė reikalauja, kad balanso koeficientas visada būtų -1, 0 arba 1.

Jei pažeidžiama savaiminio balansavimo savybė (balanso koeficientas), AVL medis pasuka savo mazgus, kad išsaugotų balanso koeficientą. AVL medyje naudojami keturi pagrindiniai pasukimai – sukimas į dešinę, pasukimas į kairę, pasukimas į kairę į dešinę ir sukimas į dešinę į kairę.

AVL medžio savaiminio balansavimo savybė pagerina blogiausio atvejo laiko sudėtingumą iki tik O (logn), o tai yra žymiai efektyvesnė, palyginti su dvejetainio paieškos medžio našumu.

3. Raudonas-Juodas medis

Raudonai juodas medis yra dar vienas savaime balansuojantis dvejetainis paieškos medis, kuris naudoja papildomą bitą kaip savaiminio balansavimo savybę. Antgalis paprastai vadinamas raudonu arba juodu, taigi ir pavadinimas raudonai juodas medis.

Kiekvienas raudonos-juodos spalvos mazgas yra raudonas arba juodas, tačiau šakninis mazgas visada turi būti juodas. Negali būti dviejų gretimų raudonų mazgų, o visi lapų mazgai turi būti juodi. Šios taisyklės naudojamos siekiant išsaugoti medžio savibalansą.

Susijęs: Algoritmai, kuriuos turėtų žinoti kiekvienas programuotojas

Priešingai nei dvejetainės paieškos medžiai, raudonai juodi medžiai turi maždaug O (logn) efektyvumą, todėl jie yra daug efektyvesni. Tačiau AVL medžiai yra daug labiau subalansuoti dėl galutinės savaime išsibalansuojančios savybės.

Pagerinkite savo duomenų struktūras

Pažangių duomenų struktūrų žinojimas gali labai pakeisti darbo pokalbius ir gali būti veiksnys, skiriantis jus nuo konkurentų. Kitos išplėstinės duomenų struktūros, į kurias turėtumėte atkreipti dėmesį, yra n-medžiai, grafikai ir atskirti rinkiniai.

Idealios duomenų struktūros nustatymas tam tikram scenarijui yra dalis to, kas daro gerą programuotoją puikiu.

6 duomenų struktūros, kurias turėtų žinoti kiekvienas programuotojas

Duomenų struktūros yra pagrindinė programinės įrangos inžinerijos dalis. Štai keletas svarbių duomenų struktūrų, kurias turėtų žinoti kiekvienas programuotojas.

Skaitykite toliau

Apie autorių