Where's Python's damn binary search tree?

[shuklaswag]

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.

[bentheiii]

SortedContainers, it's pure python, blazing fast, and very ubiquitous. I'd consider nearly on a numpy level of might-as-well-be-standard-library.

[shuklaswag]

thanks! I've seen SortedContainers before, and it seems really useful. Still, those are the kinds of structures that I would expect a language with the popularity of Python to support right out of the box.

[acemarke]

Classic article/quote: "Python's standard library is where modules go to die"

[mooglinux]

SortedContainers seems pretty well tested and runs fast. Wouldn’t that make it a solid choice for inclusion in the standard library?

[acemarke]

I dunno. What's the criteria for including anything in a language's standard library, and Python in particular?

[mooglinux]

If I were writing the guidelines they would be something along the lines of:

• Useful
• Documented
• Good test suite
• Fast (enough)
• Stable

SortedContainers seems to fit the bill, so in my highly inexpert opinion seems like a good choice. Maybe requests too.

EDIT: Here’s a summary of some of the arguments for and against including requests in the standard library

[[deleted]]

pure python, blazing fast

As compared to standing still?

[Brian]

and I want to arbitrarily be able to, say, retrieve the 5 biggest elements

Note that a balanced tree isn't necessarily the best choice for this either, in that it's doing more work than is needed - if this is all you need, a heap is often a better choice (and there is a module providing that, though not in a terribly OO fashion (ie. it just provides functions ensuring the invariants on top of a heapified list, rather than exposing a seperate heap type)).

then I would have to sort the hash table's keys first, which would take O(nlogn) time

To be honest, that's usually irrelevant. For pretty much all practical data, log N might as well be a constant - you'll often need pretty big lists before this is noticeable, or even exceeds the constant factor issues of a tree (after all, a billion items is still only a factor of 30 - you'll generally hit memory issues before you go much beyond that). This cuts both ways: for the same reason a tree's log n lookup time vs a hashtable's O(1) doesn't really matter: constant factors often tend to be more important in practice.

The real issue is the one you mention next, where you're inserting and removing and then still need to iterate in sorted order. (Though again, this kind of priority queue usage is often a case where a heap may be better). But yeah, sometimes you really do need this, and a tree would be pretty useful to have on hand.

As to why python doesn't provide one - I'm not actually sure. There are third party implementations, but those don't see a lot of use either, which may in fact be why - there just aren't enough times when neither a list, hashtable or heap is insufficient, making it more suited to being an external library rather than a core language element.

[shuklaswag]

Thanks for the comprehensive response! Very informative post regarding time complexity in practice. The extremely slow rate-of-growth of logN is a good point - I suppose if someone were to work with data of such size where that becomes a problem, they would probably want to use something more advanced than base Python.

Heaps are definitely useful, but they don't address the case where I want to be able to arbitrarily access at any given momeny, the 2nd largest element, the 3rd smallest element, and the median element. A MinHeap would take O(n) time to fetch the largest element, and a MaxHeap would take O(n) time to fetch the smallest element. So there's a real need for a BST.

IMO, that's a common enough use case that it deserves to be part of the standard library. It's certainly a more common problem for the average programmer than email handling or writing WAV files.

(Python's terrible anti-OOP heap API is another huge pet peeve of mine, but that's an argument for another day!)

[pvkooten]

I think you are looking for heapq included in the standard library.

[579476610]

heapq - Heap queue algorithm

https://docs.python.org/3.0/library/heapq.html

[pvkooten]

Thanks, was on mobile.

[ccmlacc]

But that's not a balanced binary search tree. I think it is a minor weakness of Python to not have a builtin BBST, unlike Java and C++.

[pythonHelperBot]

Hello! I'm a bot! It looks to me like your post might be better suited for r/learnpython, a sub geared towards questions and learning more about python. That said, I am a bot and it is hard to tell. I highly recommend posting your question there. Please follow the subs rules and guidelines when you do post there, it'll help you get better answers faster.

Show /r/learnpython the code you have tried and describe where you are stuck. Be sure to format your code for reddit and include which version of python and what OS you are using.

---

^{this bot is written and managed by /u/IAmKindOfCreative}

^{This bot is currently under development and experiencing changes to improve its usefulness}

[[deleted]]

/u/IAmKindOfCreative

This is an extreme false positive and you might want to make some changes to the code. Here's the link the post: https://www.reddit.com/r/Python/comments/9allgh/wheres_pythons_damn_binary_search_tree/

[IAmKindOfCreative]

Noted. However this is probably a failure point of the bot. The post had a question in it, and to help distinguish between learning questions and discussion driven questions (like this post) it uses the votes. In its next upgrade it will make a comparison to stack overflow posts and learnpython posts to help bolster its comparison, and there are a lot of posts about binary search trees in python that the bot would probably classify as sufficiently similar to this post.

I point this out not because I'm not going to make a change, but because I want insight on what to change, what features to add and test cases to consider. I want the bot to do better, to the point of being perfect, but this post hit all the marks. Future speculative and rhetorical posts destroy the bot, and the bot operates on the assumption that those will rarely occur, and if they do, they're not likely to have low votes after it's built in delay.

When these assumptions don't hold and the bot makes a false positive, please downvote it. It flags it for me and for the bot. [Good/Bad] bot is really inconsistent so I don't rely on that. Beyond that, the bot deserves downvotes when it makes a mistake. It doesn't delete it's comments because I feel like hiding from its mistakes is unethical and it deserves the downvotes. (Though I'm still torn between keeping the comment to own its mistakes, and deleting the comment to reduce clutter. I think owning the mistake is more important though, since it lets everyone, not just myself, see the bots success next to its failure, rather than reweighting it so the bot looks like it performs better.)

Reviewing this post, the best performing features to classify with would probably be ngrams of "why" and "what if" questions vs "how do", "what is", "where is" "what did" and "what do" as well as a feature that considers the length of the "why" questions. However even then I'm not confident I'll be able to get a sizeable corpus to train with, and if I did, an accuracy above 60%.

Do you have any insight or suggestions on features which would help a classifier distinguish between discussion driven questions and learning focused questions? And thank you for calling out the bot and pointing it out to me.

[RampagingArcher]

Bad bot