python - Python中的内置二叉搜索树？

Question

Python 2.7 或 Python 3.x 中是否有任何自平衡二叉搜索树（RED-BLACK、AVL或其他）内置类型？

我正在寻找与 Java 的TreeMap或TreeSet等效的东西。

如果没有这样的内置插件，为什么要省略它们？是否有特殊原因，不包括此类工具？

Answer 1

据我所知，没有什么特别的原因——我猜原因是对于如此多的应用程序来说，经过高度调整的dict实现set（它们是哈希表）运行良好。在大多数情况下，它们已经足够好了。在某些情况下，您肯定需要平衡二叉搜索树的性能特征（例如基于键而不是加法的有序遍历），但这些已经远远超出人们对获取第三方包感到满意的人迹罕至的地方在这种情况下。

我在 PyPI 上使用bintrees包有很好的体验。它在纯 Python 和用Cython编写的扩展中实现了不平衡、AVL 和红黑二叉树。

我认为其余的原因本质上是历史偶然。如果编写 bintrees 的人游说将其包含在 stdlib 中，并且愿意忍受对维护和发布施加的限制，它可能会进入。（尽管 Cython 依赖会导致问题，我猜.)

算法复杂度：

对于哈希表（如字典或集合），插入和查找是 O(1)，而对于平衡树，这些是 O(log(n))。在树中按顺序遍历键是 O(n)，但是要对哈希表做同样的事情，您需要先对键进行排序，所以它是 O(n*log(n))。当您选择使用哪种数据结构时，您需要考虑您将使用哪些操作，并选择在您的应用程序中最有意义的折衷方案。

Answer 2

您不会在标准库中找到任何树。Python 大量使用字典作为其内部的哈希表（对象、类和模块都基于字典）。因此dicts得到了极大的优化。这使得对搜索树的需求要小得多。为了提高效率，此类树将在扩展类型中实现。