Как работает операция слияния декартовых деревьев?

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

Алгоритм работы Merge: dspace.tltsu.ru

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

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

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

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

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