Python的标准库中是否有用于平衡二叉树的模块？

Question

Python的标准库中是否有用于AVL tree或red–black tree或其他类型的平衡二叉树的模块

Answer 1

在一些例子中，我发现heapq package（在Statndard库中）是有用的，特别是在任何给定的时间，如果您希望O（1）访问集合中最小的元素

对我来说，我一直在跟踪计时器的集合，通常只想检查最短的时间（首先执行的时间）是否已经准备就绪

Answer 2

在stdlib中没有类似的内容，但是as far as I can see，而是quick look at pypi brings up a few alternative：

• rbtree
• pyavl
• blist

Answer 3

不，stdlib中没有平衡的二叉树。但是，从您的评论来看，您可能还有其他选择：

• 你说你想要一个BST而不是一个用于O(log n)搜索的列表。如果您只需要搜索，并且您的数据已经排序，那么bisect模块为列表提供了一个二进制搜索算法
• Mike DeSimone推荐了集合和dict，你解释了为什么列表在算法上太慢。集合和DICT实现为哈希表，具有O（1）查找。Python中大多数问题的解决方案实际上是“使用dict”

如果两种解决方案都不适合您，您将不得不转到第三方模块或实现自己的模块