Python standard library - is there a module for balanced binary tree?

Question

Is there a module for AVL or Red-Black, or some other type of balanced binary tree in the Python standard library? I tried to find one, but to no avail (I'm relatively new to Python).

Answer 1

No, there is no balanced binary tree in stdlib. However, from your comments, it seems that you may have other options:

• You say you want to use BST instead of a list to search for O(log n) . If search is all you need and your data is already sorted, the bisect module provides a binary search algorithm for lists.
• Mike DeSimone recommended dialing and dicts, and you explained why lists are too algorithmically slow. Sets and dicts are implemented as hash tables that have O (1) lookups. Solving most of the problems in Python is actually "using a dict."

If none of the solutions is right for you, you will have to upgrade to a third-party module or implement your own.

Answer 2

There is nothing like this in stdlib as far as I can see , but a quick look at pypi brings up several alternatives :

• rbtree
• pyavl
• blist

Answer 3

There were several cases where I found the heapq package (in the stadndard library) to be useful, especially if at any given time that you want O (1) to access the smallest item in your collection.

For me, I kept track of a set of timers and, as a rule, I was just interested in checking if the minimum time (the one that should be executed first) was ready.

Answer 4

There is a new package called "bintrees" that supports ubalanced, AVL and RB trees. You can find it here .

Answer 5

No, but there AVL Tree Objects for Python (very old!) And a (closed) SourceForge project are avl trees for Python .

Answer 6

Check out also the Sorted Containers project.

Here PyCon talks about it: https://www.youtube.com/watch?v=7z2Ki44Vs4E