Is there a module for balanced binary tree in Python's standard library?

python tree standard-library
aeter picture aeter · Feb 19, 2010 · Viewed 38.6k times · Source

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?

Answer

Mike Graham picture Mike Graham · Feb 19, 2010

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.

Related questions

How can I implement a tree in Python?

I am trying to construct a General tree. Are there any built-in data structures in Python to implement it?

Read More
Tree plotting in Python

I want to plot trees using Python. Decision trees, Organizational charts, etc. Any library that helps me with that?

Read More
Plot trees for a Random Forest in Python with Scikit-Learn

I want to plot a decision tree of a random forest. So, i create the following code: clf = RandomForestClassifier(n_estimators=100) import pydotplus import six from sklearn import tree dotfile = six.StringIO() i_tree = 0 for tree_in_forest in clf.…

Read More