Perché la std :: map è implementata come un albero rosso-nero?

Perché la std::map implementata come un albero rosso-nero ?

Ci sono diversi alberi di ricerca binari bilanciati (BST) là fuori. Quali sono stati i compromessi di design nella scelta di un albero rosso-nero?

Probabilmente i due algoritmi di albero di auto bilanciamento più comuni sono alberi rosso-nero e alberi AVL . Per bilanciare l’albero dopo un inserimento / aggiornamento, entrambi gli algoritmi utilizzano la nozione di rotazioni in cui i nodes dell’albero vengono ruotati per eseguire il riequilibrio.

Mentre in entrambi gli algoritmi le operazioni di inserimento / cancellazione sono O (log n), nel caso della rotazione del riequilibrio dell’albero Red-Black è un’operazione O (1) mentre con AVL questa è un’operazione O (log n) , rendendo Albero rosso-nero più efficiente in questo aspetto della fase di riequilibrio e una delle possibili ragioni per cui è più comunemente usato.

Gli alberi rosso-nero vengono utilizzati nella maggior parte delle raccolte di raccolte, incluse le offerte da Java e Microsoft .NET Framework.

Dipende davvero dall’uso. L’albero AVL di solito ha più rotazioni di riequilibrio. Quindi se la tua applicazione non ha troppe operazioni di inserimento e cancellazione, ma pesa molto sulla ricerca, allora l’albero AVL probabilmente è una buona scelta.

std::map usa l’albero rosso-nero quando ottiene un ragionevole compromesso tra la velocità di inserimento / cancellazione del nodo e la ricerca.

Gli alberi AVL hanno un’altezza massima di 1,44 logn, mentre gli alberi RB hanno un massimo di 2logn. L’inserimento di un elemento in un AVL può implicare un ribilanciamento in un punto dell’albero. Il ribilanciamento termina l’inserimento. Dopo l’inserimento di una nuova foglia, l’aggiornamento degli antenati di quella foglia deve essere fatto fino alla radice, o fino a un punto in cui i due sottoalberi sono di uguale profondità. La probabilità di dover aggiornare k nodes è 1/3 ^ k. Il riequilibrio è O (1). La rimozione di un elemento può implicare più di un riequilibrio (fino a metà della profondità dell’albero).

Gli alberi RB sono alberi B dell’ordine 4 rappresentati come alberi di ricerca binari. Un 4-nodes nell’albero B produce due livelli nell’equivalente BST. Nel peggiore dei casi, tutti i nodes dell’albero sono 2-nodes, con una sola catena di 3 nodes fino a una foglia. Quella foglia sarà a una distanza di 2logn dalla radice.

Scendendo dalla radice al punto di inserimento, si devono cambiare 4 nodes in 2 nodes, per assicurarsi che qualsiasi inserimento non possa saturare una foglia. Tornando dall’inserzione, tutti questi nodes devono essere analizzati per assicurarsi che rappresentino correttamente 4 nodes. Questo può anche essere fatto andando giù nell’albero. Il costo globale sarà lo stesso. Non c’è il pranzo gratis! La rimozione di un elemento dall’albero è dello stesso ordine.

Tutti questi alberi richiedono che i nodes portino informazioni su altezza, peso, colore, ecc. Solo gli alberi Splay sono esenti da tali informazioni aggiuntive. Ma la maggior parte delle persone ha paura degli alberi di Splay, a causa della ramadura della loro struttura!

Infine, gli alberi possono anche trasportare informazioni sui pesi nei nodes, consentendo il bilanciamento del peso. Possono essere applicati vari schemi. Si dovrebbe riequilibrare quando una sottostruttura contiene più di 3 volte il numero di elementi dell’altro sottoalbero. Il riequilibrio viene di nuovo fatto attraverso una rotazione singola o doppia. Questo significa un caso peggiore di 2.4logn. Si può farcela con 2 volte anziché 3, un rapporto molto migliore, ma potrebbe voler dire lasciare un po ‘meno dell’1% dei sottoalberi sbilanciati qua e là. Difficile!

Quale tipo di albero è il migliore? AVL di sicuro. Sono i più semplici da codificare e hanno la loro altezza peggiore più vicina a logn. Per un albero di 1000000 elementi, un AVL sarà al massimo dell’altezza 29, un RB 40 e un peso bilanciato 36 o 50 a seconda del rapporto.

Ci sono molte altre variabili: casualità, rapporto di aggiunte, eliminazioni, ricerche, ecc.

