90

Python 的标准库中是否有用于AVL 树或红黑树或其他类型的平衡二叉树的模块？

4

7 回答 7

54

不，stdlib 中没有平衡二叉树。但是，根据您的评论，听起来您可能还有其他选择：

  • 你说你想要一个 BST 而不是一个O(log n)搜索列表。如果您只需要搜索并且您的数据已经排序，则该bisect模块为列表提供二进制搜索算法。
  • Mike DeSimone 推荐了 set 和 dicts，你解释了为什么列表在算法上太慢了。集合和字典实现为哈希表，具有 O(1) 查找。Python 中大多数问题的解决方案实际上是“使用字典”。

如果这两种解决方案都不适合您，您将不得不使用第三方模块或实施您自己的模块。

于 2010-02-19T17:26:14.353 回答
15

据我所知，stdlib 中没有这种类型的东西，但是快速查看 pypi 会带来一些替代方案：

于 2010-02-19T17:10:56.690 回答
11

在某些情况下，我发现heapq 包（在标准库中）很有用，特别是如果在任何给定时间您希望 O(1) 访问集合中最小元素的时间。

对我来说，我一直在跟踪一组计时器，并且通常只是对检查最小的时间（首先执行的时间）是否已经准备就绪感兴趣。

于 2010-02-22T06:13:18.123 回答
8

还可以查看Sorted Containers项目。

这是关于它的 PyCon 讨论：https ://www.youtube.com/watch?v=7z2Ki44Vs4E

于 2018-02-25T19:41:03.260 回答
6

有一个名为“bintrees”的新软件包支持 ubalanced、AVL 和 RB 树。你可以在这里找到它。

于 2011-05-21T11:56:56.193 回答
3

不，但是有用于 Python 的 AVL 树对象（非常旧！）和 SourceForge 上的（关闭的）项目 -用于 Python 的 avl-trees。

于 2010-02-19T17:13:45.763 回答
0

我写了一个 Python 版本的 Java TreeMap/TreeSet，其底层数据结构是平衡的二叉树（准确地说是红黑树）。

可以在这个 repo中访问源代码和文档

您可以使用pip install pytreemap. 测试 Python >=3.5

于 2020-06-24T19:32:26.937 回答