有没有 自平衡二叉搜索树 （红黑， AVL 或其他）Python 2.7或Python 3.x中的内置类型？
我正在寻找与Java相当的东西 TreeMap的 要么 TreeSet中。
如果没有这样的内置插件，为什么他们被忽略了？是否有特殊原因，因为不包括这些工具？
有没有 自平衡二叉搜索树 （红黑， AVL 或其他）Python 2.7或Python 3.x中的内置类型？
我正在寻找与Java相当的东西 TreeMap的 要么 TreeSet中。
如果没有这样的内置插件，为什么他们被忽略了？是否有特殊原因，因为不包括这些工具？
据我所知，没有什么特别的原因 - 我猜测的原因是，对于如此众多的应用程序而言，经过高度调整 dict 和 set 实现（哈希表）运行良好。在大多数情况下，它们都足够好。肯定存在需要平衡二叉搜索树的性能特征的情况（比如基于键而不是加法顺序的有序遍历），但这些远远超出人们对抓住第三方包的乐趣在这种情况下。
我有很好的使用经验 bintrees PyPI上的包。这包括非平衡，AVL和红黑二进制树的实现，包括纯Python和写入的扩展 用Cython。
我认为其余的原因基本上是历史事故。如果编写bintrees的人游说将其包含在stdlib中，并愿意忍受对维护和释放施加的约束，那么它可能会进入。（虽然Cython依赖会导致问题，但我猜。）
算法复杂度：
对于散列表（如dicts或sets），插入和查找是O（1），而对于平衡树，这些是O（log（n））。按键的有序遍历是树中的O（n），但是为了对哈希表执行相同的操作，您需要先对键进行排序，因此它是O（n * log（n））。当您选择使用哪种数据结构时，您需要考虑将要使用哪些操作，并选择在您的应用程序中最有意义的权衡。
您将无法在标准库中找到任何树。 Python大量使用字典作为其内部的哈希表（对象，类和模块都基于dicts）。因此，dicts已经大大优化。这使搜索树的需求更小。为了有效，这种树也将以扩展类型实现。