Un albero AVL e' un normale albero binario, ordinato, a cui viene applicato come constraint che deve essere bilanciato (la definizione la sai).
Un albero red/black, invece, e' un albero bilanciato, ma non un albero binario.
Per poter essere ordinato, vuol dire che l'elemento che si utilizza per mantenere l'ordinamento deve avere associato un ordinamento totale. Ad esempio:
interi, numeri con la virgola, stringhe, vettori se usi un ordinamento lessicografico ...
senza una specifica implementazione, i numeri complessi non hanno un ordine totale; i nodi di un grafo nemmeno, ... ecc
Se aggiungi o togli nodi all'albero, questo deve rimanere ordinato: nota che ho scritto ordinato e non bilanciato. E questo e' ovvio: se l'albero non dovesse essere ordinato, per controllare la presenza di un valore dovresti scandirlo tutto, ritrovandoti con una struttura dati con una complessita' uguale a quella di una lista O(N). Assolutamente inutile.
Se invece sfrutti l'ordinamento, la mancanza di ordine ti impedirebbe di trovare il valore.
Il bilanciamento influisce sul tempo di ricerca:
immagina un normale albero binario con tutti i rami a sinistra vuoti, quindi tutto sbilanciato sulla destra: ci si ritrova con una struttura dati con complessita O(N). Praticamente una lista
Un albero del genere lo crei se non fai il bilanciamento ed inserisci i valori in modo gia' ordinato ...
Ora, che cosa fa il bilanciamento? Si assicura che il numero di valori sul ramo sinistro sia circa uguale al ramo destro. In questo modo la ricerca ha complessita O(log2(N)) ...
Quindi, mentre l'ordinamento e' obbligatorio, non cosi' il bilanciamento ...