Oltre ai punti Macneils ...
Gli alberi red-black sono forse più direttamente utili perché ci sono operazioni efficienti utili che non sono ampiamente supportate in implementazioni di librerie standard come il C ++ std::map (almeno AFAIK). Gli alberi rosso-neri possono supportare "dividere" (tagliare un albero in due, uno contenente chiavi meno di una chiave specificata e uno contenente le chiavi più grande) e "unirsi" (il contrario, combinando un albero di grandi chiavi con un albero di piccole dimensioni chiavi) possono essere eseguite in O (log n) time, ma se sono supportate nelle librerie contenitore standard, sembra essere una cosa ben nascosta.
Tuttavia, le strutture dati "aumentanti" sono comuni. Un semplice esempio è l'aggiunta di informazioni sulla dimensione della sottostruttura ai nodi in quasi tutte le strutture di dati dell'albero per supportare O (log n) subscripting. Esempi più sofisticati includono gli alberi intervallati.
Una volta che hai avuto l'idea di aumentare le strutture dei dati, ci sono molte varianti che possono essere utili per particolari applicazioni - e molto poche sono disponibili preconfezionate come una libreria. Le strutture di dati della libreria standard esistenti (ad es. std::map ) non possono essere aggiunte per copiare il codice sorgente e modificarlo direttamente: non è possibile aumentarle utilizzando i parametri del modello.
Ovviamente per sviluppare una struttura dati ampliata, è necessario comprendere la sottostante struttura dati non aumentata.
Gli alberi AVL possono essere più veloci degli alberi red-black se fai molte più ricerche di inserti / eliminazioni (e se non hai bisogno di quelle operazioni di split / join), quindi a seconda dell'applicazione, potrebbero essere molto buona base per l'aumento.