Grazie

[quote="Patras"] Strano che non sia già stata inclusa come standard anche perché le prestazioni temporali mi sembrano ancora [unparseable or potentially dangerous latex formula].

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 [unparseable or potentially dangerous latex formula].
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?

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:

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


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.

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:

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

[quote="rugweri"]
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.

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.

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 [unparseable or potentially dangerous latex formula] 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 [unparseable or potentially dangerous latex formula]
- 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 [unparseable or potentially dangerous latex formula].

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: