Duomenų struktūros: praktiniai klausimai su paaiškinimais

1Kas yra duomenų struktūra

Duomenų struktūra yra duomenų atmintyje organizavimo būdas, kad tam tikros operacijos būtų greitos: elemento radimas, įterpimas, pašalinimas.

Nėra struktūros, kuri būtų greita viskam. Rinktis struktūrą reiškia rinktis, kurios operacijos turi būti pigios. Jų kaina užrašoma O didžiuoju, kur n yra elementų skaičius.

Du pagrindiniai statybiniai blokai yra masyvas ir susietasis sąrašas.

Masyvas saugo elementus viename atminties bloke, vieną po kito. Kompiuteris gali apskaičiuoti, kur yra elementas i, todėl a[i] skaitymas trunka O(1). Įterpimas pradžioje reiškia visų elementų postūmį: O(n).

Susietasis sąrašas saugo kiekvieną elementą mazge su rodykle į kitą mazgą. Paskutinė rodyklė yra null. Įterpimas į pradžią (h) pakeičia tik vieną rodyklę: O(1). Bet norint pasiekti elementą i, reikia sekti i rodyklių: O(n).

Dvikryptis susietasis sąrašas turi ir rodyklę į ankstesnį mazgą, todėl galima eiti abiem kryptimis.

2Dėklai ir eilės

Dėklas (stekas) yra kaip lėkščių krūva: pridedate ir šalinate tik viršuje. Paskutinis įdėtas elementas išimamas pirmas: LIFO.

• push uždeda elementą viršuje, pop pašalina viršutinį elementą, peek perskaito viršutinį jo nešalindamas. Visos yra O(1).
• Naudojimas: redaktoriaus atšaukimo funkcija, programos iškvietimų dėklas, skliaustų subalansuotumo tikrinimas, paieška gilyn.

Eilė yra kaip eilė prie kasos: prisijungiate gale ir išeinate priekyje. Pirmas įdėtas elementas išimamas pirmas: FIFO.

• enqueue prideda gale, dequeue pašalina iš priekio. Abi yra O(1).
• Naudojimas: spausdinimo užduotys, laukiantys apdoroti pranešimai, paieška platyn.

Dviguba eilė (deque) leidžia pridėti ir šalinti abiejuose galuose. Prioritetinė eilė visada pirmiausia pašalina didžiausią prioritetą turintį elementą; ji dažniausiai kuriama kaip krūva.

3Medžiai, krūvos, maišos lentelės ir grafai

Medis turi vieną viršutinį mazgą, šaknį. Kiekvienas kitas mazgas turi lygiai vieną tėvą. Mazgai be vaikų yra lapai. Medis su n mazgų turi n − 1 briauną.

Dvejetainiame medyje kiekvienas mazgas turi ne daugiau kaip du vaikus. Dvejetainis paieškos medis (BST) prideda taisyklę: kairiojo pomedžio raktai mažesni už mazgą, dešiniojo pomedžio – didesni.

Paieška BST seka vienu keliu žemyn, todėl kainuoja O(aukštis). Subalansuotas medis (AVL, raudonai juodas) išlaiko aukštį apie log₂ n. Raktai, įterpti surūšiuota tvarka, sudaro n aukščio grandinę.

Krūva yra dvejetainis medis, kuriame kiekvienas tėvas mažesnis už savo vaikus (min-krūva) arba didesnis (maks-krūva). Minimumas ar maksimumas yra šaknyje, o įterpimas ir šalinimas kainuoja O(log n).

Maišos lentelė saugo raktų ir reikšmių poras. Maišos funkcija paverčia raktą indeksu, todėl įterpimas ir paieška vidutiniškai trunka O(1). Du raktai su tuo pačiu indeksu yra kolizija, sprendžiama grandinėmis (sąrašas kiekvienai vietai) arba atvira adresacija (bandoma kita vieta).

Grafas turi viršūnes, sujungtas briaunomis, kurios gali turėti kryptį ar svorį. Jis saugomas kaip gretimumo matrica, O(V²) atminties, arba kaip gretimumo sąrašai, O(V + E).

4Metodas žingsnis po žingsnio

Klausimai dažnai aprašo užduotį ir klausia, kuri struktūra tinka, arba klausia, kaip struktūra atrodo po kelių operacijų.

1. Raskite operaciją, kuri turi būti greita: prieiga pagal poziciją, pagal raktą, naujausias elementas, seniausias elementas, mažiausias elementas ar intervalas.
2. Priskirkite ją struktūrai: indeksas → masyvas, raktas → maišos lentelė, naujausias → dėklas, seniausias → eilė, mažiausias ar didžiausias → krūva, surūšiuota tvarka ar intervalai → subalansuotas paieškos medis.
3. Patikrinkite kitų užduočiai reikalingų operacijų kainą O didžiuoju.
4. Sekimo klausimui atlikite operacijas po vieną ir po kiekvienos užsirašykite būseną.
5. Galutinę būseną patikrinkite pagal struktūros taisyklę: LIFO, FIFO, BST tvarką ar krūvos tvarką.

5Išspręstas pavyzdys

Sekite kiekvieną žingsnį. Pabandykite nuspėti kitą, prieš jį atidarydami.

6Dažnos klaidos

• Painiojami LIFO ir FIFO. Dėklas grąžina naujausią elementą, eilė – seniausią.
• Manoma, kad susietasis sąrašas suteikia greitą prieigą pagal indeksą. Jis turi eiti nuo pradžios.
• Manoma, kad BST visada yra O(log n). Tik subalansuotas medis toks; surūšiuoti įterpimai duoda O(n).
• Pamirštamos maišos lentelės kolizijos. O(1) yra vidurkis, o ne blogiausias atvejis.
• Painiojami apėjimai. Prieš tai (preorder): pirmiausia mazgas. Vidinis (in-order): mazgas viduryje. Po to (postorder): mazgas paskutinis.
• Gretimumo matrica naudojama dideliam retam grafui. Ji eikvoja O(V²) atminties.

7Kaip atrodo egzamino uždaviniai

• Lengvi: pagrindinės sąvokos ir faktai. LIFO ir FIFO, kas yra mazgas, šaknis ar lapas, BST taisyklė, ką daro maišos funkcija.
• Vidutiniai: sąvokų taikymas. Kuri struktūra tinka užduočiai, push ir pop arba BST įterpimų rezultatas, medžių apėjimai, maišos lentelė su tiesiniu zondavimu, kainos O didžiuoju.
• Sunkūs: atvejai ir analizė. Subalansuoti medžiai, krūvos masyvuose, B-medžiai, prefiksų medžiai (trie), union-find, Bloom filtrai ir sprendimai, tokie kaip LRU talpykla.

Krūvai, saugomai masyve nuo indekso 0, indekso i vaikai yra ties 2i + 1 ir 2i + 2, o jo tėvas – ties ⌊(i − 1) / 2⌋.