Dimensione
Confronti

Operazione Medio Caso peggiore

Ulteriori informazioni sulle strutture dati

Visualizzatore di strutture dati

Una struttura dati è un modo di conservare i dati perché le domande più frequenti abbiano una risposta rapida. Scegli una delle undici strutture classiche, dalla pila all'albero rosso-nero, scrivi un valore e premi un'operazione. Ogni passo si svolge sullo schermo: quale nodo viene confrontato, quale collegamento cambia, perché un albero ruota o un valore risale, con una frase che dice che cosa succede. Le tessere contano il lavoro di ogni operazione e una tabella ne indica il tempo di esecuzione. Scegli una struttura, scrivi un valore e premi un'operazione. Ogni operazione si svolge passo per passo: i nodi evidenziati mostrano che cosa viene confrontato, spostato o modificato, e la riga sotto l'immagine dice che cosa succede e perché. Indietro, Passo, Riproduci e Fine ripercorrono i passi. Riempi a caso e Svuota ricominciano da capo, e Annulla ritira un'operazione. Le tessere mostrano la dimensione, l'altezza degli alberi, il lavoro dell'ultima operazione (confronti, sondaggi o collegamenti al genitore seguiti) e un valore che conta per la struttura; la tabella elenca il tempo di esecuzione di ogni operazione.

Come funziona

  1. Scegli una struttura, per esempio un albero binario di ricerca, una tabella hash o un trie. Parte con un contenuto casuale; Riempi a caso e Svuota ricominciano da capo.
  2. Scrivi un valore e premi un'operazione: push, accoda, inserisci, elimina, cerca, una visita, union o find. I passi scorrono da soli; Indietro, Passo, Riproduci e Fine li ripercorrono.
  3. Leggi nella riga sotto l'immagine che cosa fa ogni passo, osserva nelle tessere la dimensione, l'altezza e il lavoro dell'ultima operazione, e confronta i tempi di esecuzione nella tabella.

Liste, pile e code

Le strutture più semplici tengono gli elementi in fila. Una pila lavora solo a un capo, quindi l'ultimo elemento entrato è il primo a uscire, come una pila di piatti; una coda aggiunge in fondo e preleva dal fronte, come una fila allo sportello. Qui la coda vive in un buffer circolare: fronte e fondo girano attorno a un array fisso e ripartono dall'inizio dopo la fine, e quando è pieno gli elementi vengono copiati in uno grande il doppio. Una lista concatenata collega i nodi con puntatori, quindi inserire in testa non costa nulla, ma trovare la coda o un indice significa seguire i collegamenti uno per uno.

Alberi, heap, tabelle hash e insiemi

Un albero binario di ricerca tiene i valori più piccoli a sinistra e quelli più grandi a destra, così una ricerca dimezza i candidati a ogni passo, purché l'albero resti folto. Gli alberi AVL e rosso-neri se ne occupano, con rotazioni che puoi guardare e che hanno il nome del loro caso. Un heap tiene in cima solo il valore più piccolo o più grande, che è tutto ciò di cui ha bisogno una coda di priorità. Una tabella hash salta direttamente a un bucket calcolato dalla chiave e deve gestire le collisioni; un trie condivide i prefissi delle parole; union-find dice in tempo quasi costante se due elementi appartengono allo stesso insieme.

Domande frequenti

Quale struttura dati dovrei usare?

Dipende dalle domande che fai più spesso. Una pila o una coda quando gli elementi vengono trattati nell'ordine di arrivo o in quello inverso; una tabella hash per cercare una chiave; un albero di ricerca bilanciato come un AVL o un rosso-nero quando servono anche le chiavi in ordine o la chiave più vicina; un heap quando serve sempre e solo l'elemento più piccolo o più grande; un trie per parole e prefissi; union-find per seguire gruppi che si fondono.

Che differenza c'è tra un albero AVL e un albero rosso-nero?

Entrambi tengono basso un albero binario di ricerca, così ogni ricerca, inserimento e cancellazione richiede un tempo proporzionale a log n. Un albero AVL è bilanciato in modo più rigido, con le altezze dei due lati di ogni nodo distanti al massimo uno, quindi le ricerche sono un po' più veloci. Un albero rosso-nero concede più margine e richiede meno rotazioni quando cambia, ed è per questo che molte librerie standard lo usano per mappe e insiemi ordinati.

Perché una tabella hash può essere lenta nel caso peggiore?

Se molte chiavi finiscono nello stesso bucket, una ricerca deve controllarle una per una, proprio come in una lista. Una buona funzione hash distribuisce le chiavi in modo uniforme e la tabella cresce prima di riempirsi troppo, così una ricerca richiede in media tempo costante. Prova una tabella di dimensione 10 con numeri che finiscono con la stessa cifra, o parole che sono anagrammi l'una dell'altra, per vedere le collisioni accumularsi.

Che cosa significano i numeri accanto ai nodi AVL?

Sono fattori di bilanciamento: l'altezza del sottoalbero sinistro di un nodo meno quella del suo sottoalbero destro. In un albero AVL ogni fattore deve essere −1, 0 o +1. Quando un inserimento o una cancellazione ne porta uno a +2 o −2, l'albero ruota in quel nodo; il caso (LL, RR, LR o RL) dice da che parte pende l'altezza in più e decide tra una e due rotazioni.

Viene inviato qualcosa a un server?

No. Ogni operazione viene eseguita nel tuo browser e il contenuto di ogni struttura è salvato nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor