Я предполагаю, что деревья сплайнов, которые вы хотите объединить, содержат n объектов каждый.(т.е. всего у нас есть 2n объектов).Тогда я думаю, что невозможно объединить их с амортизированной стоимостью log(n), , если вы не навязываете некоторые дополнительные предположения .Если у вас нет никакой информации об объектах, содержащихся в деревьях, вам придется посмотреть хотя бы на каждый элемент одного из двух деревьев, что обойдется вам в O(n).
. Однако, если вы можетесделать определенные предположения об объектах, вы можете сделать это в O(log(n)).Вы можете извлечь определенные поддеревья, чтобы вы могли вставить все поддерево в другое дерево сплайнов.Тем не менее, я не знаю точного алгоритма, как добиться O(log(n)).Например, если мы знаем, что самый большой объект в Tree1 меньше, чем самый маленький объект в Tree2, то мы можем просто развернуть самый левый узел Tree2, а затем повесить корень Tree1 подкорень Tree2.