Ho letto molti articoli sull'albero nero rosso dove impiega tempo O (log n) per le operazioni. Non sono molto chiaro come funzioni e in che modo la mappa ad albero utilizza l'algoritmo albero nero rosso bilanciare l'albero rispetto all'albero di ricerca binario.Come la mappa ad albero utilizza l'algoritmo albero nero rosso
Qualcuno può spiegare con un esempio di come funziona l'algoritmo.
Un albero rosso-nero è un albero di ricerca binario. È solo un assaggio di BST che ha versioni fantasiose delle operazioni insert e delete che riorganizzano l'albero mentre corrono in modo che l'albero non diventi "lungo e filante". Più lungo e più intenso diventa un albero, più si comporta come una lista collegata. In media, le operazioni di lista collegate richiedono la metà della lista da toccare (o l'intera lista nel caso peggiore), quindi il tempo di esecuzione varia linearmente (O (n) nel numero di elementi n). Quando l'albero è "cespuglioso" o quasi equilibrato, le operazioni sono molto più economiche (O (log n)) ciascuna. Gli algoritmi rosso-nero garantiscono che l'albero resti cespuglioso.
Per fare questo concreto, qui ci sono due alberi che memorizzano i tasti da A a G. La sinistra è lunga e filante. Nota come sembra una lista. Nel peggiore dei casi, occorrono 4 confronti chiave per trovare un elemento. L'albero sulla destra è folto. Ne ha bisogno solo 3. Qui la differenza è piccola. Per un albero di 1023 elementi, l'albero filato richiede 512 confronti e quello cespuglioso solo 10. Questa è la potenza del registro n.
B _D_
/\ / \
A D B F
/\ /\ /\
C F A C E G
/\
E G
L'albero rosso-nero non è garantito per essere perfettamente folta (nella terminologia corretta "perfettamente bilanciato"), ma le regole rosso-neri garantisce che è abbastanza folta in modo matematicamente rigoroso in modo che i tempi di funzionamento variare come il log di n piuttosto che linearmente in n.
Il genio delle regole rosso-nere è che sono "locali". Durante un inserimento o una cancellazione che infrange le regole, è possibile ripristinarle regolando solo un numero costante di nodi per ciascun nodo toccato dall'operazione. Pertanto sono economici e abbastanza facili da implementare.
Tuttavia, quando le regole rosso-nere sono vere per l'intero albero, è possibile dimostrare con una prova matematica intelligente che è abbastanza cespugliosa come descritto sopra.
E la mappa dell'albero? Una mappa è una funzione con un dominio chiamato il set di chiavi K e l'intervallo chiamato il valore impostato V. Per implementare una mappa ad albero, ogni nodo memorizza una coppia chiave-valore <k,v> dove k \in K e v \in V. Nei disegni sopra (e nella maggior parte delle presentazioni), vengono mostrati solo i tasti (lettere A-G). Nella mappa, l'inserimento, la ricerca e la cancellazione funzionano su queste coppie in un modo abbastanza ovvio. Ad esempio, la ricerca cerca una chiave usando il solito algoritmo BST. Quando viene trovata la chiave, il valore viene trovato anche perché si trova nella stessa coppia. Questo è ciò che viene restituito. In Java, la coppia si chiama Map.Entry. Puoi verificarlo nello Java source code.
Non entrerò nei dettagli su come funzionano le regole rosso-nere perché non ho potuto migliorare su the Wikipedia page. La mia ipotesi e speranza è che ti mancasse il "quadro generale", quindi ora la discussione avrà un senso. La buona notizia è che quasi tutte le lingue forniscono un'implementazione degli alberi accuratamente testata e ottimizzata per le prestazioni, quindi non è necessario conoscere gli arcani dettagli delle rotazioni. Certo, se sei curioso e vuoi solo sapere, abbi! Complimenti!
Per quello che vale, le spiegazioni degli algoritmi di Top Coder non sono sempre le più chiare. Dai la caccia agli altri fino a quando uno "fa clic" per te.I libri di testo rispettati in CS sono rispettati per una ragione: le loro spiegazioni sono eccellenti. Corman and Rivest è un preferito accettato.
Prima di tutto, dovresti essere più specifico riguardo alla tua domanda. Specifica cosa sai, cosa non fai e cosa hai provato.
Venendo alla domanda, TreeMap e alberi rosso-nero sono concetti completamente diversi. La comprensione concettuale di entrambi non dipende affatto dall'altra e suggerisco di non confonderli. Non ti darò la risposta esatta, piuttosto darò una breve panoramica dei concetti e della sequenza in cui devi impararli (IMO).
StruttureLa mappa di dati
i dati della struttura
Io parto dal presupposto si conosce il concetto di Maps e Binary Search Trees. In caso contrario, una semplice ricerca ti porterà a molte buone risorse.
Ora, alla risposta effettiva.
Prima di tutto dovresti sapere quali sono SortedMap e BST autobilanciante.
Che cos'è un SorteMap?
Da Java docs,
una mappa che fornisce inoltre un ordinamento totale sulle sue chiavi. La mappa viene ordinata in base all'ordinamento naturale delle sue chiavi o a un comparatore in genere fornito al momento della creazione della mappa ordinata.
Un SortedMap viene utilizzato quando si desidera ordinare la chiave sottostante, coppie di valori (per chiave). In questo modo, sarebbe più facile recuperare il minimo, il massimo o eseguire operazioni basate sull'intervallo.
Che cos'è un albero di ricerca binaria autobilanciante?
Da wikipedia,
un auto-equilibratura (o altezza bilanciato) albero binario di ricerca è qualsiasi albero binario di ricerca basato sui nodi che mantiene automaticamente la sua altezza (numero massimo di livelli sotto radice) piccolo a fronte di inserimenti e cancellazioni di articoli arbitrari.
Ancora, albero rosso-nero in un'implementazione di BST autobilanciante.Ci sono others come ALV tree, ecc. Il caso peggiore per qualsiasi operazione su un normale BST è O(n). Il vantaggio principale dell'utilizzo di BST bilanciato rispetto a BST normale/non bilanciato è che il caso peggiore di tutte le operazioni viene portato a O(logn) con un piccolo overhead coinvolto nel riarrangiamento dei nodi al momento dell'inserimento/eliminazione. Dai un'occhiata a this.
Quindi, che cos'è una TreeMap?
A TreeMap è un'implementazione di SortedMap.
In che modo sono correlati TreeMap e l'albero rosso-nero?
No, non lo sono. In teoria, è possibile utilizzare uno degli alberi di ricerca binaria per implementare una TreeMap. Per ottenere buoni risultati, utilizziamo alberi di ricerca binaria autobilanciati che hanno una minore complessità temporale per le operazioni di inserimento, cancellazione e recupero. In caso di Java, viene utilizzato l'albero rosso-nero. Non conosco il motivo esatto per cui viene utilizzato l'albero rosso-nero, ma credo che ce ne sia uno.