Alberi Red Black
Diciamo subito che ho capito gli inserimenti e le varie operazioni per bilanciare tutto. 
[E diciamo pure che penso siano argomenti abbastanza complessi... (Quindi rimangio subito la suddetta riga sovrastante su di cui sopra
) ]
Stavo guardando, direi per diletto, la cancellazione in un albero red black: con gli 8 casi... 4 + 4 direi.
Negli schemi che ho sul libro mi pare che non venga cancellato alcun nodo
A livello di "numero di nodi" NON ci sono mai cambiamenti: muta sulo la struttura con rotazioni e colorazioni varie.
Cosa devo capire? Cioé un'eventuale sostituzione? Per cancellazione intendiamo che un nodo u viene sostituito da un altro v?
[E diciamo pure che penso siano argomenti abbastanza complessi... (Quindi rimangio subito la suddetta riga sovrastante su di cui sopra
) ]Stavo guardando, direi per diletto, la cancellazione in un albero red black: con gli 8 casi... 4 + 4 direi.
Negli schemi che ho sul libro mi pare che non venga cancellato alcun nodo
A livello di "numero di nodi" NON ci sono mai cambiamenti: muta sulo la struttura con rotazioni e colorazioni varie.
Cosa devo capire? Cioé un'eventuale sostituzione? Per cancellazione intendiamo che un nodo u viene sostituito da un altro v?
Risposte
Ciao Giova411 
Prima di entrare nei dettagli bisogna che cerchi di non dimenticare mai un fatto fondamentale con questo tipo di alberi: durante tutte le operazioni di cancellazione/inserimento modifica l'albero deve rimanere bilanciato e preservare le proprietà della colorazione dei nodi. Questa in realtà è la chiave di tutto prima di addentrarsi nei vari casi...
Prima di entrare nei dettagli bisogna che cerchi di non dimenticare mai un fatto fondamentale con questo tipo di alberi: durante tutte le operazioni di cancellazione/inserimento modifica l'albero deve rimanere bilanciato e preservare le proprietà della colorazione dei nodi. Questa in realtà è la chiave di tutto prima di addentrarsi nei vari casi...
Ciao Only!!
Sì si! Rispettare le 4 regole, certo.
Nell'inserimento qualcosa ho capito; ho pure provato qualche esercizietto smarzo di inserimento del nodo nuovo con successiva rotazione. Ma con l'inserimento almeno vedo il nodo, visualizzo dove deve andare e ciclando si rispettano le proprietà (anche se devo risalire ed aggiustare). Il nodo poi nuovo lo VEDO pero'...
La cancellazione di un nodo invece? Dall'albero non si toglie mai ma si sostituisce? O forse è il mio libro che tratta l'argomento in modo superficiale?
Sì si! Rispettare le 4 regole, certo.
Nell'inserimento qualcosa ho capito; ho pure provato qualche esercizietto smarzo di inserimento del nodo nuovo con successiva rotazione. Ma con l'inserimento almeno vedo il nodo, visualizzo dove deve andare e ciclando si rispettano le proprietà (anche se devo risalire ed aggiustare). Il nodo poi nuovo lo VEDO pero'...
La cancellazione di un nodo invece? Dall'albero non si toglie mai ma si sostituisce? O forse è il mio libro che tratta l'argomento in modo superficiale?
In realtà quello che viene mostrato nei vari casi della cancellazione non è esattamente la cancellazione del nodo ma l'insieme delle varie operazioni di cambiamento di colori/rotazioni necessarie al fine di preservare tali proprietà dell'albero RB corrente. Il nodo va cancellato eccome se si tratta di cancellazione, ci mancherebbe...
In teoria in ogni libro di algoritmi che si possa definire tale la cancellazione in un albero binario di ricerca è trattata in precedenza in un capitolo apposito.
Di fatto se ci pensi bene anche nel caso dell'inserimento si parte (almeno nel mio libro di algoritmi fanno così) con l'albero RB avente il nodo già inserito nel posto giusto e poi si descrivono solo gli "aggiustamenti" necessari. Che dici, questione di vedute
In teoria in ogni libro di algoritmi che si possa definire tale la cancellazione in un albero binario di ricerca è trattata in precedenza in un capitolo apposito.
Di fatto se ci pensi bene anche nel caso dell'inserimento si parte (almeno nel mio libro di algoritmi fanno così) con l'albero RB avente il nodo già inserito nel posto giusto e poi si descrivono solo gli "aggiustamenti" necessari. Che dici, questione di vedute
http://www.cs.unibo.it/~turrini/DIDATTI ... beriRB.pdf
Un po' meglio ma rimane un argomento difficilotto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo