Операция слияния (Merge) позволяет слить два декартовых дерева в одно. 3 При этом все ключи в левом дереве должны быть меньше, чем ключи в правом. 3 В результате получается дерево, в котором есть все ключи из первого и второго деревьев. 3

Алгоритм работы Merge: 1

1. Если приоритет в корне левого дерева больше приоритета в корне правого: 1

• Корень левого дерева становится корнем итогового дерева. 1
• Его левое поддерево остаётся на месте. 1
• Правое поддерево левого дерева и правое дерево нужно слить в одно дерево и подвесить справа от корня. 1

1. Если приоритет в корне правого дерева больше приоритета в корне левого: 1

• Отделяют левое поддерево правого дерева от его корня. 1
• Выполняют Merge для этого поддерева и левого дерева. 1
• Корень получившегося в результате дерева делают левым потомком корня правого дерева. 1

Операция Merge может работать не с любыми парами деревьев, а только с теми, у которых все ключи одного дерева не превышают ключей второго. 2