Удаление нескольких элементов из балансирующего двоичного дерева сразу

Question

Я использую красно-черное двоичное дерево со связанными листьями в проекте (Java TreeMap), чтобы быстро находить и перебирать элементы. Проблема в том, что я могу легко получить 35000 предметов или около того на дереве, и несколько раз мне нужно удалить «все элементы выше X», которые могут быть почти всем деревом (например, 30000 предметов сразу, потому что все они больше чем X), и это занимает слишком много времени, чтобы удалить их и каждый раз перебалансировать дерево.

Есть ли какой-нибудь алгоритм, который может помочь мне здесь (чтобы я мог реализовать свою собственную реализацию дерева)?

Answer 1

Вы ищете сплит работа на красном/черном дереве, которое берет красное/черное дерево и некоторое значение k и разбивает его на два красно-чёрных дерева, один со всеми ключами, большими или равными до k и один со всеми ключами, меньшими k. Это может быть реализовано в O (log n), если вы увеличиваете структуру для хранения дополнительной информации. В вашем случае, поскольку вы используете Java, вы можете просто разделить дерево и отбросить корень дерева, которое вам неинтересно, чтобы сборщик мусора мог его обработать.

Подробнее о том, как осуществить это, приведены в this paper, начиная со страницы 9. Она реализована в терминах сцеплять (или присоединиться к) операциям, которые сочетают в себе два дерева, но я думаю, что экспозиция довольно ясно.

Надеюсь, это поможет!