# Alternative to binary search trees: A sorted array with empty spaces

There are many data structures that have O(log(n)) insert, delete and find operations: Self balancing binary search trees, skip lists and others. My question is: Why doesn't the following simple thing work?

Just hold an array whose values are sorted, with a certain percentage of empty cells distributed in a randomish way over the length of the array. For example, $$A = [1, -, -, 2, 3, -, 5, -, 7]$$

• Find is the usual binary search, where if you hit an empty cell you go right until you find a value.
• To delete, you find the value you want to delete and then delete it.
• To insert, you find the place where your new element is supposed to go using binary search, and then insert it, moving elements to the right if an empty space needs to be created.

I haven't done the analysis, but it seems like this should provide O(log(n)) average case runtime for the different operations, just like a binary search tree. Is there a name for this thing? Do people use it?

• I think this is basically en.wikipedia.org/wiki/Library_sort May 29, 2022 at 8:56
• Thank you! Yes, that seems to be it. I'll go read the paper. May 29, 2022 at 9:13
• Note the comment “ If used without this shuffling, it could easily degenerate into quadratic behaviour.” This seems to suggest that their methods (as stated) don’t (directly) generalize to a data structure (since it requires to see the whole input in advance to shuffle it) May 30, 2022 at 5:33