Есть ли способ перебрать TreeSet / TreeMap в O (N), при этом удаляя другую запись, отличную от той, на которую в данный момент указывает итератор?
Вот простой пример использования TreeSet,Набор содержит натуральные числа, и я проверяю, возможно ли создать N / 2 пары, например, каждая пара содержит [x, 2 * x].Я перебираю карту по нижнему ключу, проверяю, найдем ли мы двойное, и удаляю его при обнаружении. Для ясности, этот пример просто для иллюстрации, мне не нужно находить решение для самого примера, но нужно знать, могу ли я удалить его во время итерации.
public boolean checkTree(TreeSet<Integer> tree){
for (Integer i: tree) {
int twice = i*2;
if(!tree.contains(twice)) return false;
else tree.remove(twice);
}
return true;
}
Конечно, если я это сделаю, я получу ConcurrentModificationException , потому что я удаляю элемент без использования iterator.remove () .Но я не могу использовать этот метод, потому что я хотел бы удалить другой элемент.
Вот один обходной путь, о котором я могу подумать:
public boolean checkTree(TreeSet<Integer> tree){
while (tree.size() > 0) {
int twice = tree.pollFirst()*2;
if(!tree.contains(twice)) return false;
else tree.remove(twice);
}
return true;
}
Но он будет выполняться медленнее, потому что вызовN раз pollFirst () - это O (N log N) вместо O (N) treeIterator.Общая сложность действительно останется прежней, потому что includes () и remove () вызовы.
Есть ли способ удалить, продолжая итерацию по деревуиспользуя обход inorder?В классе TreeMap есть метод successor () , но он не является общедоступным.Этот вопрос действительно может относиться ко всем NavigableSet / NavigableMap.