28/10/12 16:06
sigur
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.
gauss.ececs.uc.edu/RedBlackTester/…
ece.uc.edu/~franco/C321/html/RedBlack/…
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.
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.
gauss.ececs.uc.edu/RedBlackTester/…
ece.uc.edu/~franco/C321/html/RedBlack/…
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 28/10/12 16:08
aaa