Python中内置的二进制搜索树? [英] Built-in binary search tree in Python?

问题描述

Python 2.7或更高版本中是否有任何自平衡二进制搜索树( RED-BLACK ， AVL 或其他)内置类型Python 3.x?

Are there any self-balancing binary search tree (RED-BLACK, AVL or others) built-in types in Python 2.7 or Python 3.x?

我正在寻找与Java TreeMap 或 TreeSet .

I am looking for something equivalent to Java's TreeMap or TreeSet.

如果没有这样的内置程序，为什么要忽略它们?是否有不包含此类工具的特殊原因?

If there are no such built-ins, why have they been ommited? Is there a special reason, for not including such tools?

推荐答案

据我所知，没有特殊原因-我猜原因是对于许多应用程序来说，高度调整的dict和set实现(哈希表)效果很好.在大多数情况下，它们足够好.在某些情况下，您确实需要平衡的二进制搜索树的性能特征(例如，基于键而不是加法的有序遍历)，但是这些条件远远超出了人们通常会满意地抓住第三方程序包的路径在这种情况下.

There's no special reason, to my knowledge - I'd guess that the reason is that for so many applications the highly-tuned dict and set implementations (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.

我在PyPI上使用 bintrees 包方面有很好的经验.在纯Python中以及以 Cython 编写的扩展中，都实现了不平衡的AVL树和红黑二叉树的实现.

I've had a good experience using the bintrees package on PyPI. This has implementations of unbalanced, AVL and red-black binary trees, in both pure Python and as extensions written in Cython.

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

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.)

算法复杂度:

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

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.

这篇关于Python中内置的二进制搜索树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！