SortedSet - Eishaaya/GMRDataStructuresTest GitHub Wiki

Set Theory

In mathematics, a set is a well-defined collection of distinct objects. It itself, can be considered an object. The objects that make up a set can be anything. In general, the ordering of a set is of no importance, however the sorted set data structure that you will implement will be ordered to any arbitrary specified ordering.

Two sets are said to be equal if they have the same elements. As specified above, sets are composed of distinct objects, therefore, no duplicates are ever allowed.

Complexities

A sorted set in itself is an abstract data structure. The goal of this data structure is to represent a collection of objects that are maintained in sorted order. It's target will be to maintain space complexity of O(n) and keep search, insert and delete to O(n). To achieve said goal, we will make use of the red-black tree that was required of you to implement earlier.

Implementation Guide

public interface ISortedSet<T> : IEnumerable<T>
{
    IComparer<T> Comparer { get; }
    int Count { get; }
    void Clear();
    bool Add(T item);
    void AddRange(IEnumerable<T> items);
    bool Contains(T item);
    bool Remove(T item);
    T Max();
    T Min();
    T Ceiling(T item);
    T Floor(T item);
    ISortedSet<T> Union(ISortedSet<T> other);
    ISortedSet<T> Intersection(ISortedSet<T> other);
}

Assignments

  • Implement the sorted set using a red-black tree and test out the floor and ceiling functions.

References

<-- Previous