Эффективная массовая модификация постоянных структур данных

Я понимаю, как обычно деревья используются для изменения постоянных структур данных (создания нового узла и замены всех его предков).

Но что, если у меня есть дерево из 10 000 узлов, и мне нужно изменить их тысячи? Я не хочу повторять и создавать тысячи новых корней, мне нужен только один новый корень, который получается в результате изменения всего сразу.

Например: Возьмем, к примеру, постоянное двоичное дерево. В случае с одним узлом обновления он выполняет поиск, пока не найдет узел, создает новый с модификациями и старыми дочерними элементами и создает новых предков до корня.

В случае массового обновления мы могли бы сделать: Вместо того, чтобы просто обновлять один узел, вы собираетесь обновить на нем 1000 узлов за один проход.

В корневом узле текущий список - это полный список. Затем вы разделяете этот список между теми, которые соответствуют левому узлу, и теми, которые соответствуют правому. Если ни один из детей не подходит, не спускайтесь к нему. Затем вы спускаетесь к левому узлу (при условии, что есть совпадения), разделяете его список поиска между его дочерними элементами и продолжаете. Когда у вас есть единственный узел и совпадение, вы обновляете его и возвращаетесь вверх, заменяя и обновляя предки и другие ветви по мере необходимости.

Это приведет только к одному новому корню, даже если он изменил любое количество узлов.