Alberi, alberi rossi e neri

"Ciao, Amico!"

"Ciao Rishi!"

"Ho trovato i miei vecchi appunti laggiù e ho preparato del materiale interessante per te. Penso che ti interesserà ascoltarlo."

"Sentiamo. Trovi sempre qualcosa di interessante che poi si rivela molto utile."

"OK. Oggi voglio parlarti degli alberi , quindi inizierò con i grafici ."

" Un grafico è un sistema di punti e linee che li collegano. I punti sono chiamati i vertici del grafico e le linee sono chiamate i bordi del grafico. Ad esempio:"

"Un grafico è molto comodo da usare come modello matematico per vari processi e attività del mondo reale. Per i grafici sono stati inventati molti compiti e algoritmi diversi, quindi vengono utilizzati abbastanza spesso."

"Ad esempio, supponiamo che i vertici siano città e che i bordi siano strade. Quindi cercare la strada più breve tra le città diventa: «dato un grafico, trova il percorso più breve tra due vertici». "

"Ma il percorso da A a B non è sempre uguale al percorso da B ad A. Quindi, a volte è preferibile avere due linee diverse. Per fare ciò, le linee (bordi del grafico) vengono sostituite con frecce. In in altre parole, il grafico può avere due frecce: una da A a B e un'altra da B ad A."

"Se il grafico utilizza frecce, allora si chiama grafo orientato ; se ha solo linee, allora si chiama grafo non orientato ".

"Ogni vertice può avere il proprio numero di spigoli. Un vertice può anche non avere affatto spigoli. Al contrario, un vertice può essere connesso da spigoli a ogni altro vertice.  Se ogni coppia di vertici in un grafo è connessa da uno spigolo, allora è chiamato un grafico completo. "

"Se puoi usare gli spigoli per raggiungere ogni vertice in un grafo, allora si chiama grafo connesso . Un grafo che ha tre vertici separati e nessun spigolo è ancora un grafo, ma lo chiamiamo grafo disconnesso ."

"Per formare un grafo connesso da N vertici, hai bisogno di almeno N-1 spigoli. Questo tipo di grafo è chiamato albero."

"Inoltre, di solito un vertice viene scelto come radice dell'albero e gli altri vengono dichiarati rami. I rami degli alberi che non hanno rami propri sono chiamati foglie . Ad esempio:"

"Se ogni elemento dell'albero ha due figli, allora si chiama albero binario . In altre parole, possono esserci 0 o 2 rami. Puoi vedere un albero binario in alto a destra."

" Un albero è detto albero binario completo quando ogni ramo ha 2 figli e tutte le foglie (vertici senza figli) sono sulla stessa riga."

"Per esempio:"

"Perché sono necessari questi alberi?"

"Oh, gli alberi sono usati in molti posti. In generale, gli alberi binari sono dati strutturati ordinati."

"Che cos'è?"

"Sì, è molto semplice. Memorizziamo un certo valore in ogni vertice. E ogni elemento segue una regola: il valore memorizzato nel figlio destro deve essere maggiore del valore memorizzato nel vertice, e il valore memorizzato nel figlio sinistro deve essere minore del valore memorizzato nel vertice.  Questo ordinamento consente di trovare rapidamente gli elementi dell'albero di cui hai bisogno."

"Puoi chiarire cosa significa?"

"Gli elementi dell'albero sono solitamente ordinati per somma. Supponiamo di avere 7 elementi: 13, 5, 4, 16, 8, 11, 10"

"Ecco come gli elementi vengono aggiunti all'albero."

"Se stiamo cercando il numero 7 in questo albero, allora è così che andrà la ricerca"

"0) Inizia dalla radice."

"1a) 7 è uguale a 13? No"

"1b) 7 è maggiore di 13? No, quindi passiamo al sottoalbero di sinistra."

"2a) 7 è uguale a 5? No."

"2b) 7 è maggiore di 5? Sì, quindi ci spostiamo nel sottoalbero di destra."

"3a) 7 è uguale a 8? No"

"3b) 7 è maggiore di 8? No, quindi passiamo al sottoalbero di sinistra."

"4a) Non esiste un sottoalbero sinistro, il che significa che il numero 7 non è nell'albero."

"Ah. In altre parole, dobbiamo solo controllare i vertici sul percorso dalla radice all'eventuale posizione del numero desiderato. Sì, è davvero veloce."

"Inoltre, se l'albero è bilanciato, dovrai solo passare attraverso circa 20 vertici per cercare un milione di elementi."

"Sono d'accordo, non sono molti."

"Cosa intendi per albero equilibrato?"

"Un albero che non è distorto, cioè che non ha rami lunghi. Ad esempio, se gli elementi fossero già stati ordinati quando abbiamo costruito l'albero, allora avremmo realizzato un albero molto lungo composto da un solo ramo. "

"Hmm. Hai ragione. Quindi cosa facciamo?"

"Come probabilmente avrai già intuito, l'albero più efficiente ha rami che hanno approssimativamente la stessa lunghezza. Quindi ogni confronto scarta la parte più grande del sottoalbero rimanente."

"Quindi, dobbiamo ricostruire l'albero?"

"Sì. Ha bisogno di essere «bilanciato» — per essere reso il più vicino possibile a un albero binario completo."

"Per risolvere questo problema, sono stati inventati gli alberi autobilanciati.  Se l'albero si deforma dopo aver aggiunto un elemento, riordina leggermente gli elementi per rendere tutto OK.  Ecco un esempio di bilanciamento:"

"Alcuni di questi alberi sono noti come alberi rosso -neri ."

"Perché si chiamano rosso-neri?"

"Il loro inventore ha disegnato tutti i vertici usando due colori. Un colore era rosso e l'altro era nero. I diversi vertici obbediscono a regole diverse. Questo costituisce l'intera base per la procedura di bilanciamento."

"Per esempio:"

"Allora quali sono queste regole?"

"1) Un vertice rosso non può essere figlio di un vertice rosso."

"2) La profondità del nero di ogni foglia è la stessa (la profondità del nero si riferisce al numero di vertici neri sul percorso dalla radice)."

"3) La radice dell'albero è nera."

"Non spiegherò come funziona: probabilmente la tua testa sta già esplodendo."

"Sì. Il mio processore emette un po' di fumo."

"Ecco un link per te. Se vuoi, puoi leggere di più qui."

Collegamento a materiale aggiuntivo

"E ora, vai a prenderti una pausa."