Python中的内置二叉搜索树？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17857496/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Built-in binary search tree in Python?
提问by Alexandru Chirila
Are there any self-balancing binary search tree(RED-BLACK, AVLor others) built-in types in Python 2.7 or Python 3.x?
Python 2.7 或 Python 3.x 中是否有任何自平衡二叉搜索树（RED-BLACK、AVL或其他）内置类型？
I am looking for something equivalent to Java's TreeMapor TreeSet.
我正在寻找相当于 Java 的TreeMap或TreeSet 的东西。
If there are no such built-ins, why have they been ommited? Is there a special reason, for not including such tools?
如果没有这样的内置函数，为什么要省略它们？不包括此类工具是否有特殊原因？
采纳答案by babbageclunk
There's no special reason, to my knowledge - I'd guess that the reason is that for so many applications the highly-tuned dictand setimplementations (which are hash tables) work well. They're good enough in most cases. There are definitely situations where you need the performance characteristics of balanced binary search trees (like ordered traversal based on key- rather than addition-order), but those are far enough off the beaten path that people are happy with grabbing a third-party package in that case.
据我所知，没有什么特别的原因——我猜想原因是对于如此多的应用程序，高度调整dict和set实现（哈希表）运行良好。在大多数情况下，它们已经足够好了。肯定在某些情况下您需要平衡二叉搜索树的性能特征（例如基于键而不是加法的有序遍历），但这些都远远超出人们对获取第三方包感到满意的人迹罕至的地方在这种情况下。
I've had a good experience using the bintreespackage on PyPI. This has implementations of unbalanced, AVL and red-black binary trees, in both pure Python and as extensions written in Cython.
我在 PyPI 上使用bintrees包有很好的经验。这在纯 Python 和用Cython编写的扩展中实现了不平衡、AVL 和红黑二叉树。
I think the rest of the reason is essentially historical accident. If the person who wrote bintrees lobbied for its inclusion in the stdlib, and was willing to put up with the constraints that imposes on maintenance and releases, it would probably go in. (Although the Cython dependency would cause a problem, I'd guess.)
我认为其余的原因本质上是历史偶然。如果编写 bintrees 的人游说将其包含在 stdlib 中，并且愿意忍受对维护和发布施加的约束，那么它可能会加入。（尽管 Cython 依赖会导致问题，我猜.)
Algorithmic complexity:
算法复杂度：
For hash tables (like dicts or sets), insertion and lookup are O(1), while for a balanced tree these are O(log(n)). In-order traversal of keys is O(n) in a tree, but to do the same thing with a hash table you need to sort the keys first, so it's O(n*log(n)). When you're picking which kind of data structure to use, you need to think about which operations you're going to be using, and pick the tradeoff that makes the most sense in your application.
对于哈希表（如字典或集合），插入和查找是 O(1)，而对于平衡树，这些是 O(log(n))。键的有序遍历在树中是 O(n)，但是要对哈希表执行相同的操作，您需要先对键进行排序，因此它是 O(n*log(n))。当您选择使用哪种数据结构时，您需要考虑将使用哪些操作，并选择在您的应用程序中最有意义的权衡。
回答by hivert
You won't find any trees in the standard library. Python heavily uses dictionary that is hash table for its internal (object, classes and modules are all based on dicts). Therefore dicts has been greatly optimized. This make the needs for search trees much smaller. Also to be efficient such trees would have been implemented in an extension type.
您不会在标准库中找到任何树。Python 大量使用字典作为其内部的哈希表（对象、类和模块都基于字典）。因此 dicts 得到了极大的优化。这使得对搜索树的需求小得多。为了提高效率，此类树将在扩展类型中实现。
