Как объединить два 2-3 дерева?

Question

[neji ne]

Ситуация такова: нужен алгоритм объединения двух 2-3 деревьев, если диапазоны их ключей пересекаются и возможна ли вставка одного дерева в другое не по одному узлу?

Answer 1

[Сергей Тихонов]

В голову приходит MergeSort, в котором два упорядоченных "полу-массива" за линейное время объединяются в один. Можно попробовать тот же фокус с обходом упорядоченного дерева, тогда вставка всё равно будет по одному элементу, но не от корня, а от листовых вершин.