Alberi rosso-neri

Question

Ho visto alberi binari e ricerche binarie menzionati in diversi libri che ho letto ultimamente, ma poiché sono ancora all'inizio dei miei studi in Informatica, devo ancora frequentare un corso che tratti veramente di algoritmi e dati strutture in modo serio.

Ho controllato le fonti tipiche (Wikipedia, Google) e la maggior parte delle descrizioni dell'utilità e dell'implementazione (in particolare) degli alberi Rosso-Nero sono risultate dense e difficili da comprendere.Sono sicuro che per qualcuno con il background necessario abbia perfettamente senso, ma al momento sembra quasi una lingua straniera.

Quindi cosa rende gli alberi binari utili in alcune delle attività più comuni che ti ritrovi a svolgere durante la programmazione?Oltre a ciò, quali alberi preferisci utilizzare (includi un'implementazione di esempio) e perché?

Answer 1

Gli alberi rosso-neri sono ottimi per creare alberi ben bilanciati.Il problema principale con gli alberi di ricerca binari è che puoi sbilanciarli molto facilmente.Immagina che il tuo primo numero sia un 15.Quindi tutti i numeri successivi sono sempre più piccoli di 15.Avrai un albero molto pesante sul lato sinistro e non ha nulla sul lato destro.

Gli alberi Rosso Nero risolvono il problema forzando il bilanciamento dell'albero ogni volta che si inserisce o si elimina.Ciò avviene attraverso una serie di rotazioni tra nodi antenati e nodi figli.L'algoritmo è in realtà piuttosto semplice, anche se è un po' lungo.Suggerirei di prendere il libro di testo CLRS (Cormen, Lieserson, Rivest e Stein), "Introduzione agli algoritmi" e di leggere su RB Trees.

Inoltre, l'implementazione non è così breve, quindi probabilmente non è meglio includerla qui.Tuttavia, vengono utilizzati gli alberi ampiamente per app ad alte prestazioni che necessitano di accesso a molti dati.Forniscono un modo molto efficiente per trovare i nodi, con un sovraccarico relativamente piccolo di inserimento/eliminazione.Ancora una volta, suggerirei di consultare CLRS per documentarsi su come vengono utilizzati.

Sebbene i BST non possano essere utilizzati esplicitamente, un esempio dell'uso degli alberi in generale si trova in quasi ogni singolo RDBMS moderno.Allo stesso modo, il tuo file system è quasi certamente rappresentato come una sorta di struttura ad albero e anche i file sono indicizzati in questo modo.Gli alberi alimentano Google.Gli alberi alimentano quasi tutti i siti Web su Internet.

Answer 2

Vorrei rispondere solo alla domanda "Quindi cosa rende utili gli alberi binari in alcune delle attività comuni che ti ritrovi a svolgere durante la programmazione?"

Questo è un argomento importante su cui molte persone non sono d’accordo.Alcuni sostengono che gli algoritmi insegnati in una laurea in informatica, come gli alberi di ricerca binari e i grafici diretti, non vengono utilizzati nella programmazione quotidiana e sono quindi irrilevanti.Altri non sono d'accordo, dicendo che questi algoritmi e strutture dati sono il fondamento di tutta la nostra programmazione ed è essenziale capirli, anche se non devi mai scriverne uno tu stesso.Questo filtra in conversazioni sulle buone pratiche di colloquio e assunzione.Per esempio, Steve Yegge ha un articolo su colloquio presso Google che affronta questa domanda.Ricorda questo dibattito;le persone esperte non sono d'accordo.

Nella tipica programmazione aziendale potrebbe non essere necessario creare alberi binari o addirittura alberi molto spesso.Tuttavia, utilizzerai molte classi che operano internamente utilizzando gli alberi.Molte delle classi organizzative principali in ogni lingua utilizzano alberi e hash per archiviare e accedere ai dati.

Se sei coinvolto in attività o situazioni ad alte prestazioni che sono in qualche modo fuori dalla norma della programmazione aziendale, troverai gli alberi come tuoi amici immediati.Come ha detto un altro utente, gli alberi sono strutture dati fondamentali per database e indici di tutti i tipi.Sono utili nel data mining e nella visualizzazione, nella grafica avanzata (2D e 3D) e in una serie di altri problemi computazionali.

Ho utilizzato alberi binari sotto forma di Alberi BSP (partizionamento binario dello spazio). nella grafica 3D.Attualmente sto esaminando di nuovo gli alberi per ordinare grandi quantità di dati geocodificati e altri dati per la visualizzazione delle informazioni nelle applicazioni Flash/Flex.Ogni volta che si stanno spingendo i limiti dell'hardware o si desidera eseguire specifiche hardware inferiori, comprendere e selezionare l'algoritmo migliore può fare la differenza tra fallimento e successo.

Answer 3

Nessuna delle risposte menziona esattamente a cosa servono i BST.

Se quello che vuoi fare è semplicemente cercare in base ai valori, una tabella hash è molto più veloce, inserimento e ricerca O (1) (caso migliore ammortizzato).

Un BST sarà una ricerca O(log N) dove N è il numero di nodi nell'albero, anche gli inserti sono O(log N).

Gli alberi RB e AVL sono importanti come un'altra risposta menzionata a causa di questa proprietà, se viene creato un semplice BST con valori in ordine, l'albero sarà alto quanto il numero di valori inseriti, questo è negativo per le prestazioni di ricerca.

La differenza tra gli alberi RB e AVL risiede nelle rotazioni richieste per il ribilanciamento dopo un inserimento o un'eliminazione, gli alberi AVL sono O(log N) per i ribilanciamenti mentre gli alberi RB sono O(1).Un esempio di vantaggio di questa complessità costante è nel caso in cui potresti mantenere un'origine dati persistente, se hai bisogno di tenere traccia delle modifiche per il rollback dovresti tenere traccia di O (log N) possibili modifiche con un albero AVL.

Perché saresti disposto a pagare il costo di un albero su una tabella hash?ORDINE!Le tabelle hash non hanno ordine, i BST invece sono sempre naturalmente ordinati in virtù della loro struttura.Quindi, se ti ritrovi a gettare un mucchio di dati in un array o in un altro contenitore e poi a ordinarli in seguito, un BST potrebbe essere una soluzione migliore.

La proprietà order dell'albero offre una serie di funzionalità di iterazione ordinate, in ordine, prima in profondità, prima in ampiezza, pre-ordine, post-ordine.Questi algoritmi di iterazione sono utili in diverse circostanze se vuoi cercarli.

Gli alberi rosso-neri vengono utilizzati internamente in quasi tutti i contenitori ordinati di librerie di lingua, C++ Set and Map, .NET SortedDictionary, Java TreeSet, ecc...

Quindi gli alberi sono molto utili e potresti usarli abbastanza spesso senza nemmeno saperlo.Molto probabilmente non lo farai mai Bisogno scriverne uno tu stesso, anche se lo consiglio vivamente come interessante esercizio di programmazione.

Answer 4

Gli alberi Red Black e B-tree vengono utilizzati in tutti i tipi di archiviazione persistente;poiché gli alberi sono equilibrati le prestazioni degli attraversamenti in larghezza e profondità sono mitigate.

Quasi tutti i moderni sistemi di database utilizzano alberi per l'archiviazione dei dati.

Answer 5

I BST fanno girare il mondo, come detto da Micheal.Se stai cercando un buon albero da implementare, dai un'occhiata Alberi AVL (Wikipedia).Hanno una condizione di bilanciamento, quindi è garantito che siano O(logn).Questo tipo di efficienza di ricerca rende logico l'inserimento in qualsiasi tipo di processo di indicizzazione.L'unica cosa che sarebbe più efficiente sarebbe una funzione di hashing, ma quelle diventano brutte velocemente, velocemente e in fretta.Inoltre, ti imbatti nel Paradosso del compleanno (noto anche come problema della casella).

Che libro di testo stai usando?Abbiamo usato Strutture dati e analisi in Java di Mark Allen Weiss.In realtà ce l'ho aperto sulle ginocchia mentre scrivo questo.Ha un'ottima sezione sugli alberi Rosso-Neri e include anche il codice necessario per implementare tutti gli alberi di cui parla.

Answer 6

Gli alberi rosso-neri rimangono in equilibrio, quindi non devi attraversare in profondità per estrarre gli oggetti.Il tempo risparmiato rende gli alberi RB O(log()n)) nel caso PEGGIORE, mentre gli alberi binari sfortunati possono entrare in una configurazione sbilanciata e causare recuperi in O(n) in un caso negativo.Ciò accade nella pratica o su dati casuali.Pertanto, se hai bisogno di codice critico in termini di tempo (recuperi di database, server di rete ecc.), utilizzi gli alberi RB per supportare elenchi/insiemi ordinati o non ordinati.

