Hrm, you’re right. Worst case appears to…

Comment on “BList” by bramcohen

Hrm, you're right. Worst case appears to be log(n) ** 2, with the whitebox speedups only getting a constant factor improvement.

You could start putting value information inside the tree. It would result in weird results when the tree isn't sorted, but insort() doesn't make any particular guarantees on unsorted lists.

The use case of inserting and removing from a sorted list is certainly one worth optimizing for, since it involves a lot of inserts and deletes at random locations, and is relatively common.


Comments are closed.