Как Python3 сортирует список операций по сравнению с сбалансированным BST?

Question

Я использую отсортированный список для двоичного поиска значений, используя встроенный модуль bisect, который дает время поиска O (log n). Документация делит на две части, что вставка с insort() дает общее время O (n) с доминирующим временем вставки в список. У него также есть время удаления O (n).

Есть ли способ использовать список и иметь O (log n) для вставки, удаления и поиска? Могу ли я сделать это с помощью сбалансированного бинарного дерева поиска (BST), такого как красно-черное дерево? Какой модуль Python3 имеет структуру данных с этими свойствами?

ПРИМЕЧАНИЕ. Я видел, что существует пакет bintrees для PyPI, в котором есть RBTree и AVLTree, но он заброшен, и их документация указывает на использование sortedcontainers lib. Насколько я знаю, у sortedcontainers нет этих деревьев (они написаны на C и являются базовыми для SortedList, SortedDict и SortedSet).

Answer 1

Можно ли сделать это с помощью сбалансированного бинарного дерева поиска (BST), такого как красно-черное дерево?

Да.

Какой модуль Python3 имеетструктура данных с этими свойствами?

Встроенная структура данных Python set имеет O (log n) вставки, удаления и поиска. Точнее, более жестким пределом для всех этих операций является (амортизированный) O (1).

Однако эти наборы не сортируются. Они предоставляются sortedcontainers.

sortedcontainers, поскольку, насколько я видел, эти деревья не используются (они написаны на C и являются базовыми для SortedList, SortedDict и SortedSet).

Я не совсем уверен в деталях реализации библиотеки, но SortedSet (или, в более общем смысле, SortedDict) - это то, что вы хотите (O (log n) insert, O (log)n) удалить O (1) lookup), если вам нужны отсортированные наборы. В противном случае используйте встроенный set.