Python中内置的二进制搜索树？[关闭]

Python中内置的二进制搜索树？[关闭]

有没有特殊的原因，据我所知-
我猜的原因是，如此多的应用的高度调整

dict

和

set

实现（这是哈希表）工作做好。在大多数情况下，它们足够好。在某些情况下，您确实需要平衡的二进制搜索树的性能特征（例如，基于键而不是加序的有序遍历），但这些条件已经远远超出了人们通常会抓住第三方软件包的范围在这种情况下。

我在PyPI上使用bintrees包有很好的经验。这在纯Python中以及作为用Cython编写的扩展都具有不平衡的AVL和红黑二进制树的实现。

我认为其余原因本质上是历史事故。如果编写二叉树的人游说将其包含在stdlib中，并且愿意忍受维护和发布所施加的约束，那么它可能会加入进来。（尽管Cython依赖会导致问题，我猜）

算法复杂度：

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