Из какой коллекции можно быстро удалять элемент, но к ней применим бин. поиск?

Question

[BitNeBolt]

В общем, в моем решении задачи нужно искать элемент бин. поиском (по сути, upperBound от какого-то x) и удалять его, чтобы он не использовался в последующих поисках. Проблема в том, что сложность всегда перерастает в квадрат: при ArrayList удаление занимает O(n), при LinkedList - бин поиск O(nlogn) и так n раз.

Как ускорить ситуацию? Возможно, есть принципиально другой подход? В sortedSet нет метода для upperBound.

Answer 1

[Wataru]

TreeSet.

Там можно искать нужный вам элемент через floor или ceiling. Поиск и удаление, если создатели библиотеки в java хоть что-то слышали про алгоритмы и структуры данных, работают за логарифм.

Answer 2

[Alexandroppolus]

Написать своё сбалансированное дерево. Удаление и upperBound будут за логарифм