Sorting a data structure with O (log (n)) insertion and O (1) output
I am coding in Java and I need a sorted integer data structure that has a maximum insertion time of O (log (n)) and O (1) by index. Is there a built-in data structure that can do this, or if not, how do I program myself?
I know that Set can do the first task, but for the look i element, I will need to iterate over all elements up to i.
source to share
Possible solutions are trees that keep track of the number of children, which Wikipedia calls "order statistics trees". However, the search performance will be tied to the tree height, which is O (log n).
Trees that accelerate quickly, such as B-trees, can significantly reduce index searches, although it will always remain O (log n).
Unfortunately, there is no such tree in the Java collection structure. However a few days of work and testing should provide a sane implementation :)
source to share