101

Is there a module for an AVL tree or a red–black tree or some other type of a balanced binary tree in the standard library of Python?

Martin Thoma
  • 124,992
  • 159
  • 614
  • 958
aeter
  • 11,960
  • 6
  • 27
  • 29
  • 1
    I just use sets or dictionaries. If I need to use a better hashing routine, I define `__hash__()`. Do you need something fancier? If so, why? BTW, if you can't find it in docs.python.org, it's probably not a standard module. – Mike DeSimone Feb 19 '10 at 17:11
  • 1
    @Mike - I'm trying to solve a task from Project Euler. I think that using a balanced binary search tree instead of a list for one of my data-containers would speed up the algorithm with logarithmic ratio (because of the O(logn) searches), which would solve the task without heating my computer up. Also, I was just curious about it. – aeter Feb 19 '10 at 17:16
  • 1
    What about a set he for O(1) lookups – mmmmmm Feb 19 '10 at 17:19
  • @Mark: Thank you, this seems a better solution for me. What I needed was a data structure with fast adding and fast lookup - and I had no idea that sets are so blazing fast in Python. – aeter Feb 19 '10 at 17:53
  • Possible duplicate of [Does python have a sorted list?](http://stackoverflow.com/questions/1109804/does-python-have-a-sorted-list) – Ciro Santilli OurBigBook.com May 18 '17 at 19:12

7 Answers7

56

No, there is not a balanced binary tree in the stdlib. However, from your comments, it sounds like you may have some other options:

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

If neither solution works well for you, you'll have to go to a third party module or implement your own.

Mike Graham
  • 73,987
  • 14
  • 101
  • 130
  • 2
    Thank you very much! Using a set solved my problem. I had no idea they have O(1) lookups in Python (I have always thought that the whole set should be traversed before finding the right value - but as I said, I'm new to Python). Thank you also for your explanation for the usual data structures in Python. – aeter Feb 19 '10 at 17:51
  • 1
    The implementation of dict or set is based on hash table. Because of the math property of hash functions, the lookups are constant time on average. https://en.wikipedia.org/wiki/Hash_table – Jeanno Nov 19 '18 at 21:31
16

there is nothing of this sort in stdlib, as far as I can see, but quick look at pypi brings up a few alternative:

Devin Jeanpierre
  • 92,913
  • 4
  • 55
  • 79
SilentGhost
  • 307,395
  • 66
  • 306
  • 293
  • 14
    There's also a fast-as-C but pure-Python implementation called [sortedcontainers](http://www.grantjenks.com/docs/sortedcontainers/) The docs have a good [performance comparison](http://www.grantjenks.com/docs/sortedcontainers/performance.html) with the alternatives you list. – GrantJ Aug 11 '14 at 18:56
13

There have been a few instances where I have found the heapq package (in the stadndard library) to be useful, especially if at any given time you want O(1) access time to the smallest element in your collection.

For me, I was keeping track of a collection of timers and was usually just interested in checking if the smallest time (the one to be executed first) was ready to go as of yet.

Paul Osborne
  • 5,024
  • 6
  • 24
  • 20
10

Check out also the Sorted Containers project.

Here's a PyCon talk about it: https://www.youtube.com/watch?v=7z2Ki44Vs4E

postrational
  • 6,306
  • 3
  • 22
  • 27
7

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

Merlyn Morgan-Graham
  • 58,163
  • 16
  • 128
  • 183
Zaur Nasibov
  • 22,280
  • 12
  • 56
  • 83
  • I installed the bintrees module(2.0.1), but when I import it, I get the message: `Warning: FastBinaryTree not available, using Python version BinaryTree.` Any idea how to fix this? I installed Cython, but it still gives that error on import. – yaraju Mar 28 '14 at 11:11
  • I kind of figured out - On Windows, the FastXTree versions need a C compiler installed such as MSVC or Mingw32. I haven't tried it out - as I'll most likely implement a custom tree for my purpose. – yaraju Mar 28 '14 at 13:40
  • 3
    From https://pypi.python.org/pypi/bintrees/2.0.1: "Compiling the fast Trees requires Cython and on Windows is a C-Compiler necessary (MingW works fine)." – yaraju Mar 28 '14 at 13:43
  • @yaraju after installing cython, you need to reinstall bintrees in order to compile the fast extension. – hruske Oct 04 '15 at 21:45
3

No, but there's AVL Tree Objects for Python (very old!) and a (closed) project on SourceForge - avl-trees for Python.

AndiDog
  • 68,631
  • 21
  • 159
  • 205
1

I wrote a Python version of the Java TreeMap/TreeSet, of which the underlying data structure is a balanced binary tree (Red-Black tree to be precise).

Source code and documentation can be accessed in this repo

You can install with pip install pytreemap. Tested for Python >=3.5

GavinPHR
  • 31
  • 1
  • 1