Albero binario di ricerca
Albero binario di ricerca è un esperimento interattivo di Strutture dati, una simulazione gratuita di StudyFi Lab che funziona direttamente nel browser.
In ogni nodo i valori minori stanno a sinistra e quelli maggiori a destra. Ricerca e inserimento seguono quindi un solo percorso dalla radice e costano O(h), dove h è l’altezza dell’albero: in un albero bilanciato h ≈ log₂ n. La cancellazione ha tre casi: una foglia sparisce, un nodo con un figlio viene sostituito dal figlio e un nodo con due figli prende il valore del suo successore in ordine. La visita in ordine elenca i valori ordinati; alberi simili stanno dietro agli indici dei database.
Prova questo: Cancella la radice: ha due figli, quindi vedrai la ricerca del successore. Poi prova «Inserisci valori ordinati»: l’albero degenera in una lista e l’altezza sale a n.
Domande frequenti
Che cosa mostra l’esperimento «Albero binario di ricerca»?
In ogni nodo i valori minori stanno a sinistra e quelli maggiori a destra. Ricerca e inserimento seguono quindi un solo percorso dalla radice e costano O(h), dove h è l’altezza dell’albero: in un albero bilanciato h ≈ log₂ n. La cancellazione ha tre casi: una foglia sparisce, un nodo con un figlio viene sostituito dal figlio e un nodo con due figli prende il valore del suo successore in ordine. La visita in ordine elenca i valori ordinati; alberi simili stanno dietro agli indici dei database.
Come provo «Albero binario di ricerca»?
Cancella la radice: ha due figli, quindi vedrai la ricerca del successore. Poi prova «Inserisci valori ordinati»: l’albero degenera in una lista e l’altezza sale a n.
Studi per una verifica?
Carica i tuoi appunti e StudyFi li trasforma in flashcard, test e podcast.