Ma gli RBTree sono per i principianti!Se stai facendo intelligenza artificiale e hai bisogno di eseguire una ricerca, ti accorgi che forzi molte informazioni sullo stato.È possibile utilizzare un rosso-nero persistente per creare nuovi stati in O(log(n)).Un albero rosso nero persistente conserva una copia dell'albero prima e dopo un'operazione morfologica (inserimento/eliminazione), ma senza copiare l'intero albero (normalmente e l'operazione O(log(n))).Ho reso open source un albero rosso-nero persistente per Java

http://edinburghhacklab.com/2011/07/a-java-implementation-of-persistent-red-black-trees-open-sourced/

Answer 7

La migliore descrizione degli alberi rosso-neri che ho visto è quella in "Introduzione agli algoritmi" di Cormen, Leisersen e Rivest.Potrei anche capirlo abbastanza per implementarne parzialmente uno (solo inserimento).Ci sono anche alcune applet come Questo su varie pagine web che animano il processo e consentono di osservare e scorrere una rappresentazione grafica dell'algoritmo che costruisce una struttura ad albero.

Answer 8

Dato che chiedi quale albero usano le persone, devi sapere che un albero Rosso Nero è fondamentalmente un albero B 2-3-4 (cioè un albero B di ordine 4).Un albero B lo è non equivalente a un albero binario (come chiesto nella tua domanda).

