Стандартная библиотека Python - есть ли модуль для сбалансированного бинарного дерева?

Question

Есть ли в стандартной библиотеке Python модуль для AVL, Red-Black или какого-либо другого типа сбалансированного бинарного дерева? Я пытался найти один, но безуспешно (я относительно новичок в Python).

Answer 1

Нет, в stdlib нет сбалансированного бинарного дерева.Тем не менее, из ваших комментариев кажется, что у вас могут быть другие варианты:

• Вы говорите, что хотите BST вместо списка для O(log n) поисков.Если поиск - это все, что вам нужно, и ваши данные уже отсортированы, модуль bisect предоставляет бинарный алгоритм поиска по спискам.
• Майк ДеСимоне рекомендовал наборы и дикты, и вы объяснили, почему списки слишком алгоритмически медленны.Наборы и дикты реализованы в виде хеш-таблиц с поиском O (1).Решением большинства проблем в Python на самом деле является «использовать диктовку».

Если ни одно из решений не подойдет вам, вам придется перейти на сторонний модуль или реализовать свой собственный.

Answer 2

нет ничего подобного в stdlib, , насколько я вижу , но быстрый взгляд на pypi вызывает несколько альтернатив :

• rbtree
• pyavl
• Blist

Answer 3

Было несколько случаев, когда я находил пакет heapq (в стандартной библиотеке) полезным, особенно если в любой момент времени вы хотите, чтобы O (1) время доступа к наименьшему элементу в вашей коллекции.

Что касается меня, я отслеживал коллекцию таймеров и обычно просто интересовался проверкой того, готово ли наименьшее время (то, которое должно быть выполнено первым) к тому моменту.

Answer 4

Существует новый пакет под названием "bintrees", который поддерживает сбалансированные деревья, AVL и RB. Вы можете найти его здесь .

Answer 5

Проверьте также проект Sorted Containers .

Вот что говорит PyCon об этом: https://www.youtube.com/watch?v=7z2Ki44Vs4E

Answer 6

Нет, но есть AVL Tree Objects для Python (очень старый!) И (закрытый) проект на SourceForge - avl-деревья для Python .