Python 的标准库中是否有用于平衡二叉树的模块? [英] Is there a module for balanced binary tree in Python's standard library?

问题描述

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

Is there a module for an AVL tree or a red–black tree or some other type of a balanced binary tree in the standard library of Python?

推荐答案

不，stdlib 中没有平衡二叉树.但是，根据您的评论，您似乎还有其他选择:

No, there is not a balanced binary tree in the stdlib. However, from your comments, it sounds like you may have some other options:

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

• You say that you want a BST instead of a list for O(log n) searches. If searching is all you need and your data are already sorted, the bisect module provides a binary search algorithm for lists.
• Mike DeSimone recommended sets and dicts and you explained why lists are too algorithmically slow. Sets and dicts are implemented as hash tables, which have O(1) lookup. The solution to most problems in Python really is "use a dict".

如果这两种解决方案都不适合您，则您必须使用第三方模块或实现自己的模块.

If neither solution works well for you, you'll have to go to a third party module or implement your own.

这篇关于Python 的标准库中是否有用于平衡二叉树的模块?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！