Quiè un'eccellente risorsa che descrive l'astrazione iniziale nota come B-tree binario simmetrico che successivamente si è evoluto in RBTree.Avresti bisogno di una buona conoscenza degli alberi B prima che abbia senso.Riassumere:un collegamento "rosso" su un albero rosso nero è un modo per rappresentare i nodi che fanno parte di un nodo dell'albero B (valori all'interno di un intervallo di chiavi), mentre i collegamenti "neri" sono nodi collegati verticalmente in un albero B.

Quindi, ecco cosa ottieni quando traduci le regole di un albero Rosso Nero in termini di un albero B (sto usando il formato Regola dell'albero rosso nero => B Albero equivalente):

1) Un nodo è rosso o nero.=> Un nodo in un b-tree può essere parte di un nodo o come nodo in un nuovo livello.

2) La radice è nera.(Questa regola viene talvolta omessa, poiché non influisce sull'analisi) => Il nodo radice può essere pensato sia come parte di un nodo radice interno che come figlio di un nodo genitore immaginario.

3) Tutte le foglie (NIL) sono nere.(Tutte le foglie sono dello stesso colore della radice.) => Poiché un modo di rappresentare un albero RB è omettere le foglie, possiamo escluderlo.

4)Entrambi i figli di ogni nodo rosso sono neri.=> I figli di un nodo interno in un albero B si trovano sempre su un altro livello.

