Algoritmo cancellazione nodo in un ABR

di Anonimizzato13701 il
3 risposte
/
Anonimizzato13701
Utente anonimizzato
Salve a tutti programmatori.
Avrei bisogno dello pseudocodice dell'algoritmo per l'eliminazione di un nodo in un albero binario di ricerca. Ho scritto lo pseudocodice per trovare il predecessore di un nodo (con relativa chiamata alla funzione massimo). Quindi l'algoritmo dovrebbe contenere la funzione per il predecessore e non per il successore. Ovvero deve rispettare ciò:
1. u e una foglia: in tal caso distacchiamo semplicemente la foglia dall'al-
bero;
2. u ha un unico figlio e sia v l'unico figlio di u
(a) se u e radice allora v diviene la nuova radice dell'albero;
(b) se u non e radice allora sia w il padre di u, sostituiamo l'arco
(w; u) con l'arco (w; u);
3. u ha due figli: in tal caso sia v il predecessore di u. Poiche
u ha due gli il predecessore sara il massimo del sottoalbero sinistro
di u e pertanto sara una foglia oppure un nodo interno avente al mas-
simo un solo figlio: quello sinistro. La canellazione di u pertanto puo
avvenire copiando la chiave di v in u ed eliminando v cadendo per
quest'ultima operazione nei due casi precendenti.

Per caso sapete in che sito posso reperirlo? Non vorrei usare la funzione del successore.

Grazie a tutti

3 Risposte

  • /
    Anonimizzato10779
    Utente anonimizzato
    Ho appena iniziato anch'io i BST, quindi potrei sbagliare, ma la butto lì:

    E se lavorassi per rotazioni, in modo da far risalire sepre il nodo fino a farlo diventare una foglia?

    ciao
  • Super Famoso
    Iscritto da
    apr, 2013
    Messaggi
    6268
    La rimozione di un nodo in un albero consiste in due passi:

    1) scambio del nodo da rimuovere con un nodo foglia. Quale foglia? Non e' un problema, destra o sinistra va bene lo stesso
    2) rimozione del nodo foglia.

    Ovviamente se il nodo da rimuovere e' gia' un nodo foglia, il passo 1 non serve
  • /
    Anonimizzato10779
    Utente anonimizzato

    migliorabile ha scritto:

    La rimozione di un nodo in un albero consiste in due passi:

    1) scambio del nodo da rimuovere con un nodo foglia. Quale foglia? Non e' un problema, destra o sinistra va bene lo stesso
    2) rimozione del nodo foglia.

    Ovviamente se il nodo da rimuovere e' gia' un nodo foglia, il passo 1 non serve
    Dopo lo scambio con una foglia devi comunque far in modo che siano rispettate le proprietà del BST (ogni nodo ha un valore intermedio tra quelli del sottoalbero sx e quelli del dx).
    A questo punto tanto vale applicare l'algoritmo di rotazione fino a far risalire il nodo in una foglia.
Devi accedere o registrarti per scrivere nel forum
3 risposte