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

问题描述：

Python 标准库中是否有AVL 树、红黑树或其他类型的平衡二叉树的模块？

解决方案 1：

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

• 你说你想要一个二叉搜索树（BST）而不是列表来进行O(log n)搜索。如果你只需要搜索，并且数据已经排序，那么bisect模块提供了一个用于列表的二分搜索算法。

• Mike DeSimone 推荐了集合和字典，你也解释了为什么列表在算法上太慢了。集合和字典是用哈希表实现的，查找复杂度为 O(1)。Python 中大多数问题的解决方案其实就是“使用字典”。

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

解决方案 2：

据我所知， stdlib 中没有这种东西，但快速浏览一下 pypi 就会发现一些替代方案：

• 红黑树

• 皮亚夫尔

• 布利斯特

解决方案 3：

在一些情况下，我发现heapq 包（在标准库中）很有用，特别是当您希望在任何给定时间以 O(1) 的时间访问集合中的最小元素时。

对我来说，我一直在跟踪一组计时器，并且通常只是想检查最小的时间（首先执行的时间）是否已准备好。

解决方案 4：

另请查看Sorted Containers项目。

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

解决方案 5：

有一个名为“bintrees”的新包，它支持 ubalanced、AVL 和 RB 树。您可以在这里找到它。

解决方案 6：

没有，但是有适用于 Python 的 AVL 树对象（非常老！）和 SourceForge 上的（已关闭的）项目 -适用于 Python 的 avl-trees。

解决方案 7：

我编写了 Java TreeMap/TreeSet 的 Python 版本，其底层数据结构是平衡二叉树（准确地说是红黑树）。

源代码和文档可在此 repo中访问

你可以使用 安装pip install pytreemap。已针对 Python >=3.5 进行测试