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?