Algoritmo cancellazione nodo in un ABR

di
VentoNelGrano
il
3 risposte
V
VentoNelGrano
Pochi posts
Iscritto da
dic, 2013
Messaggi:
6

Algoritmo cancellazione nodo in un ABR

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

  • D
    dvaosta
    Molto attivo
    Iscritto da
    lug, 2012
    Messaggi:
    962

    Re: Algoritmo cancellazione nodo in un ABR

    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
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6076

    Re: Algoritmo cancellazione nodo in un ABR

    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
  • D
    dvaosta
    Molto attivo
    Iscritto da
    lug, 2012
    Messaggi:
    962

    Re: Algoritmo cancellazione nodo in un ABR

    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