[Algoritmi] Dubbio rimozione da AVL

[absinth]

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 $O(h)=O(\log n)$ 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 $O(\log n)$
- 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 $O(\log n)$.

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:

Testo nascosto, fai click qui per vederlo

[apatriarca]

Come regola generale: NON STUDIARE CERCANDO SLIDE A CASO SU INTERNET. Ci sono un sacco di ragioni per seguire questa regola:
1. Le slide sono fatte (o almeno dovrebbero) per aiutare la comprensione di una lezione frontale e non come risorsa di studio. E' quindi abbastanza normale trovare errori o omissioni o semplificazioni.
2. Le slide fanno parte di un contesto più grande, l'intera lezione, di cui stai estraendo un singolo elemento. E' insomma possibile che il professore possa fare delle semplificazioni poi eliminate in seguito oppure presentare un algoritmo che non funziona per poi mostrare come aggiustarlo correttamente.
3. Non sempre le risorse che si trovano su internet sono affidabili.

E' possibile eliminare un elemento da un AVL facendo come hai descritto (come si vede facilmente anche guardando un sito come Wikipedia o andando su un manuale). La slide potrebbe tuttavia discutere di altro. Potrebbe per esempio mostrare quando è necessario bilanciare l'albero facendo uso del normale algoritmo per gli alberi binari.

[absinth]

Grazie mille! Cercherò di seguire il Suo consiglio