BinarySearchTree

The Binary Search Tree data structure

public class BinarySearchTree<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 int CompareTo(object obj);
    public bool Contains(KeyValuePair<TKey, TValue> item);
    public bool ContainsKey(TKey key);
    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex);
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
    public IEnumerator<KeyValuePair<TKey, TValue>> GetSortedEnumerator();
    public bool Remove(KeyValuePair<TKey, TValue> item);
    public bool Remove(TKey key);
    public bool TryGetValue(TKey key, out TValue value);
    
    // ...

    // Properties
    public IComparer<TKey> Comparer { get; }
    public int Count { get; }
    public bool IsEmpty { get; }
    public bool IsFixedSize { get; }
    public bool IsFull { get; }
    public bool IsReadOnly { get; }
    public TValue this[TKey key] { get; set; }
    public ICollection<TKey> Keys { get; }
    public KeyValuePair<TKey, TValue> Max { get; }
    public KeyValuePair<TKey, TValue> Min { get; }
    public ICollection<TValue> Values { get; } 
    
    // ...
}

A Binary Search tree is a search data structure that takes the form of a Binary Tree. It's inner workings are simple : items less than the parent node are placed in the left subtree, and items larger in the right subtree. This allows for quick searching of items by eliminating more items on each level. One of it's worst cases, however, is adding items in sequential order - O(n) comparisons are necessary in the worst case. However, because of it's simplicity it's a suitable search data structure for cases where the input will be randomized. Where randomized data can not be ensured, the use of a balanced search tree (like a [RedBlackTree Red Black Tree]) is recommended.

More Information