73
правки
Изменения
→Merge
if (t1.key < t2.key)
t2.next = t1.son;
t1.soon son = t2;
else
t1.next = t2.son;
t2.soon son = t1;
</pre>
Проход по корневым спискам выполнится за <tex>O(logN)</tex>, объединение деревьев выполняется за <tex>O(1)</tex>. Тогда <tex>merge</tex> работает за <tex>O(logN)</tex>.
=== Insert ===
Разрешим при объединении двух деревьев присоединять еще одну вершину, дерево ранга 0. Тогда получится возможным существование еще двух типов деревьев:
