What benefit does a balanced search tree provide over a sorted key-value pair array?

Question

public class Entry{

int key;
String value;
}

If you have an array of Entry.

Entry[]

You can do a binary search on this array to find, Insert or remove an Entry all in O(Log(n)). I can also do a range search in O(log(n)).

And this is very simple.

What does a comparatively complicated data structure like a red-black balanced search tree, give me over a simple sorted key value array?

Answer 1

If data is immutable, the tree has no benefit.

The only benefit of the array is locality of reference, e.g. data is close together and CPU may cache it.

Because the array is sorted, search is O(log n)

If you add / remove items things changed.

For small number of elements, the array is better (faster) this is because of the locality of reference.

For larger number of items Red Black Tree (or another self balanced tree) will perform better, because the array will need to shift the elements.
e.g. insert and delete will take O(log n) + huge n/2 for the shift.