Problema con un B-Albero
dovrei cancellare la chiave 130, il problema è che è un nodo interno.
dovrei copiare il predecessore di 130 al posto di 130, e eliminare la foglia in cui c'era 100.
però poi mi ritrovo con un nodo con 2 chiavi e 2 figli invece di 3...
come devo fare?
dovrei copiare il predecessore di 130 al posto di 130, e eliminare la foglia in cui c'era 100.
però poi mi ritrovo con un nodo con 2 chiavi e 2 figli invece di 3...
come devo fare?
Risposte
Che cosa ti dice di fare il tuo manuale in questo caso? Come hai potuto notare, copiare il predecessore (o successore) del nodo non è la soluzione corretta.
"apatriarca":
Che cosa ti dice di fare il tuo manuale in questo caso? Come hai potuto notare, copiare il predecessore (o successore) del nodo non è la soluzione corretta.
riporta solo 3 casi:
1. v è un nodo interno
2. v è foglia quasi non vuota
3. v è foglia quasi vuota
escludendo il caso 2 e 3, il caso 1 riporta solo queste parole: "cerchiamo il nodo contenente il predecessore di k. dopodiche copiamo il predecessore di k all'interno di v e al posto di k e chiamiamo la cancellazione del precedente di k che è sicuramente contenuto in una foglia."
non c'è manco un riferimento al fatto del successivo... (ps: sono dispense, non un vero e proprio libro)
cercando ora su wikipedia, nel caso di nodo interno ci sono 3 casi (di cui 2 simmetrici, quello che fa al caso mio è questo:
Siano y e z rispettivamente i figli che precedono e succedono k e si supponga che abbiano t − 1 chiavi. Allora si devono inserire nel nodo y sia la chiave k che tutte le chiavi di z; in questo caso i figli di z divengono figli di y. Tuttavia il nodo x perde k e il puntatore a z e il nodo y diviene pieno. Quindi si deve necessariamente procedere ricorsivamente ad eliminare k da y.
ora seguendo le istruzioni di wikipedia, mi ritrovo con il nodo che contiene 230, che ha 2 figli, uno contenente 100,130,200 e l'altro 250,310.
dopodiche cancello 130 dato che fa parte di un nodo foglia non quasi vuoto.
ora però il problema mi si pone con la cancellazione di 4. come procedo?
Ti trovi nel secondo caso di wikipedia se non sbaglio e quindi devi trovare il successore di 4, cioè 5, cancellarlo dalla foglia e inserirlo al posto del 4.
quindi mi ritrovo col nodo che contiene la chiave 5, e due figli di cui uno ha la chiave 1 e l'altro la chiave 20.
ora scusa se chiedo ancora aiuto, ma anche leggendo le istruzioni di wiki, non riesco a risolvere l'ultimo caso, cancellare la chiave 1.
rimango con un nodo con la chiave 5 e un solo figlio destro con la chiave 20.. :/
ora scusa se chiedo ancora aiuto, ma anche leggendo le istruzioni di wiki, non riesco a risolvere l'ultimo caso, cancellare la chiave 1.
rimango con un nodo con la chiave 5 e un solo figlio destro con la chiave 20.. :/
Non puoi pensare di studiarti delle strutture dati più o meno complesse senza un testo di riferimento completo e attendibile. A grandi linee l'eliminazione di un elemento da un B-tree prosegue come segue:
[*:1r9dzb71]Se l'elemento fa parte della foglia che si sta prendendo in considerazione allora si elimina semplicemente l'elemento;[/*:m:1r9dzb71]
[*:1r9dzb71]Se l'elemento fa parte di un nodo interno che si sta prendendo in considerazione allora si possono avere i seguenti casi:
[*:1r9dzb71] Se il figlio sinistro dell'elemento ha almeno t elementi allora trova il predecessore della chiave, rimuovila dal sottoalbero e sostituiscila alla chiave.[/*:m:1r9dzb71]
[*:1r9dzb71] Simmetricamente al caso precedente, se il figlio destro ha almeno t elementi, allora trovi il successore, lo elimini dal sottoalbero e lo sostituisci alla chiave.[/*:m:1r9dzb71]
[*:1r9dzb71] Se entrambi gli elementi figli hanno t-1 elementi, allora unisci i due figli e k in un unico nodo figlio e rimuovi poi la chiave ricorsivamente da questo nuovo nodo[/*:m:1r9dzb71][/list:u:1r9dzb71][/*:m:1r9dzb71]
[*:1r9dzb71] Se invece il nodo non è presente nel nodo interno che si sta prendendo in considerazione (se non è presente in una foglia non c'è la chiave nell'albero..) allora si deve trovare il sottoalbero che dovrebbe contenere la chiave e fare una delle seguenti cose nel caso in cui il nodo figlio contenga solo t-1 elementi. Richiamare poi ricorsivamente la procedura di rimozione per il sottoalbero.
[*:1r9dzb71] Se il sottoalbero ha almeno un nodo adiacente con almeno t elementi, rimuovi un elemento dal nodo genitore e portalo nel sottoalbero, aggiungi un elemento del nodo adiacente al nodo genitore e sposta i sottoalberi figli nel modo corretto (essendomi dimenticato di definire un decente lessico preferisco chiarire il concetto con l'esempio successivo).[/*:m:1r9dzb71]
[*:1r9dzb71] Se nessuno dei nodi adiacenti ha più di t elementi, allora unisci il nodo con uno adiacente e la chiave corrispondente nel nodo genitore.[/*:m:1r9dzb71][/list:u:1r9dzb71][/*:m:1r9dzb71][/list:u:1r9dzb71]
Rappresenterò i nodi nella forma \(((c_0) \; k_1 \; (c_1) \; \dots \; (c_{n-1}) \; k_n \; (c_n) )\) dove \(c_i\) sono i sottoalberi (sempre rappresentati in quel modo e \(k_i\) sono le chiavi. Il tuo albero è quindi rappresentato da:
\[ ((1) \; 4 \; (5 \; 20)) \; 80 \; ((100) \; 130 \; (200) \; 230 \; (250 \; 310)) \]
Per eliminare \(1\) proseguiamo nel seguente modo.
1. Esaminiamo il nodo radice e vediamo che il nostro elemento si deve trovare a sinistra. Siccome il nodo ha sinistra ha solo \(1\) elemento, osserviamo il nodo adiacente che ne ha due e portiamo l'\(80\) in basso nel nodo, portiamo il \(130\) in alto e spostiamo il nodo figlio \((100\) a destra dell'\(80\) ottenendo quindi l'albero:
\[ ((1) \; 4 \; (5 \; 20) \; 80 \; (100)) \; 130 \; ((200) \; 230 \; (250 \; 310)) \]
A questo punto vediamo che il nostro elemento non si trova neanche nel nodo interno che stiamo considerando e il figlio che lo contiene ha un solo elemento per cui ripetiamo l'operazione precedente spostando il \(4\) in basso e il \(5\) in alto. Otteniamo quindi l'albero
\[ ((1 4) \; 5 \; (20) \; 80 \; (100)) \; 130 \; ((200) \; 230 \; (250 \; 310)) \]
A questo punto troviamo la chiave in una foglia e quindi lo eliminiamo ottenendo infine l'albero:
\[ ((4) \; 5 \; (20) \; 80 \; (100)) \; 130 \; ((200) \; 230 \; (250 \; 310)) \]
È abbastanza complicata anche l'eliminazione del \(4\). La prima fase sarebbe uguale a quella per eliminare l'\(1\) arrivando quindi all'albero:
\[ ((1) \; 4 \; (5 \; 20) \; 80 \; (100)) \; 130 \; ((200) \; 230 \; (250 \; 310)) \]
Ma a questo punto abbiamo trovato l'elemento nel nodo corrente e siccome il figlio a destra a 2 elementi possiamo spostare il successore in alto ottenendo:
\[ ((1) \; 5 \; (20) \; 80 \; (100)) \; 130 \; ((200) \; 230 \; (250 \; 310)) \]
Queste regole per aggiustare l'albero scendendo permettono di mantenere le regole dell'albero in caso di rimozione.
sei stato molto chiaro, vediamo se ho capito bene. io devo cancellare dal seguente B-albero, prima la chiave 4 e successivamente la 1:
((1) 4 ( 5 20 )) 80 ((100 200) 230 (310)
faccio scendere il 4 a sinistra, e salire il suo successore 5
((1 4) 5 (20 )) 80 ((100 200) 230 (310)
e cancello tranquillamente il 4 e mi ritrovo con:
((1) 5 (20 )) 80 ((100 200) 230 (310)
ora per cancellare l'1 faccio scendere il 5 a sinistra e salire il 20, scende anche l'80 diventando figlio del 20 e sale alla radice il 100:
((1 5) 20(80 )) 100 ((200) 230 (310).
è giusto?
dopodiché elimino senza problemi l'1.
((1) 4 ( 5 20 )) 80 ((100 200) 230 (310)
faccio scendere il 4 a sinistra, e salire il suo successore 5
((1 4) 5 (20 )) 80 ((100 200) 230 (310)
e cancello tranquillamente il 4 e mi ritrovo con:
((1) 5 (20 )) 80 ((100 200) 230 (310)
ora per cancellare l'1 faccio scendere il 5 a sinistra e salire il 20, scende anche l'80 diventando figlio del 20 e sale alla radice il 100:
((1 5) 20(80 )) 100 ((200) 230 (310).
è giusto?
dopodiché elimino senza problemi l'1.
No, hai dimenticato il primo passaggio. Siccome entrambi i figli della radice hanno solo 1 elemento ti trovi nell'ultimo punto dell'ultimo punto. Devi cioè unire i due figli della radice con la radice formando un unico nodo più grosso. Cioè
\[ ((1) \; 4 \; (5 \; 20)) \; 80 \; ((100 \; 200) \; 230 \; (310)) \]
diventa
\[ ((1) \; 4 \; (5 \; 20) \; 80 \; (100 \; 200) \; 230 \; (310)) \]
riducendo quindi l'altezza dell'albero di uno. A questo punto trovi il 4 e sei nel caso in cui uno dei nodi abbia almeno 2 elementi e quindi prendi il suo successori e glielo sostituisci per cui si ottiene
\[ ((1) \; 5 \; (20) \; 80 \; (100 \; 200) \; 230 \; (310)) \]
Per ridurre l'uno a questo punto ti fermi al 5 e noti che sia (1) che (20) hanno solo un elemento e quindi devi far scendere il 5 e fare un unico nodo come segue:
\[ ((1 \; 5 \; 20) \; 80 \; (100 \; 200) \; 230 \; (310)) \]
A questo punto elimini dalla foglia
\[ ((5 \; 20) \; 80 \; (100 \; 200) \; 230 \; (310)) \]
Ricorda che se ti trovi in un nodo con meno di t-1 elementi dal quale eliminare qualcosa hai tralasciato un passaggio.
\[ ((1) \; 4 \; (5 \; 20)) \; 80 \; ((100 \; 200) \; 230 \; (310)) \]
diventa
\[ ((1) \; 4 \; (5 \; 20) \; 80 \; (100 \; 200) \; 230 \; (310)) \]
riducendo quindi l'altezza dell'albero di uno. A questo punto trovi il 4 e sei nel caso in cui uno dei nodi abbia almeno 2 elementi e quindi prendi il suo successori e glielo sostituisci per cui si ottiene
\[ ((1) \; 5 \; (20) \; 80 \; (100 \; 200) \; 230 \; (310)) \]
Per ridurre l'uno a questo punto ti fermi al 5 e noti che sia (1) che (20) hanno solo un elemento e quindi devi far scendere il 5 e fare un unico nodo come segue:
\[ ((1 \; 5 \; 20) \; 80 \; (100 \; 200) \; 230 \; (310)) \]
A questo punto elimini dalla foglia
\[ ((5 \; 20) \; 80 \; (100 \; 200) \; 230 \; (310)) \]
Ricorda che se ti trovi in un nodo con meno di t-1 elementi dal quale eliminare qualcosa hai tralasciato un passaggio.
ora ho capito, vedrò di stamparmi bene in testa tutti i casi, l'ultimo punto mi era proprio sfuggito.
grazie mille apatriarca!
grazie mille apatriarca!
ho un'altro dubbio, da questo b-albero devo eliminare 50:
trovo il successore della chiave da eliminare, cioè 300. lo elimino dal sottoalbero destro e lo metto al posto di 50. giusto?
e le chiavi 100 e 200 le pongo come fratelli di 30 e 40?
quindi da questa situazione iniziale di partenza:
((15) 20 (30 40)) 50 ((100 200) 300 (350) 400 (450 500))
diventa questo?
((15) 20 (30) 40( 100 200 )) 300 ((350) 400 (450 500))
trovo il successore della chiave da eliminare, cioè 300. lo elimino dal sottoalbero destro e lo metto al posto di 50. giusto?
e le chiavi 100 e 200 le pongo come fratelli di 30 e 40?
quindi da questa situazione iniziale di partenza:
((15) 20 (30 40)) 50 ((100 200) 300 (350) 400 (450 500))
diventa questo?
((15) 20 (30) 40( 100 200 )) 300 ((350) 400 (450 500))
Il successore di 50 è 100 e non 300. Il successore è il più piccolo elemento dell'albero maggiore dell'elemento e si trova sempre in una foglia. In questo caso cerchi quindi il successore di 50 e arrivi fino alla foglia (100 200) dalla quale elimini l'elemento più piccolo e lo vai a sostituire al 50.
"apatriarca":
Il successore di 50 è 100 e non 300. Il successore è il più piccolo elemento dell'albero maggiore dell'elemento e si trova sempre in una foglia. In questo caso cerchi quindi il successore di 50 e arrivi fino alla foglia (100 200) dalla quale elimini l'elemento più piccolo e lo vai a sostituire al 50.
non so come ho fatto a non vedere 100, eppure l'h anche scritto
sarà che ormai algoritmi mi sta fondendo il cervello
quindi cancellando 50 abbiamo questa situazione:
((15) 20 ( 30 40)) 100 ((200) 300 (350) 400 (450 500))
right?
Sì, dovrebbe essere corretto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo