Python的标准库 - 是否存在平衡二叉树的模块？

Question

在Python的标准库中是否有AVL或Red-Black模块或其他类型的平衡二叉树？我试图找到一个,但没有成功(我对Python比较新).

Answer 1

不,stdlib中没有平衡的二叉树.但是,根据您的评论,听起来您可能还有其他选择:

你说你想要一个BST而不是一个O(log n)搜索列表.如果您只需搜索并且您的数据已经排序,则bisect模块会为列表提供二进制搜索算法.
Mike DeSimone建议使用集合和dicts,并解释了为什么列表在算法上太慢.集合和dicts实现为散列表,其具有O(1)查找.Python中大多数问题的解决方案实际上是"使用dict".

如果两种解决方案都不适合您,则必须转到第三方模块或实施自己的模块.

非常感谢你！使用一套解决了我的问题。我不知道他们在Python中有O（1）查找（我一直认为在找到正确的值之前应该遍历整个集合-但正如我所说的，我是Python的新手）。也感谢您对Python中常用数据结构的解释。 (2认同)

Answer 2

还有一个快速为C但纯Python的实现称为[sortedcontainers](http://www.grantjenks.com/docs/sortedcontainers/)文档有一个很好的[性能比较](http://www.grantjenks .com/docs/sortedcontainers/performance.html)以及您列出的替代方案. (7认同)

Answer 3

有一些实例我发现heapq包(在stadndard库中)很有用,特别是在任何给定时间你想要O(1)访问集合中最小元素的时间.

对我来说,我正在跟踪一组计时器,并且通常只是想检查最小的时间(首先执行的那个)是否准备好了.

Answer 4

有一个名为"bintrees"的新软件包支持不平衡,AVL和RB树.你可以在这里找到它.

来自https://pypi.python.org/pypi/bintrees/2.0.1:"编译快速树需要Cython,在Windows上是必需的C编译器(MingW工作正常)." (3认同)

Answer 5

另请查看Sorted Containers项目。

这是关于它的 PyCon 讨论：https : //www.youtube.com/watch?v= 7z2Ki44Vs4E