5)Ogni cammino semplice da un dato nodo a una qualsiasi delle sue foglie discendenti contiene lo stesso numero di nodi neri.=> Un albero B viene mantenuto in equilibrio poiché richiede che tutti i nodi foglia siano alla stessa profondità (quindi l'altezza di un nodo dell'albero B è rappresentata dal numero di collegamenti neri dalla radice alla foglia di un albero Rosso Nero )

Inoltre, esiste un'implementazione "non standard" più semplice di Robert Sedgewick Qui:(È l'autore del libro Algoritmi insieme a Wayne)

Answer 9

C'è tanto, tanto calore qui, ma poca luce, quindi vediamo se riusciamo a fornirne un po'.

Primo, un albero RB è una struttura dati associativa, a differenza, ad esempio, di un array, che non può accettare una chiave e restituire un valore associato, beh, a meno che non sia una "chiave" intera in un indice sparso dello 0% di interi contigui.Nemmeno un array può aumentare di dimensioni (sì, conosco anche realloc(), ma sotto le coperte richiede un nuovo array e quindi un memcpy()), quindi se hai uno di questi requisiti, un array non va bene .L'efficienza della memoria di un array è perfetta.Zero sprechi, ma non molto intelligente o flessibile - nonostante realloc().

Secondo, a differenza di bsearch() su un array di elementi, che È una struttura dati associativa, un albero RB può crescere (E ridursi) di dimensioni in modo dinamico.bsearch() funziona bene per indicizzare una struttura dati di dimensione nota, che rimarrà di quella dimensione.Quindi, se non conosci in anticipo la dimensione dei tuoi dati, o è necessario aggiungere o eliminare nuovi elementi, è disponibile bsearch().Bsearch() e qsort() sono entrambi ben supportati nel C classico e hanno una buona efficienza della memoria, ma non sono abbastanza dinamici per molte applicazioni.Sono però i miei preferiti perché sono veloci, facili e, se non hai a che fare con app in tempo reale, molto spesso sono abbastanza flessibili.Inoltre, in C/C++ è possibile ordinare un array di puntatori a record di dati, puntando, ad esempio, al membro struc{} che si desidera confrontare, e quindi riorganizzare il puntatore nell'array di puntatori in modo tale che la lettura dei puntatori in ordine alla fine del puntatore sort restituisce i dati in ordine ordinato.L'utilizzo di questo con file di dati mappati in memoria è estremamente efficiente in termini di memoria, veloce e abbastanza semplice.Tutto quello che devi fare è aggiungere alcuni "*" alle funzioni di confronto.

Terzo, a differenza di una tabella hash, che anch'essa deve avere una dimensione fissa e non può essere ampliata una volta riempita, un albero RB crescerà automaticamente e si bilancerà per mantenere la sua garanzia di prestazioni O(log(n)).Soprattutto se la chiave dell'albero RB è un int, può essere più veloce di un hash, perché anche se la complessità di una tabella hash è O(1), quell'1 può essere un calcolo dell'hash molto costoso.I confronti multipli di interi di 1 clock di un albero spesso superano i calcoli di hash di oltre 100 clock, per non parlare del rehashing e dello spazio di malloc() per collisioni di hash e rehash.Infine, se si desidera l'accesso ISAM, nonché l'accesso con chiave ai propri dati, è escluso un hash, poiché non esiste un ordinamento dei dati inerente alla tabella hash, in contrasto con l'ordinamento naturale dei dati in qualsiasi implementazione dell'albero.L'uso classico di una tabella hash è fornire accesso con chiave a una tabella di parole riservate per un compilatore.L'efficienza della memoria è eccellente.

