So long as (fast/optimal) real-time access to new data is not a concern, you can introduce compaction to solve both problems.
> (fast/optimal) real-time access to new data
https://en.wikipedia.org/wiki/Optimal_binary_search_tree#Dyn...
> (fast/optimal) real-time access to new data
https://en.wikipedia.org/wiki/Optimal_binary_search_tree#Dyn...