Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Salve a tutti! Siccome vorrei implementare questo tipo di albero in Java, mi sono messo alla ricerca delle sue proprietà e funzioni; insomma ho iniziato a studiarlo .
Tra i vari risultati di Google ho trovato due siti in cui propongono una demo per provare e vedere "dal vivo" come funzionano gli alberi rosso neri.
Li ho provati entrambi con il seguente input:
84, 24, 92, 100, 10, 51, 98, 14, 3, 354, 67, 1, 8, 59
Per quanto riguarda l'inserimento tutto ok, non ho problemi; ma quando avviene la cancellazione di un nodo c'è una situazione che non mi è chiara. Nella maggior parte dei casi, se il nodo in questione ha entrambi i figli si trova il suo successore/sostituto cercando il nodo con il minimo valore nel sotto-albero a destra del nodo; in alcuni casi invece, nonostante il nodo abbia entrambi i figli, ricerca il sostituto come massimo nel sotto-albero sinistro. Uno di questi casi, in cui si ricerca il massimo a sinistra, è se provate a cancellare la radice (84). Per quello che ho capito, l'algoritmo dovrebbe trovare il sostituto in (92), invece sostituisce la radice (84) con 67; in tutti gli altri casi (che ho provato) invece ricerca il minimo nel sotto-albero di sinistra (cioé come mi aspettavo che succedesse con la radice).
C'è qualcosa che mi sfugge e non ho capito nella ricerca del successivo, oppure si "comporta in modo strano" la demo?
Spero di essere stato il più chiaro possibile.
Ultima modifica effettuata da sigur il 28/10/2012 alle 17:08
Penso che alla fine sono riuscito a capire il perché di questo "strano" comportamento. In realtà la funzione che utilizza per cercare il successore/sostituto del nodo non cerca solo il nodo minimo del sotto-albero destro, ma anche il massimo nel sotto-albero sinistro.
Trovati entrambi se il nodo del sotto-albero sinistro è rosso e quello del sotto-albero destro è nero, ritorna il nodo sinistro; altrimenti torna sempre il destro.
Ora sto considerando se questo "trucchetto" sia una buona ottimizzazione.
.
