for a balanced BST, it has an additional property of max difference of any two leaves' depth are no greater than 1, in additiona to BST property itself, thus achieving range query in O(logn) and is mutable (allowing element add, del in O(logn) ).
from sortedcontainers.SortedList docs, it only says
Sorted list is a sorted mutable sequence.
In the add function, it first find a sublist, then does bisect.insort on that sublist, which is claimed to be O(logn) in approx. Correct me if wrong, it seems to me SortedList is more of an array of sorted sublists. It splits list into n/(logn) sublists, each of size logn. locating one sublist takes O(logn - loglogn). and insort on sublist takes O(logn), in total approx O(logn) as claimed.
could someone more knowledgable on this help explain how SortedList really works? and is it really a balanced BST or not? thanks.