Python标准库中有平衡二叉树的模块吗？

Question

在Python的标准库里，有没有关于AVL树、红黑树或者其他类型的平衡二叉树的模块呢？

Answer 1

我发现有几次使用到heapq包（这是标准库里的一个工具）非常有用，特别是当你想要以O(1)的时间快速找到你集合中最小的元素时。

对我来说，我在记录一组计时器，通常只关心最小的时间（也就是最先要执行的那个）是否已经准备好了。

Answer 2

在标准库里没有这样的东西，至少我没看到，不过快速浏览一下pypi可以找到一些替代方案：

• rbtree
• pyavl
• blist

Answer 3

不，标准库里没有平衡二叉树。不过，从你的评论来看，你可能还有其他选择：

• 你说你想要一个二叉搜索树（BST），而不是列表，这样可以实现O(log n)的搜索。如果你只需要搜索，并且你的数据已经是排好序的，bisect模块可以为列表提供一种二分查找算法。
• Mike DeSimone推荐使用集合和字典，而你解释了为什么列表在算法上太慢。集合和字典是通过哈希表实现的，查找时间是O(1)。在Python中，大多数问题的解决方案确实是“用字典”。

如果这两种解决方案都不适合你，那你就需要使用第三方模块或者自己实现一个了。