Pages: [1]   Go Down
Print
Author Topic: Cancellare un nodo in un BST  (Read 818 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« on: 28-05-2010, 15:12:21 »

Salve ragazzi, come da titolo avrei un dubbio sulla seguente tipologia di esercizi:
http://img683.imageshack.us/img683/1796/testoy.jpg
il cui albero (prima di cancellare il nodo 10) è così configurato:
http://img72.imageshack.us/img72/241/albero.jpg
In particolare il dubbio è nell'operazione di cancellazione, l'algoritmo che conosco è il seguente:
1) Se il nodo non ha figli, basta rimuoverlo dall'albero
2) Se il nodo ha un solo figlio, allora basta sostituirlo con esso.
3) Se il nodo ha due figli (come il nostro caso), invece di cancellarlo, bisogna trovare il suo inorder-successor (minimo del sottoalbero destro) oppure il suo inorder-predecessor (massimo del sottoalbero sinistro). Dopodichè basta sostituire la chiave del nodo con quella del suo inorder-successor/predecessor ed eliminare quest'ultimo (che avrà al massimo un figlio).
Il dubbio è se devo scegliere l'inorder successor o l'inorder predecessor, infatti avremmo due configurazioni diverse dell'albero:
1) Scegliendo il successor http://img408.imageshack.us/i/successor.jpg/
2) Scegliendo il predecessor http://img295.imageshack.us/i/predecessor.jpg/

Dall'output corretto fornito dal sistema (3, 11, 7, ecc...) sembrerebbe corretta la seconda configurazione, ma in generale come bisogna fare?
Non ero presente quando è stata spiegata la cancellazione, magari c'è un algoritmo diverso.  pc

Grazie a chiunque risponderà  ok
Logged
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #1 on: 29-05-2010, 11:28:15 »

anche io ho questo dubbio atroce, ho scritto l'algoritmo del prof ma c'è qualche errore, e quindi è diventato illeggibile 
Logged

Ciò che è nostro è stato in campo sudato....ciò che vostro è stato in aula assegnato.
In serie B non sei mai stato perchè la prescrizione t'ha salvato.
Pages: [1]   Go Up
Print
Jump to: