Alberi Binari di Ricerca

Un albero binario di ricerca (BST) è una struttura dati ad albero dove ogni nodo contiene un valore, e i nodi sono organizzati in un modo tale che per ogni nodo, tutti i nodi nel suo sottoalbero sinistro hanno valori minori o uguali al suo valore, mentre tutti i nodi nel suo sottoalbero destro hanno valori maggiori.

L'insieme di tutti gli alberi binari di ricerca su un insieme ordinato A è chiamato BRT(A). Questo insieme contiene tutti gli alberi binari di ricerca possibili che possono essere costruiti con gli elementi di A.

Un albero binario di ricerca può essere vuoto (∅) o composto da un nodo radice (a) con un sottoalbero sinistro (l) e un sottoalbero destro (r), dove tutti i nodi in L sono minori di a e tutti i nodi in R sono maggiori di a.

Per visualizzare un albero binario di ricerca, si usa una rappresentazione grafica dove ogni nodo è rappresentato da un cerchio contenente il suo valore. I puntatori sono linee che collegano i nodi, con linee orizzontali per le radici e linee verticali per i sottoalberi.

Ogni nodo in un albero binario di ricerca contiene una key (il suo valore) e due puntatori: left e right. Il puntatore left punta al sottoalbero sinistro, mentre right punta al sottoalbero destro. In alcuni casi, viene aggiunto anche un puntatore parent che punta al padre del nodo.

L'algoritmo di stampa in ordine per un BST visita tutti i nodi dell'albero in ordine crescente dei loro valori. L'algoritmo funziona ricorsivamente visitando prima il sottoalbero sinistro, poi la radice e infine il sottoalbero destro.

Un algoritmo che stampa tutte le chiavi di un albero binario di ricerca in ordine crescente.

Un algoritmo che crea una lista ordinata di tutte le chiavi presenti in un albero binario di ricerca.

Un algoritmo che crea una lista ordinata di tutte le chiavi presenti in un albero binario di ricerca.

Il caso peggiore per l'algoritmo ToList-Inorder (Versione 1) si verifica quando l'albero è completamente sbilanciato a destra o a sinistra.

Un algoritmo che cerca una chiave specifica in un albero binario di ricerca.

L'algoritmo 'Tree-Search(T, x)' cerca un nodo con chiave 'x' in un BST 'T'. Se il nodo è presente, viene restituito; altrimenti, viene restituito 'nil'.

La complessità dell'algoritmo di ricerca in un BST è O(h), dove 'h' è l'altezza dell'albero. Questo perché nell'algoritmo si seguono al massimo 'h' archi.

L'algoritmo 'Tree-Min(T)' restituisce il nodo con la chiave minima in un BST non vuoto 'T'.

La complessità dell'algoritmo di ricerca del minimo è O(h), dove 'h' è l'altezza dell'albero. Questo perché si seguono al massimo 'h' archi verso sinistra.

Il successore di un nodo 'N' in un BST 'T' è il nodo con la chiave minima tra quelle maggiori di 'N.key'.

L'algoritmo 'Tree-Succ(N)' restituisce il successore del nodo 'N' in un BST, se esiste; altrimenti, restituisce 'nil'.

L'inserimento di una chiave 'x' in un BST crea un nuovo nodo con chiave 'x' e lo inserisce nella posizione corretta all'interno dell'albero, preservando la proprietà di ordinamento.

L'inserimento in un BST ha una complessità di O(h), dove 'h' è l'altezza dell'albero. Questo perché per trovare la posizione corretta, potrebbero essere necessari al massimo 'h' confronti.

Un algoritmo che inserisce un nuovo nodo in un albero binario di ricerca mantenendo la proprietà di ordinamento.

Il nodo in cui deve essere inserito un nuovo nodo. Viene determinato durante la ricerca nel BST.

Il processo di ricerca del nodo genitore e del punto esatto dove inserire un nuovo nodo nell'albero.

Il nuovo nodo è sempre inserito come figlio del nodo genitore.

Quando il nuovo nodo ha un valore uguale al nodo corrente, viene ignorato.

L'algoritmo stabilisce se il nuovo nodo deve essere inserito come figlio sinistro o destro del nodo genitore.

La parte dell'algoritmo che effettua l'effettivo inserimento del nuovo nodo in base alla sua posizione

Il nuovo nodo inserito non ha figli iniziali. Un nodo appena inserito è fondamentalmente un nodo foglia.

Se il nodo Z è una foglia, basta eliminare il riferimento al nodo Z nel suo genitore. Se Z è la radice, l'albero diventa vuoto.

Se il nodo Z ha un solo figlio, bisogna agganciare il figlio di Z al genitore di Z.

Se il nodo Z ha due figli, si sostituisce l'etichetta di Z con l'etichetta minima del suo sottoalbero destro. Successivamente si elimina il nodo che conteneva l'etichetta minima, applicando uno dei due metodi precedenti (ha al massimo un figlio).

L'algoritmo 1-Delete(Z, T) rimuove il nodo Z da un albero binario di ricerca T, dove Z ha esattamente un figlio.

L'algoritmo Tree-Delete(Z, T) rimuove il nodo Z da un albero binario di ricerca T. Gestisce tutti i casi di cancellazione (foglie, un figlio, due figli).

Trova il nodo con la chiave minima nel sottoalbero destro di Z.

Sostituisci la chiave di Z con la chiave minima nel sottoalbero destro di Z, quindi elimina il nodo con la chiave minima.

Simulare l'algoritmo Tree-Delete(Z, T) utilizzando un albero binario di ricerca disegnato, per i diversi casi di cancellazione.

Un algoritmo che crea una lista ordinata di tutte le chiavi presenti in un albero binario di ricerca. Viene utilizzata una tecnica ricorsiva per visitare l'albero in ordine, aggiungendo le chiavi alla lista man mano che vengono incontrate.

Il caso peggiore per l'algoritmo ToList-Inorder si verifica quando l'albero è completamente sbilanciato a destra o a sinistra. In questo caso, l'algoritmo deve eseguire un numero di operazioni Append pari al numero di nodi nell'albero, portando a una complessità temporale di O(n^2).

Un algoritmo che visita un albero binario di ricerca in modo iterativo, cercando una chiave specifica in esso. A differenza della ricerca ricorsiva, mantiene una traccia esplicita del percorso al nodo corrente e della direzione successiva da prendere.

Un algoritmo che rimuove un nodo da un albero binario di ricerca, mantenendo la proprietà di ordinamento dell'albero. Gestisce diversi casi, inclusi: nodo foglia, nodo con un solo figlio e nodo con due figli.

Il caso peggiore dell'algoritmo per la generazione della lista ordinata delle chiavi in un albero binario di ricerca si verifica quando l'albero è completamente sbilanciato. L'algoritmo deve eseguire un numero di operazioni Append pari al numero di nodi nell'albero, portando a una complessità temporale di O(n^2), dove n è il numero di elementi nell'albero.