Dimensiune
Comparații

Operație Mediu Cel mai rău caz

Mai multe informații despre structurile de date

Vizualizator de structuri de date

O structură de date este un mod de a păstra datele astfel încât întrebările puse cel mai des să primească repede răspuns. Alegeți una dintre cele unsprezece structuri clasice, de la stivă la arborele roșu-negru, scrieți o valoare și apăsați o operație. Fiecare pas se derulează pe ecran: ce nod se compară, ce legătură se schimbă, de ce un arbore se rotește sau o valoare urcă, cu o propoziție care spune ce se întâmplă. Plăcuțele numără munca fiecărei operații, iar un tabel îi dă timpul de execuție. Alegeți o structură, scrieți o valoare și apăsați o operație. Fiecare operație se derulează pas cu pas: nodurile evidențiate arată ce se compară, se mută sau se schimbă, iar rândul de sub imagine spune ce se întâmplă și de ce. Înapoi, Pas, Redă și Sfârșit parcurg din nou pașii. Umplere aleatorie și Golire o iau de la capăt, iar Anulare retrage o operație. Plăcuțele arată dimensiunea, înălțimea arborilor, munca ultimei operații (comparații, sondări sau legături spre părinte urmate) și o cifră care contează pentru structură; tabelul dă timpul de execuție al fiecărei operații.

Cum funcționează

  1. Alegeți o structură, de pildă un arbore binar de căutare, o tabelă de dispersie sau un trie. Pornește cu un conținut aleatoriu; Umplere aleatorie și Golire o iau de la capăt.
  2. Scrieți o valoare și apăsați o operație: push, adăugare în coadă, inserare, ștergere, căutare, o parcurgere, union sau find. Pașii se derulează singuri; Înapoi, Pas, Redă și Sfârșit îi parcurg din nou.
  3. Citiți pe rândul de sub imagine ce face fiecare pas, urmăriți pe plăcuțe dimensiunea, înălțimea și munca ultimei operații și comparați timpii de execuție din tabel.

Liste, stive și cozi

Cele mai simple structuri țin elementele în șir. O stivă lucrează doar la un capăt, deci ultimul element intrat iese primul, ca o stivă de farfurii; o coadă adaugă în spate și scoate din față, ca un rând la ghișeu. Aici coada stă într-un buffer circular: fața și spatele se rotesc în jurul unui tablou fix și o iau de la început după sfârșit, iar când bufferul se umple, elementele sunt copiate într-unul de două ori mai mare. O listă înlănțuită leagă nodurile prin pointeri, deci inserarea la cap nu costă nimic, dar pentru a găsi coada sau un indice trebuie urmate legăturile una câte una.

Arbori, heapuri, tabele de dispersie și mulțimi

Un arbore binar de căutare ține valorile mai mici la stânga și pe cele mai mari la dreapta, așa că o căutare înjumătățește candidații la fiecare pas, cât timp arborele rămâne stufos. Arborii AVL și roșu-negri au grijă de asta, prin rotații pe care le puteți urmări și care poartă numele cazului lor. Un heap ține sus doar valoarea cea mai mică sau cea mai mare, și de mai mult nu are nevoie o coadă de priorități. O tabelă de dispersie sare direct la un compartiment calculat din cheie și trebuie să se descurce cu coliziunile; un trie împarte prefixele cuvintelor; union-find spune în timp aproape constant dacă două elemente aparțin aceleiași mulțimi.

Întrebări frecvente

Ce structură de date ar trebui să folosesc?

Depinde de întrebările pe care le puneți cel mai des. O stivă sau o coadă când elementele sunt tratate în ordinea sosirii sau invers; o tabelă de dispersie pentru a căuta o cheie; un arbore de căutare echilibrat, ca un AVL sau un roșu-negru, când aveți nevoie și de chei în ordine sau de cheia cea mai apropiată; un heap când aveți nevoie mereu doar de cel mai mic sau cel mai mare element; un trie pentru cuvinte și prefixe; union-find pentru a urmări grupuri care se unesc.

Care este diferența dintre un arbore AVL și un arbore roșu-negru?

Amândoi păstrează un arbore binar de căutare puțin adânc, așa că fiecare căutare, inserare și ștergere durează un timp proporțional cu log n. Un arbore AVL este echilibrat mai strict, cu înălțimile celor două părți ale fiecărui nod la cel mult unu distanță, deci căutările sunt puțin mai rapide. Un arbore roșu-negru permite mai multă libertate și cere mai puține rotații la schimbări, de aceea multe biblioteci standard îl folosesc pentru dicționarele și mulțimile sortate.

De ce poate fi lentă o tabelă de dispersie în cel mai rău caz?

Dacă multe chei ajung în același compartiment, o căutare trebuie să le verifice una câte una, exact ca într-o listă. O funcție de dispersie bună împrăștie cheile uniform, iar tabela crește înainte să se umple prea tare, așa că o căutare durează în medie un timp constant. Încercați o tabelă de dimensiune 10 cu numere care se termină în aceeași cifră sau cuvinte care sunt anagrame unele ale altora și vedeți cum se adună coliziunile.

Ce înseamnă numerele de lângă nodurile AVL?

Sunt factori de echilibru: înălțimea subarborelui stâng al unui nod minus cea a subarborelui său drept. Într-un arbore AVL, fiecare factor trebuie să fie −1, 0 sau +1. Când o inserare sau o ștergere face ca unul să devină +2 sau −2, arborele se rotește la acel nod; cazul (LL, RR, LR sau RL) spune încotro se înclină înălțimea în plus și decide între una și două rotații.

Se trimite ceva la un server?

Nu. Fiecare operație rulează în browserul dumneavoastră, iar conținutul fiecărei structuri este salvat în stocarea locală a acestui browser.

Ești gata să încerci?

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

Mergi la editor