Structurile de date explicate

Orice program își păstrează datele undeva, iar felul în care o face decide ce este rapid și ce este lent. O listă de un milion de nume poate fi parcursă nume cu nume sau ordonată astfel încât douăzeci de comparații să găsească orice nume. Structurile de date sunt astfel de organizări: câteva idei, cele mai multe mai vechi decât calculatorul personal, care se află în fiecare bază de date, sistem de operare, browser și joc.

Un arbore binar de căutare colorat în roșu și negru, o stivă de cutii, un rând de compartimente de dispersie cu un lanț de chei în coliziune și săgeți care leagă nodurile unei liste
Un arbore binar de căutare colorat în roșu și negru, o stivă de cutii, un rând de compartimente de dispersie cu un lanț de chei în coliziune și săgeți care leagă nodurile unei liste

La ce folosește o structură de date

O structură de date se alege după întrebările la care trebuie să răspundă. Jurnalul de apeluri al unui telefon vrea întâi ultimul apel, o imprimantă întâi cea mai veche lucrare, un dicționar sensul unui cuvânt dintre o sută de mii, un planificator de traseu cea mai apropiată intersecție nevizitată. Fiecare structură face unele operații rapide renunțând la altele, iar notația O mare descrie acest schimb: O(1) înseamnă că timpul nu crește cu numărul n de elemente, O(log n) că dublarea lui n adaugă un pas, iar O(n) că timpul crește proporțional cu n.

Stive, cozi și deque

O stivă adaugă și scoate la același capăt: ultimul intrat, primul ieșit. Istoricul de anulare, butonul Înapoi și apelurile unui program în execuție sunt stive. O coadă adaugă în spate și scoate din față: primul intrat, primul ieșit, ca apăsările de taste sau o coadă de tipărire. Un deque permite ambele lucruri la ambele capete. Toate trei durează un timp constant pe operație. O coadă este adesea ținută într-un buffer circular, un tablou fix în care fața și spatele trec de la ultima poziție înapoi la început; când se umple, elementele sunt copiate într-un tablou de două ori mai mare. Copierea costă O(n), dar se întâmplă atât de rar încât fiecare operație costă totuși O(1) în medie, ceea ce se numește o limită amortizată.

Liste înlănțuite

O listă înlănțuită păstrează fiecare valoare într-un nod cu un pointer spre nodul următor. Inserarea sau ștergerea schimbă doar unul sau doi pointeri, fără să mute nimic, dar nu se poate sări la al zecelea nod: se urmează legăturile de la cap. O listă care își păstrează doar capul ajunge la coadă în O(n) pași; listele reale țin de obicei și un pointer la coadă, iar cele dublu înlănțuite unul înapoi, și așa se construiesc istoricul unui browser sau o memorie cache LRU.

Arbori binari de căutare

Un arbore binar de căutare ține, la fiecare nod, valorile mai mici în subarborele stâng și pe cele mai mari în cel drept. O căutare compară și merge la stânga sau la dreapta, iar o parcurgere în inordine citește valorile sortate. Ștergerea unei frunze înseamnă pur și simplu scoaterea ei, un nod cu un copil este înlocuit de acel copil, iar un nod cu doi copii de succesorul său în inordine, cea mai mică valoare din subarborele drept. Toate acestea durează un timp proporțional cu înălțimea arborelui: aproximativ log n când arborele este stufos, dar n când valorile vin sortate și arborele degenerează într-o listă.

Arbori AVL și roșu-negri

Arborii autoechilibrați își repară forma după fiecare schimbare. Un arbore AVL, inventat de Adelson-Velski și Landis în 1962, păstrează înălțimile celor doi subarbori ai fiecărui nod la cel mult unu distanță; când factorul de echilibru al unui nod ajunge la ±2, o rotație (cazurile LL și RR) sau două (LR și RL) refac echilibrul. Un arbore roșu-negru își colorează nodurile astfel încât rădăcina să fie neagră, niciun nod roșu să nu aibă un copil roșu și fiecare drum în jos să treacă prin același număr de noduri negre, ceea ce ține cel mai lung drum de cel mult două ori mai lung decât cel mai scurt. Se repară prin recolorare și cel mult câteva rotații și este arborele din TreeMap în Java, std::map în C++ și planificatorul Linux.

Heapuri și cozi de priorități