Le risposte precedenti riguardano solo le alternative ad albero e il nero rosso probabilmente rimane solo per ragioni storiche.

Perché non un hash table?

In un albero un tipo richiede solo un ordine parziale (

La progettazione di una buona tabella hash richiede una conoscenza approfondita del contesto in cui verrà utilizzata. Dovrebbe utilizzare l’indirizzamento aperto o il concatenamento collegato? Quali livelli di carico dovrebbe accettare prima di ridimensionare? Dovrebbe usare un hash costoso che eviti le collisioni, o uno che è ruvido e veloce?

(C ++ 11 ha aggiunto tabelle hash con unordered_map . Puoi vedere dalla documentazione che richiede l’impostazione delle politiche per configurare molte di queste opzioni.)

Poiché l’STL non può anticipare quale sia la scelta migliore per la tua applicazione, l’impostazione predefinita deve essere più flessibile. Gli alberi “funzionano” e si adattano bene.

E gli altri alberi?

L’offerta di Black Black offre una rapida ricerca e si bilanciano da soli, a differenza dei BST. Un altro utente ha evidenziato i suoi vantaggi rispetto all’albero AVL autobilanciato.

Alexander Stepanov (il creatore di STL) ha detto che avrebbe usato un albero B * invece di un albero rosso-nero se avesse scritto di nuovo std::map che è più amichevole per le cache di memoria moderne.

Uno dei più grandi cambiamenti da allora è stata la crescita delle cache. Le mancanze nella cache sono molto costose, quindi la località di riferimento è molto più importante ora. Le strutture dati basate su nodes, che hanno una bassa localizzazione di riferimento, hanno molto meno senso. Se stessimo progettando STL oggi, avrei un diverso set di contenitori. Ad esempio, un albero B * in memoria è una scelta molto migliore di un albero rosso-nero per l’implementazione di un contenitore associativo. – Alexander Stepanov

Puoi leggere di più qui

L’albero nero rosso o B * è sempre il migliore?

In altre occasioni Alex ha affermato che std::vector è quasi sempre il miglior contenitore di lista per ragioni simili. Raramente ha senso usare std::list o std::deque anche per quelle situazioni che ci sono state insegnate a scuola (come la rimozione di un elemento dal centro della lista). std::vector è così veloce da battere quelle strutture per tutto tranne il grande n.

Applicare lo stesso ragionamento se si ha solo un piccolo numero di elementi (centinaia?) Usando una ricerca std::vector e lineare può essere più efficiente dell’implementazione dell’albero di std::map . A seconda della frequenza di inserimento, un std::vector combinato con std::binary_search può essere la scelta più veloce.

È solo la scelta della tua implementazione – potrebbero essere implementati come qualsiasi albero bilanciato. Le varie scelte sono tutte paragonabili con piccole differenze. Quindi ogni è buono come qualsiasi.

Aggiornamento 2017-06-14: webbertiger modifica la sua risposta dopo aver commentato. Vorrei sottolineare che la sua risposta ora è molto meglio ai miei occhi. Ma ho mantenuto la mia risposta solo come informazione aggiuntiva …

A causa del fatto che penso che la prima risposta sia sbagliata (correzione: non entrambi più) e la terza ha un’affermazione sbagliata. Sento che dovevo chiarire le cose …

I 2 alberi più popolari sono AVL e Red Black (RB). La principale differenza sta nell’utilizzo:

  • AVL: Meglio se il rapporto di consultazione (leggi) è più grande della manipolazione (modifica). Il footprint di memoria è un po ‘inferiore a RB (a causa del bit richiesto per la colorazione).
  • RB: Meglio nei casi generali in cui vi è un equilibrio tra consultazione (lettura) e manipolazione (modifica) o più modifica rispetto alla consultazione. Un ingombro di memoria leggermente più grande a causa della memorizzazione della bandiera rosso-nero.

La principale differenza deriva dalla colorazione. Si ha meno azione di riequilibrio nell’albero RB rispetto a AVL perché la colorazione consente di saltare o accorciare le azioni di riequilibrio che hanno un costo relativamente elevato. A causa della colorazione, l’albero RB ha anche un livello superiore di nodes perché potrebbe accettare nodes rossi tra quelli neri (con la possibilità di ~ 2x livelli in più) rendendo la ricerca (leggi) un po ‘meno efficiente … ma perché è un costante (2x), rimane in O (log n).

Se si considera il colpo di prestazione per una modifica di un albero (significativo) VS il colpo di prestazione di consultazione di un albero (quasi insignificante), diventa naturale preferire RB su AVL per un caso generale.