How Python3 sorted list operations compare to a balanced BST?

user_666130 0
Viewed 591

I am using a sorted list to binary search values using built-in bisect module, which gives lookup time of O(log n). The documentation of bisect points out that inserting with insort() gives a total time of O(n) by dominated insert time in a list. It also has a deletion time of O(n).

Is there a way to use a list and have O(log n) insert, delete and lookup? Can I do that with a balanced binary search tree (BST) like a Red-Black Tree? Which Python3 module has a data structure with those properties?

NOTE: I've seen there is a package bintrees on PyPI that has RBTree and AVLTree but it is abandoned and their documentation points to using sortedcontainers lib. sortedcontainers as far as I've seen doesn't have these trees for usage (they are writen in C and are base for SortedList, SortedDict and SortedSet).

binary-search-tree data-structures time-complexity python-3.x list
1 Answers

Can I do that with a balanced binary search tree (BST) like a Red-Black Tree?

Yes.

Which Python3 module has a data structure with those properties?

The Python built-in data structure set has O(log n) insert, delete and lookup. More precisely, a tighter bound for all these operations is (amortised) O(1).

However, these sets are not sorted. These are provided by sortedcontainers.

sortedcontainers as far as I've seen doesn't have these trees for usage (they are writen in C and are base for SortedList, SortedDict and SortedSet).

I'm not exactly sure about the implementation details of the library, but SortedSet (or more generally SortedDict) are what you want (O(log n) insert, O(log n) delete, O(1) lookup) if you require sorted sets. Otherwise, use the built-in set.

user_75068610
Related