Python中内置的二进制搜索树?

2024-03-28 12:27:56 发布

您现在位置:Python中文网/ 问答频道 /正文

Python 2.7或Python 3.x中是否有内置类型的自平衡二叉搜索树(RED-BLACKAVL或其他类型)?

我正在寻找与Java的TreeMapTreeSet等价的东西。

如果没有这样的内置组件,为什么要对它们进行修改?不包括这些工具有什么特别的原因吗?


Tags: 工具类型组件原因redjava内置black
2条回答

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

据我所知,没有什么特别的原因-我想原因是对于许多应用程序来说,经过高度优化的dictset实现(它们是哈希表)工作得很好。它们在大多数情况下都足够好。在某些情况下,您肯定需要平衡的二进制搜索树的性能特性(比如基于键的有序遍历,而不是加法顺序),但是这些特性已经远远偏离了常规路径,人们很乐意在这种情况下获取第三方包。

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

我认为其余的原因本质上是历史偶然。如果编写bintrees的人游说将其包含在stdlib中,并且愿意忍受对维护和发布的限制,那么它很可能会加入。(我想,尽管Cython依赖性会引起问题。)

算法复杂度:

对于哈希表(如dict或set),插入和查找是O(1),而对于平衡树,插入和查找是O(log(n))。在树中,键的遍历顺序是O(n),但是要对哈希表执行相同的操作,需要首先对键进行排序,所以是O(n*log(n))。在选择要使用哪种数据结构时,需要考虑要使用哪种操作,并选择在应用程序中最有意义的折衷方案。

相关问题 更多 >