[Dati e Algoritmi] Dubbio rimozione da AVL

[Patras]

Ciao a tutti! Studiando dati e algoritmi mi sono trovato di fronte a una slide che ho trovato in rete in cui si dice che per l'AVL non si può rimuovere la radice se essa ha come figli nodi interni e tutto sommato tratta solo il caso della rimozione solo per nodi che hanno come figli le foglie cosa che non mi torna dato che la rimozione dovrebbe esser possibile per qualsiasi nodo(?).

Anche perché a quanto pare la prestazione temporale della rimozione rimane ancora perché:
- Un AVL essendo anche un BST consente la rimozione della radice per mezzo della sostituzione con il nodo più vicino nell'attraversamento simmetrico in un tempo circa
- Anche se dopo tale operazione l''AVL rimane sbilanciato, trovando il nodo più profondo sbilanciato si può bilanciare con la rotazione in un tempo credo di nuovo .

Forse ho sbagliato da qualche parte o non ho capito bene gli AVL? Se qualcuno mi può chiarire questo dubbio mi fa un grande piacere. Ecco la slide tanto per capire il contesto:

[rugweri]

Quello che hai scritto tu è incomprensibile, quindi spero che non te la prenda troppo se lo ignoro semplicemente.

Per quanto riguarda la slide: se ben ricordo, l'algoritmo di eliminazione per gli AVL prevede di:

1) Eliminare il nodo usando l'algoritmo dei BST, che richiamo brevemente:
1.1) Trova il nodo da cancellare
1.2) Se è una foglia, cancellalo; se ha un solo figlio, scambialo con lui e cancella; se ha due figli, individua il suo successore, scambialo con lui (eventualmente effettuando una rotazione) e poi cancella.
2) Analizzare tutti gli antenati del nodo eliminato fino a trovare il primo antenato che sia radice di un albero non bilanciato
3) Ri-bilanciarlo con opportune rotazioni
4) Continuare a scorrere fino ad arrivare alla radice, ri-bilanciando tutte le volte che occorre

Il problema sta nel secondo punto: la radice non ha antenati, quindi dopo averla eliminata ti ritrovi con due semi-alberi separati (entrambi AVL, ma comunque separati) su cui l'algoritmo non ti da modo di intervenire. Qualora ti trovassi in questa situazione, in realtà, potresti effettuare un join (ci sono vari algoritmi per farlo: 1, 2) dei due alberi, ma parliamo di algoritmi specifici per questo singolo caso e comunque abbastanza verbosi.

[Patras]

Il problema sta nel secondo punto: la radice non ha antenati, quindi dopo averla eliminata ti ritrovi con due semi-alberi separati (entrambi AVL, ma comunque separati) su cui l'algoritmo non ti da modo di intervenire.

Grazie per la risposta. Non conoscevo l'algoritmo standard quindi pensavo a un altro modo di fare che ho descritto prima, provo a spiegarmi meglio perché il dubbio mi rimane ancora.
Per spiegarmi meglio dico "nodo pre-foglia" per il padre di duo foglie, perché ragiono su questi nodi dato che in un AVL le foglie si mantengono vuote.

Come togliere la radice:
In un BST la radice la posso eliminare: basta che al posto della radice metto la foglia successiva nell'attraversamento simmetrico. Il nuovo albero è ancora un BST.
Facciamo lo stesso per l'AVL. Qui però la foglia è in realtà una pre-foglia, slegata dai suoi figli vuoti che ora vengono presi dal padre. Il nuovo albero potrebbe non essere più bilanciato però siccome il nodo che abbiamo tolto è uno solo, faccio il bilanciamento con una rotazione, analizzando gli ex antenati di quella pre-foglia che ora è diventata la radice.

Perché non vale questo ragionamento? Forse le prestazioni risultano pessime o c'è un errore grande che ho fatto? Se c'è di nuovo qualcosa che non è chiaro me lo può precisare per favore?

[rugweri]

Dammi il "tu", per favore, che sono troppo giovane per il "lei"

Comunque... continuo a non capire cosa vuoi dire, anche se credo di iniziare ad intuirne il senso: me lo puoi illustrare con un disegno o qualcosa del genere? Te lo chiedo anche perché, se il tuo ragionamento è sbagliato, provando ad implementarlo graficamente te ne rendi conto, e quindi risolvi il problema anche se io non capisco cosa vuoi dire

[Patras]

Intanto ho sbagliato perché anche il BST ha queste foglie che le mantiene sempre vuote. In ogni caso facendo finta che sia un AVL faccio queste operazioni, e una volta finito faccio il bilanciamento sul sotto-albero destro (in questo particolare caso non ha senso perché rimane bilanciato).
L'unica immagine utile credo che sia l'ultima però comunque ho messo anche le altre per sicurezza:

[rugweri]

Il tuo ragionamento è sensato, ma il problema è sempre il punto 2 dell'algoritmo. Ti spiego meglio:

Intanto, una precisazione: ieri sera per stanchezza ho scritto una cavolata: non è vero che l'algoritmo che ti ho proposto genera due AVL separati (a "riunirli" ci pensa l'algoritmo di eliminazione dei BST al passo 1.2), quindi gli algoritmi di unione non c'entravano niente.

Ora, guarda un attimo cosa fa l'algoritmo che ti ho proposto, così vedi dov'è il problema:

1) Il primo passo dell'eliminazione prende in ingresso un AVL (che è anche un BST) e da in uscita un BST, che però potrebbe non essere un AVL.
2) Il secondo passo analizza tutti gli antenati del nodo eliminato per trovare eventuali sotto-alberi da bilanciare.
3) I passi 3-4 effettuano i bilanciamenti.

Ti ho sottolineato un dettaglio importante, che ti avevo già citato: l'algoritmo classico, eliminando la radice, non è in grado di ri-bilanciare nulla, perché non trova antenati da analizzare.

Ti faccio vedere una cosa: supponiamo di avere questo AVL:

2.png (11.86 KiB) Osservato 6448 volte

Eliminando la radice (ricorda che utilizziamo la sostituzione con il successore), otteniamo:

3.png (10.08 KiB) Osservato 6448 volte

Questo albero non è bilanciabile con l'algoritmo classico, perché la radice non ha antenati e quindi non vengono eseguite rotazioni correttive. Sarebbe invece bilanciabile con un algoritmo modificato sì da considerare come primo antenato del nodo il nodo stesso, o con un algoritmo di eliminazione BST opportuno, in grado per esempio di scegliere se effettuare la sostituzione con il successore o con il predecessore del nodo eliminato.

[Patras]

Grazie mille sei stato chiaro. Comunque la modifica all'algoritmo classico non mi sembrerebbe così complicata per quanto riguarda la radice attraverso la sostituzione che dicevo "stile BST". Strano che non sia già stata inclusa come standard anche perché le prestazioni temporali mi sembrano ancora .
Forse perché adottano un'altra soluzione più semplice che riguarda la costruzione dell'albero. Mi viene da pensare che avendo per esempio una mappa di N chiavi ordinabili che si riferiscono ai loro dati, aggiungo un'altra chiave senza dato che la mantengo circa a metà e la tengo nella radice. Questa chiave è sconosciuta all'user che a sua volta non potrà rimuoverla mai. Forse non è poi così semplice. Ma di solito come si fa per superare il questo problema?

[rugweri]

Strano che non sia già stata inclusa come standard anche perché le prestazioni temporali mi sembrano ancora .

FEEEEEEEERMO
Io ti ho mostrato il perché le slides riportassero quell'appunto sulla cancellazione alla radice, ma non ho mai detto che l'algoritmo effettivamente usato nelle implementazioni pratiche sia quello che ho citato.

Ti spiego: certi corsi di algoritmi si limitano a presentare delle versioni base degli algoritmi, versioni che di fatto sono limitate o in certi casi addirittura "sbagliate" ma più brevi da spiegare, e poi propongono delle migliorie dicendo semplicemente che "il programmatore potrebbe voler implementare [...]". La versione dell'algoritmo di cancellazione che ti ho citato io rientra in questi casi.
Tuttavia, nessuna implementazione degli AVL - escluse quelle realizzate dai cretini, ma lì il problema non è il singolo algoritmo - si pone il problema di valutare un nodo in più, anche perché un'implementazione intelligente potrebbe - ad esempio - basarsi sugli order-statistic BST, che rendono la verifica delle dimensioni dei sottoalberi (ma più complesse - non tanto, in realtà, ma comunque qualche istruzione in più c'è - le procedure relative al BST).

[Patras]

Grazie