Un heap binar este un arbore binar complet păstrat într-un tablou, fără niciun pointer: copiii poziției i se află la 2i + 1 și 2i + 2. Într-un heap minim, fiecare părinte este cel mult cât copiii săi, deci cea mai mică valoare este mereu în rădăcină. O valoare nouă merge la sfârșit și urcă peste părinții mai mari; extragerea rădăcinii aduce ultima valoare sus și o coboară. Ambele costă O(log n), iar un tablou întreg poate deveni heap în O(n). Heapurile pun în mișcare cozile de priorități din drumurile minime ale lui Dijkstra, din simulările de evenimente și din planificatoarele sistemelor de operare, și dau sortarea heapsort.

Tabele de dispersie

O tabelă de dispersie transformă o cheie într-un indice de tablou cu o funcție de dispersie și merge direct acolo. Chei diferite pot ajunge la același indice: o coliziune. Înlănțuirea ține o mică listă în fiecare compartiment; adresarea deschisă, ca sondarea liniară, încearcă pozițiile următoare până găsește una liberă și, la ștergerea unei chei, trebuie să lase o piatră funerară pentru ca, mai târziu, căutările să continue sondarea. Cu o funcție de dispersie bună și un factor de încărcare (chei pe compartiment) ținut jos prin creșterea tabelei, inserarea, căutarea și ștergerea costă în medie O(1). O funcție slabă, ca adunarea codurilor caracterelor unui cuvânt, trimite anagramele în același compartiment. Tabelele de dispersie stau în spatele dict din Python, al obiectelor JavaScript și al indecșilor bazelor de date.

Trie și union-find

Un trie, sau arbore de prefixe, păstrează șirurile câte un caracter pe nivel, așa că cuvintele care încep la fel împart un drum, iar un nod marchează unde se termină un cuvânt. Găsirea unui cuvânt de lungime L durează L pași, oricâte cuvinte ar fi păstrate, iar toate cuvintele cu un prefix dat stau într-un singur subarbore: așa funcționează completarea automată și corectoarele ortografice. Union-find ține elementele în mulțimi disjuncte, fiecare un arbore a cărui rădăcină dă numele mulțimii. Find urmează legăturile spre părinte până la rădăcină; union agață o rădăcină sub alta. Cu reuniune după rang și comprimarea drumului, o serie lungă de operații costă un timp aproape constant pe operație, inversa funcției Ackermann α(n), care este cel mult 4 pentru orice n realist. Algoritmul lui Kruskal pentru arborele parțial de cost minim se sprijină pe ea.

Întrebări frecvente

Care este diferența dintre un tablou și o listă înlănțuită?

Un tablou își ține elementele unul lângă altul în memorie, deci orice poziție se atinge imediat, dar inserarea la mijloc înseamnă mutarea a tot ce urmează. O listă înlănțuită poate insera oriunde schimbând pointeri, dar atingerea unei poziții înseamnă mers de la cap. Tablourile folosesc și mult mai bine memoria cache a procesorului, de aceea în practică sunt de obicei mai rapide.

Ce înseamnă timp amortizat?

Costul mediu pe operație într-o serie lungă, chiar dacă o singură operație este uneori scumpă. Un buffer circular care se dublează când se umple copiază din când în când toate cele n elemente, dar pentru că copierile devin tot mai rare pe măsură ce bufferul crește, n adăugări costă în total O(n), adică O(1) fiecare în medie.

Un heap este același lucru cu un arbore binar de căutare?

Nu. Un arbore binar de căutare așază fiecare subarbore stâng înaintea nodului său și fiecare subarbore drept după el, deci poate lista toate valorile în ordine și găsi repede orice valoare. Un heap promite doar că fiecare părinte vine înaintea copiilor săi, ceea ce ajunge pentru a găsi imediat minimul sau maximul, dar nu pentru a căuta o valoare oarecare.

Cum știe union-find dacă două elemente sunt legate?

Urmează legăturile spre părinte de la fiecare element până la rădăcina arborelui său. Dacă amândouă ajung la aceeași rădăcină, sunt în aceeași mulțime. Comprimarea drumului face apoi ca fiecare nod de pe drum să arate direct spre rădăcină, așa că următoarea întrebare despre ele durează un singur pas.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Deschideți vizualizatorul de structuri de date