Il quarto, e molto in basso in qualsiasi elenco, è l'elenco collegato, o doppiamente collegato, che, a differenza di un array, supporta naturalmente l'inserimento e l'eliminazione di elementi e, come ciò implica, il ridimensionamento.È la più lenta di tutte le strutture dati, poiché ogni elemento sa solo come arrivare all'elemento successivo, quindi devi cercare, in media, collegamenti (element_knt/2) per trovare il tuo dato.Viene utilizzato principalmente dove sono comuni inserimenti ed eliminazioni da qualche parte nel mezzo dell'elenco e, soprattutto, dove l'elenco è circolare e alimenta un processo costoso che rende il tempo per leggere i collegamenti relativamente ridotto.Il mio RX generale consiste nell'utilizzare un array arbitrariamente grande anziché un elenco collegato se l'unico requisito è che possa aumentare di dimensioni.Se esaurisci le dimensioni di un array, puoi riallocare() un array più grande.L'STL lo fa per te "sotto le coperte" quando usi un vettore.Grezzo, ma potenzialmente migliaia di volte più veloce se non sono necessari inserimenti, eliminazioni o ricerche con chiave.L'efficienza della memoria è scarsa, soprattutto per gli elenchi doppiamente collegati.In effetti, una lista doppiamente concatenata, che richiede due puntatori, è esattamente inefficiente in termini di memoria quanto un albero rosso-nero, pur non avendo NESSUNA delle sue attraenti caratteristiche di recupero veloce e ordinato.

Quinto, gli alberi supportano molte operazioni aggiuntive sui loro dati ordinati rispetto a qualsiasi altra struttura di dati.Ad esempio, molte query di database sfruttano il fatto che un intervallo di valori foglia può essere facilmente specificato specificando il loro genitore comune e quindi concentrando l'elaborazione successiva sulla parte dell'albero che il genitore "possiede".Il potenziale per il multi-threading offerto da questo approccio dovrebbe essere ovvio, poiché solo una piccola regione dell'albero deve essere bloccata, vale a dire solo i nodi che possiede il genitore e il genitore stesso.

In breve, gli alberi sono la Cadillac delle strutture dati.Si paga un prezzo elevato in termini di memoria utilizzata, ma si ottiene una struttura dati completamente autogestita.Questo è il motivo per cui, come sottolineato in altre risposte qui, i database delle transazioni utilizzano quasi esclusivamente alberi.

Answer 10

Se desideri vedere come dovrebbe apparire graficamente un albero Rosso-Nero, ho codificato un'implementazione di un albero Rosso-Nero che puoi scarica qui

Answer 11

IME, quasi nessuno capisce l'algoritmo dell'albero RB.Le persone possono ripeterti le regole, ma non capiscono Perché quelle regole e da dove provengono.Non faccio eccezione :-)

Per questo motivo preferisco l'algoritmo AVL, perché è facile comprendere.Una volta capito, puoi codificarlo da zero, perché ha senso per te.

Answer 12

Gli alberi possono essere veloci.Se in un albero binario bilanciato sono presenti un milione di nodi, sono necessari in media venti confronti per trovare un elemento qualsiasi.Se in un elenco collegato sono presenti un milione di nodi, sono necessari in media cinquecentomila confronti per trovare lo stesso elemento.

Se l'albero è sbilanciato, però, può essere lento quanto un elenco, E richiedono anche più memoria da archiviare.Immagina un albero in cui la maggior parte dei nodi ha un figlio destro, ma nessun figlio sinistro;Esso È un elenco, ma devi comunque mantenere spazio di memoria da inserire nel nodo sinistro se ne viene visualizzato uno.

Comunque, il Albero AVL è stato il primo algoritmo ad albero binario bilanciato e l'articolo di Wikipedia su di esso è abbastanza chiaro.L'articolo di Wikipedia sugli alberi rosso-neri è chiaro come il fango, onestamente.

Oltre agli alberi binari, i B-Tree sono alberi in cui ogni nodo può avere molti valori.B-Tree lo è non un albero binario, guarda caso ne è il nome.Sono davvero utili per utilizzare la memoria in modo efficiente;ogni nodo dell'albero può essere dimensionato per adattarsi a un blocco di memoria, in modo da non andare (lentamente) a trovare tonnellate di cose diverse nella memoria che è stata paginata su disco.Ecco un esempio fenomenale di B-albero.