Built-in binary search tree in Python?

Question

Is there a self-balancing binary search tree (RED-BLACK, AVL or others) built-in types in Python 2.7 or Python 3.x?

I am looking for something that is equivalent to Java TreeMap or TreeSet .

If there are no such built-in modules, why were they skipped? Is there a special reason if you do not include such tools?

Answer 1

For no particular reason, as far as I know, I would suggest that the reason is that for so many applications, the well-configured dict and set implementations (which are hash tables) work well. In most cases, they are good enough. There are certain situations when you need performance characteristics of balanced binary search trees (for example, ordered key-based traversal rather than addition-order), but they are quite far from the beaten path that people are happy with capturing a third-party package in this case.

I had good experience using the bintrees package in PyPI. This has implementations of unbalanced, AVL, and red-black binary trees in both pure Python and extensions written in Cython .

I think the rest of the reason is essentially a historical catastrophe. If the person who wrote bintrees lobbied for his inclusion in stdlib, and was ready to put up with the restrictions that apply to service and releases, he probably will. (Although the dependency of Cython will cause the problem, I would have guessed.)

Algorithmic complexity:

For hash tables (e.g. dicts or sets), insert and search is O (1), while for a balanced tree it is O (log (n)). In the order of the keys, there is O (n) in the tree, but in order to do the same with the hash table, you need to sort the keys first, so that is O (n * log (n)). When you choose which data structure to use, you need to think about what operations you are going to use and choose the compromise that makes the most sense in your application.

Answer 2

You will not find any trees in the standard library. Python makes heavy use of the dictionary, which is a hash table for the internal one (object, classes, and modules are based on dicts). Therefore dicts has been highly optimized. This makes the need for search trees much less. In addition, to be effective, such trees would be implemented in extension.