Add binarytree to stdlib - Ideas - Discussions on Python.org
Where's Python's damn binary search tree?
I think you are looking for heapq included in the standard library.
More on reddit.comBuilt-in binary search tree in Python? - Stack Overflow
Best Python 3rd party data structures library? Must have sorted containers at a minimum
Warning: angry rant incoming
I've been using Python for five years now and it's been awesome. Readable syntax, memorable keywords, easy to set up and install, an amazing community, tons of documentation, a great standard library...
But no damn binary search tree - not without having to resort to some unofficial third-party module, at least.
"But Python doesn't need binary search trees because dictionaries are so blazin' fast!"
That's what some people say when the lack of BSTs are brought up. But that's not a good reason! Yes, dictionaries are awesome. Yes, hash tables are the best choice for most circumstances. No, that does not mean that it is acceptable to exclude major data structures from the standard library when other respectable langauges like C, Java, and C# give you a great pre-made BST right out of the box, no third-party imports required.
Why do I care so much? Because hash tables are really inefficient for sorted data operations. If I have a crapton of data and I want to arbitrarily be able to, say, retrieve the 5 biggest elements or traverse the collection in sorted order or anything of that nature, then I would have to sort the hash table's keys first, which would take O(nlogn) time. And yes, I can keep that sorted list in memory, but what if I add and remove some keys from the dict? Boom, now I have to re-sort the list of keys again. If I have to keep doing this over and over again it can add up to a lot of overhead. Sad!
To me, the optimal solution seems to be a self-balancing binary search tree. But self-balancing binary search trees (or B-trees, similarly) are just way too much work for a lazy dev like me to implement myself. And while I'm fine with using third party modules, it's just embarrassing and frankly terrible that such a common data structure, so essential to the world of computing, is not available in Python out of the box. Once again, nearly every language used for serious development provides this, why doesn't Python?
Maybe there is truly, honestly a very legitimate reason why Python has excluded a binary search tree implementation from its standard library. In that case, I would love to be enlightened - it is my understanding that order operations like "get the top 5 elements" or "traverse the set in order" are slow on most non-tree structures. AFAIK, Python doesn't provide any low time-complexity data structures for order operations, and while max(), sort(), and the like are really cool, they just aren't enough to make up for a lack of efficient sorting data structures.
There's no special reason, to my knowledge - I'd guess that the reason is that for so many applications the highly-tuned dict and set implementations (which are hash tables) work well. They're good enough in most cases. There are definitely situations where you need the performance characteristics of balanced binary search trees (like ordered traversal based on key- rather than addition-order), but those are far enough off the beaten path that people are happy with grabbing a third-party package in that case.
I've had a good experience using the bintrees package on PyPI. This has implementations of unbalanced, AVL and red-black binary trees, in both pure Python and as extensions written in Cython.
I think the rest of the reason is essentially historical accident. If the person who wrote bintrees lobbied for its inclusion in the stdlib, and was willing to put up with the constraints that imposes on maintenance and releases, it would probably go in. (Although the Cython dependency would cause a problem, I'd guess.)
Algorithmic complexity:
For hash tables (like dicts or sets), insertion and lookup are O(1), while for a balanced tree these are O(log(n)). In-order traversal of keys is O(n) in a tree, but to do the same thing with a hash table you need to sort the keys first, so it's O(n*log(n)). When you're picking which kind of data structure to use, you need to think about which operations you're going to be using, and pick the tradeoff that makes the most sense in your application.
You won't find any trees in the standard library. Python heavily uses dictionary that is hash table for its internal (object, classes and modules are all based on dicts). Therefore dicts has been greatly optimized. This make the needs for search trees much smaller. Also to be efficient such trees would have been implemented in an extension type.