2010-10-10 3 views
22

Quali sono le applicazioni degli alberi rosso-neri? Esiste qualche applicazione in cui possono essere utilizzati solo gli alberi RB e nessun'altra struttura dati?Applicazioni di alberi rosso-neri

+8

Si può sempre fare un po 'di lavoro con qualsiasi struttura dati, ma in alcuni casi diventerà 'O (spaventoso)'. La domanda dovrebbe essere: quali algoritmi funzionano meglio con RB Trees? (E credo che Wikipedia abbia alcune risposte). – delnan

risposta

7

A meno che non si abbiano requisiti prestazionali specifici, un albero R-B può essere sostituito da un altro albero binario autobilanciato, ad esempio un albero AVL. La scelta tra i due è fondamentalmente un ottimizzazione delle prestazioni - offrono le stesse operazioni di base.

Non è che entrambi siano decisamente "più veloci" degli altri, solo che sono abbastanza diversi che gli usi specifici tenderanno ad avere prestazioni leggermente diverse, a parità di tutti gli altri. Quindi, se attiri le tue esigenze con cura, o solo per caso, potresti ritrovarti con uno di loro "abbastanza veloce" per il tuo uso, e l'altro no. R-B offre un inserimento leggermente più veloce di AVL, al costo di una ricerca leggermente più lenta.

25

A red-black tree è un'implementazione particolare di self-balancing binary search tree e oggi sembra essere la scelta più popolare di implementazione.

Binary search trees vengono utilizzati per implementare mappe finite, in cui viene memorizzato un set di chiavi con valori associati. È inoltre possibile implementare i set utilizzando solo i tasti e non memorizzando alcun valore.

Il bilanciamento dell'albero è necessario per garantire buone prestazioni, altrimenti l'albero potrebbe degenerare in un elenco, ad esempio se si inseriscono chiavi già ordinate.

Il vantaggio degli alberi di ricerca sulle tabelle hash è che è possibile attraversare l'albero in modo efficiente in base al criterio di ordinamento.

AVL-trees sono un'altra variante di alberi di ricerca binari bilanciati. Erano popolari prima che gli alberi rosso-neri fossero conosciuti. Sono più attentamente bilanciati, con una differenza massima di uno tra le altezze della sottostruttura sinistra e destra (gli alberi RB garantiscono al massimo un fattore di due). Il loro principale inconveniente è che il riequilibrio richiede uno sforzo maggiore.

Quindi gli alberi rosso-neri sono certamente una buona scelta, ma non l'unica per questa applicazione.

+4

Penso che gli alberi AVL siano migliori perché sono comprensibili. Devo ancora incontrare uno sviluppatore che capisca come funzionano gli alberi RB - con ciò intendo più comprensione che recitare l'elenco delle regole di bilanciamento. –

+3

L'invariante di base non è così complicato: in un albero rosso-nero ogni percorso di una foglia ha lo stesso numero di nodi neri e non ci sono nodi rossi adiacenti su un percorso. Ciò implica che le lunghezze dei percorsi differiscono al massimo da un fattore due. Per quanto riguarda le rotazioni richieste, questa è un'analisi caso per caso per entrambi i tipi di alberi. – starblue

2

Non esiste una regola come il nero rosso può essere utilizzata solo in un caso particolare dipende dall'applicazione in casi come quando è necessario costruire l'albero solo una volta e devi interrogarlo più volte che puoi andare per un albero AVL perché nella ricerca ad albero di AVL è abbastanza veloce .. Ma è strettamente bilanciato quindi l'inserimento e la cancellazione potrebbero richiedere del tempo albero AVl può essere usato per il linguaggio di pronuncia dove devi costruire la struttura dati solo una volta e il rosso albero nero viene utilizzato nell'Utilità di pianificazione Completamente corretta utilizzata negli attuali kernel Linux ora un giorno ..

i vincoli applicati sull'albero nero rosso applicano anche il punto che quello il percorso dalla radice a la foglia più lontana non è lunga più del doppio del percorso dalla radice alla foglia più vicina.

BTW è possibile cercare i vari seach e inserire ecc tempo necessario per un albero nero rosso quaggiù

 Average  Worst case 

Space O(n)  O(n) 

Search O(log n) O(log n) 

Insert O(log n) O(log n) 

Delete O(log n) O(log n) 
5

Rosso Nero alberi sono da una classe di BST auto bilanciamento e come risposta da altri, tale può essere utilizzato un albero di auto bilanciamento. Vorrei aggiungere che gli alberi rosso-neri sono ampiamente usati come tabelle dei simboli di sistema.Ad esempio, vengono utilizzati per implementare quanto segue:

  • Java: java.util.TreeMap, java.util.TreeSet.
  • STL C++: mappa, multimappa, multiset.
  • kernel Linux: tutto giusto scheduler, linux/rbtree.h
1

Process Scheduler in Linux utilizza Rosso Nero Alberi. Gli alberi neri rossi sono una sostituzione per le code di esecuzione che avevano priorità per i processi in coda da cui lo scheduler può prelevare.

The Completely Fair Scheduler (C.F.S) è il nome di un pianificatore di processi che è stato unito alla release 2.6.23 del kernel Linux. Gestisce l'allocazione delle risorse della CPU per l'esecuzione dei processi e mira a massimizzare l'utilizzo complessivo della CPU ottimizzando al contempo le prestazioni interattive.