Рис. 4.33. Расцепление 2-3-дерева.
Операции
на вход подаются такие две последовательности
что каждый элемент из
меньше каждого элемента из
на выход она выдает конкатенацию этих последовательностей, т. е.
Если
представлены соответственно
то мы хотим соединить
в одно дерево
листьями которого являются листья дерева
в их первоначальном порядке и следующие за ними листья дерева
в их первоначальном порядке. Это можно осуществить, вызвав процедуру
приведенную на рис. 4.32.
Наконец, рассмотрим операцию
Напомним, что операция
разбивает
два множества
Для ее реализации определим процедуру
которая расцепляет
на два такие
что метки всех листьев в
не больше а, а метки всех листьев в
больше а.
Метод можно неформально описать следующим образом. Дано
содержащее элемент а. Идем по пути из корня в лист с меткой а. Этот путь разбивает наше дерево на поддеревья, корнями которых служат не сами узлы, лежащие на нем, а их сыновья. Это иллюстрирует рис. 4.33, где слева от пути находятся деревья
и тривиальное дерево, состоящее из одного узла
а справа — деревья
Деревья слева от рассматриваемого пути и дерево, состоящее из одного узла а, соединяются с помощью только что описанного алгоритма конкатенации деревьев. Аналогично соединяются деревья, расположенные справа от пути. Необходимые детали даны в процедуре ДЕЛЕНИЕ (рис. 4.34).