Python标准库中有平衡二叉树的模块吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
不，stdlib 中没有平衡二叉树。但是，从您的评论来看，您似乎还有其他选择：
O(log n)搜索的列表。如果您只需要搜索并且数据已经排序，则 bisect 模块提供列表的二分搜索算法。如果这两种解决方案都不适合您，您将不得不使用第三方模块或实现您自己的模块。
No, there is not a balanced binary tree in the stdlib. However, from your comments, it sounds like you may have some other options:
O(log n)searches. If searching is all you need and your data are already sorted, thebisectmodule provides a binary search algorithm for lists.If neither solution works well for you, you'll have to go to a third party module or implement your own.
据我所知，stdlib 中没有此类内容，据我所知，但是 快速查看 pypi 会带来一些替代方案：
there is nothing of this sort in stdlib, as far as I can see, but quick look at pypi brings up a few alternative:
在一些情况下，我找到了 heapq 包 （在 stadndard 库中）很有用，特别是在任何给定时间您希望 O(1) 访问集合中最小元素的时间。
对我来说，我正在跟踪一组计时器，通常只是想检查最小的时间（首先执行的时间）是否已经准备好。
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.
另请查看排序容器项目。
这是 PyCon 的讨论：https://www.youtube.com/watch?v=7z2Ki44Vs4E< /a>
Check out also the Sorted Containers project.
Here's a PyCon talk about it: https://www.youtube.com/watch?v=7z2Ki44Vs4E
有一个名为“bintrees”的新软件包，它支持 ubalanced、AVL 和 RB 树。您可以在此处找到它。
There is a new package called "bintrees" which supports ubalanced, AVL and RB trees. You can find it here.
不，但是有 Python 的 AVL 树对象 （非常旧！）和 SourceForge 上的一个（已关闭）项目 - avl-trees for Python。
No, but there's AVL Tree Objects for Python (very old!) and a (closed) project on SourceForge - avl-trees for Python.
我写了一个Python版本的Java TreeMap/TreeSet，其底层数据结构是平衡二叉树（准确地说是红黑树）。
源代码和文档可以在此存储库中访问
您可以使用
pip install pytreemap.测试 Python >=3.5
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