Implementazione di Red-Black Tree in C#

Sto cercando un'implementazione di un Red-Black Tree in C#, con le seguenti caratteristiche:Implementazione di Red-Black Tree in C#

ricerca, inserire e cancellare in O (log n).
Il tipo di membro deve essere generico.
Supporto in Comparer(T), per ordinare T da diversi campi in esso.
La ricerca nell'albero deve essere con il campo specifico, quindi non accetta T, ma accetta il tipo di campo che lo ordina.
La ricerca non deve essere solo il valore esatto. Dovrebbe supportare la ricerca di quello inferiore/superiore.

Grazie.

fonte

2009-11-09 Alon Gubkin

Rispondendo alla tua altra domanda, denominata "Libro o Insegnante", il * vero * modo migliore per apprendere la programmazione è * scrivere programmi *. Scrivi questo per conto tuo e poi imparerai qualcosa. –

@Pavel: Potrei scrivere questo, ma sto cercando qualcosa di pronto, così posso continuare a sviluppare i lati principali del mio programma e accelerare lo sviluppo. –

Per lo più ho appena descritto SortedDictionary<T, U>, ad eccezione della ricerca binaria con valore inferiore/successivo più prossimo, che è possibile implementare da soli senza troppe difficoltà.

Ci sono motivi specifici per cui lo SortedDictionary è insufficiente?

fonte

2009-11-09 19:47:04 mquander

* "che potresti implementare da solo senza troppe difficoltà." * Non credo che si possa facilmente estendere SortedDictionary. Guardando i metadati e semplicemente cercando di estenderli, i pezzi interni necessari non sembrano accessibili. Ho sbagliato? – Catskul

Vuoi dire che il SortedDictionary implementa un albero rosso-nero? Se lo fai, dove l'hai trovato? Non vedo alcuna menzione su di esso nelle pagine MSDN. – comecme

Sì; L'ho appena verificato sfogliando la classe in Reflector. Internamente, inserisce le chiavi in un 'SortedSet ', che è implementato come un albero rosso/nero. Non sono sicuro di dove l'ho sentito - mi sento come se una vecchia versione della documentazione MSDN entrasse in maggiori dettagli sull'implementazione di "SortedDictionary" in contrasto con "SortedList". Inoltre, non sono esattamente sicuro del motivo per cui ho pensato che avrebbe potuto estenderlo facilmente.Non è chiaro che potesse. Oh bene. – mquander

Strappa TreeSet dalle librerie di raccolta C5.

fonte

2009-11-09 19:46:44

Questo è esattamente OrderedDictionary in PowerCollections. È praticamente identico a SortedDictionary (albero nero rosso con generici) con l'aggiunta della possibilità di impostare un tasto di inizio/fine e di scansionare tutti i valori in quell'intervallo.

SortedDicionary consente solo di esporre una funzione GetEnumerator() che inizia all'inizio della raccolta e consente solo una chiamata a MoveNext(), quindi anche se si utilizza LINQ non si verifica nulla di magico: si avvia all'inizio e si esegue il espressione su ogni singolo nodo, in ordine, fino a quando non trova quelli corrispondenti alla tua espressione LINQ.

OrderedDictionary ha una funzione che ottiene un enumeratore in corrispondenza di o prima di una determinata chiave e che esegue la ricerca in O (log n).

Una parola di cautela però: l'enumeratore nella PowerCollections OrderedDictionary è implementato utilizzando "resa" e l'utilizzo della memoria e le prestazioni di enumerazione è almeno O (n^2) ... è possibile modificare l'implementazione te stesso per renderlo implementare un enumeratore tradizionale ed entrambi questi problemi vanno via. Presenterò quella patch a Codeplex se riuscirò mai a trovare il tempo.

fonte

2013-02-11 19:09:00 huntharo

Implementazione di Red-Black Tree in C#

risposta

Problemi correlati