Python内置二进制搜索树？

Question

在Python 2.7或Python 3.x中是否存在任何自平衡二叉搜索树(RED-BLACK,AVL或其他)内置类型？

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

如果没有这样的内置插件,他们为什么会被忽略？是否有特殊原因,因为不包括此类工具？

Answer 1

据我所知,没有什么特别的原因 - 我猜测的原因是,对于如此多的应用程序,高度调整dict和set实现(哈希表)运行良好.在大多数情况下,它们都足够好.肯定存在需要平衡二叉搜索树的性能特征的情况(比如基于键而不是加法顺序的有序遍历),但这些远远超出了人们对抓住第三方包的乐趣.在这种情况下.

我在PyPI上使用bintrees包有很好的经验.它具有非平衡,AVL和红黑二进制树的实现,既有纯Python,也有用Cython编写的扩展.

我认为其余的原因基本上是历史事故.如果编写bintrees的人游说将其包含在stdlib中,并且愿意忍受对维护和释放施加的约束,那么它可能会进入.(虽然Cython依赖会导致问题,但我猜.)

算法复杂度:

对于散列表(如dicts或sets),插入和查找是O(1),而对于平衡树,这些是O(log(n)).按键的有序遍历是树中的O(n),但是为了对哈希表执行相同的操作,您需要首先对键进行排序,因此它是O(n*log(n)).当您选择使用哪种数据结构时,您需要考虑将要使用哪些操作,并选择在您的应用程序中最有意义的权衡.

Answer 2

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