public class RedBlackTree<TKey, TValue> : IVisitableDictionary<TKey, TValue>
{
    // Methods    
    public void Accept(IVisitor<KeyValuePair<TKey, TValue>> visitor);
    public void Add(KeyValuePair<TKey, TValue> item);
    public void Add(TKey key, TValue value);    
    public bool Contains(KeyValuePair<TKey, TValue> item);
    public bool ContainsKey(TKey key);    
    public void DepthFirstTraversal(OrderedVisitor<KeyValuePair<TKey, TValue>> visitor);    
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
    public bool Remove(TKey key);
    public bool TryGetValue(TKey key, out TValue value);

    // ...

    // Properties
    public IComparer<TKey> Comparer { get; }
    public TValue this[TKey key] { get; set; }
    public ICollection<TKey> Keys { get; }
    public TKey Max { get; }
    public TKey Min { get; }
    public ICollection<TValue> Values { get; }
    
    // ...
}

The Red Black Tree is a self-balancing binary search tree. What this means, essentially, is that the the length of paths from the root node to child nodes are controlled - so you can't get an extremely long path to one node, and short paths to the others (which degrades search performance).

The Red Black Tree implemented in NGenerics implements the IDictionary<TKey, TValue> interface.

The insertion and removal algorithms were adapted from Julienne Walker's (Eternally confuzzled) algorithms - if you want to learn about Red Black Trees, look there first.

More information on Red Black trees