Как объединить два двоичных дерева поиска, сохраняющих свойство BST?
Если мы решим взять каждый элемент из дерева и вставить его в другой, сложность этого метода будет O(n1 * log(n2))
, где n1
- количество узлов дерева (например, T1
), который мы разделили, а n2
- количество узлов другого дерева (скажем T2
). После этой операции только один BST имеет n1 + n2
узлы.
Мой вопрос: можем ли мы сделать лучше, чем O (n1 * log (n2))?