Creating a whole new collection requires some preliminary work. We need to have new algorithms or new internal data structures that offer significant improvements over the built-in collections. It's important to do thorough Big-O complexity calculations before designing a new collection. It's also important to use timeit after an implementation to be sure that the new collection really is an improvement over available built-in classes.

We might, for example, want to create a binary search tree structure that will keep the elements in a proper order. As we want this to be a mutable structure, we'll have to perform the following kinds of design activities:

• Design the essential binary tree structure.
• Decide which structure is the basis: MutableSequence, MutableMapping, or MutableSet.
• Look at the special methods for the collection in the collections.abc section of the Python Standard Library documentation, section 8.4.1.

A binary search tree has nodes that contain a key value, and two branches: a less than branch for all keys less than this node's key, and a greater than or equal to branch for keys greater than, or equal to, this node's key.

We need to examine the fit between our collection and the Python ABCs:

• A binary tree doesn't fit well with some sequence features. Notably, we don't often use an integer index with a binary tree. We most often refer to elements in a search tree by their key. While we can impose an integer index without too much difficulty, it will involve tree traversals.
• A tree could be used for the keys of a mapping; this would keep the keys in a sorted order at a relatively low cost.
• It is a good alternative to a set or a Counter class because it can tolerate multiple copies of a key, making it easily bag-like.

We'll look at creating a sorted multiset or a bag. This can contain multiple copies of an object. It will rely on relatively simple comparison tests among objects.

This is a rather complex design. There are a great many details. To create a background, it's important to read articles such as http://en.wikipedia.org/wiki/Binary_search_tree. At the end of the previous Wikipedia page are a number of external links that will provide further information. It's essential to study the essential algorithms in books such as Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein; Data Structures and Algorithms by Aho, Ullman, and Hopcroft; or The Algorithm Design Manual by Steven Skiena.