Implementazione di Red-Black Tree in C #

Question

Sto cercando l'implementazione di un Rosso-Nero Albero in C #, con le seguenti caratteristiche:

• Ricerca, inserire e cancellare in O (log n).
• tipo Membri dovrebbe essere generico.
• Supporto nella Comparer (T) , per l'ordinamento T da diversi campi in esso.
• Ricerca nella struttura dovrebbe essere con il settore specifico, in modo da non accetterà T, ma sarà accettare il tipo di campo di smistamento di esso.
• La ricerca non dovrebbe essere solo valore esatto. Dovrebbe sostenere la ricerca quello inferiore / superiore.

Grazie.

Answer 1

È in gran parte appena descritto SortedDictionary<T, U> , tranne che per il prossimo-basso / successivo più alto valore di ricerca binaria, che è possibile implementare sul proprio senza troppe difficoltà.

Ci sono ragioni specifiche che SortedDictionary è insufficiente per voi?

Answer 2

Rip il TreeSet da librerie di raccolta C5.

Answer 3

Questa è esattamente l'OrderedDictionary in PowerCollections. È praticamente identico a SortedDictionary (rosso albero nero con i generici) con l'aggiunta della possibilità di impostare una chiave chiave di inizio / fine e la scansione di tutti i valori in tale intervallo.

SortedDicionary consente solo espone una funzione GetEnumerator (), che comincia all'inizio della raccolta e consente solo un chiamata MoveNext (), quindi, anche se si utilizza LINQ non c'è nulla accade la magia: si parte all'inizio e corre la tua espressione su ogni singolo nodo, al fine, finché non trova quelle corrispondenti espressione tuo LINQ.

OrderedDictionary ha una funzione che ottiene un enumeratore in corrispondenza o prima di una chiave particolare, e che fa 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 da soli per renderlo implementare un enumeratore tradizionale e entrambi questi problemi andare via. Io sostengo che patch per Codeplex se riesco mai a trovare il tempo.