4.12. СЦЕПЛЯЕМЫЕ ОЧЕРЕДИ

В разд. 4.10 было показано, как на листьями выполнить каждую из операций ВСТАВИТЬ, УДАЛИТЬ, MIN и ПРИНАДЛЕЖАТЬ за время если пользоваться значениями Сейчас покажем, как за время выполнить каждую из операций СЦЕПИТЬ и РАСЦЕПИТЬ. Снова будем предполагать, что элементы расположены на листьях 2-3-дерева в порядке возрастания слева направо и для каждого узла вычисляются значения

Рис. 4.33. Расцепление 2-3-дерева.

Операции на вход подаются такие две последовательности что каждый элемент из меньше каждого элемента из на выход она выдает конкатенацию этих последовательностей, т. е. Если представлены соответственно то мы хотим соединить в одно дерево листьями которого являются листья дерева в их первоначальном порядке и следующие за ними листья дерева в их первоначальном порядке. Это можно осуществить, вызвав процедуру приведенную на рис. 4.32.

Наконец, рассмотрим операцию Напомним, что операция разбивает два множества Для ее реализации определим процедуру которая расцепляет на два такие что метки всех листьев в не больше а, а метки всех листьев в больше а.

Метод можно неформально описать следующим образом. Дано содержащее элемент а. Идем по пути из корня в лист с меткой а. Этот путь разбивает наше дерево на поддеревья, корнями которых служат не сами узлы, лежащие на нем, а их сыновья. Это иллюстрирует рис. 4.33, где слева от пути находятся деревья и тривиальное дерево, состоящее из одного узла а справа — деревья

Деревья слева от рассматриваемого пути и дерево, состоящее из одного узла а, соединяются с помощью только что описанного алгоритма конкатенации деревьев. Аналогично соединяются деревья, расположенные справа от пути. Необходимые детали даны в процедуре ДЕЛЕНИЕ (рис. 4.34).

Рис. 4.34. (см. скан) Процедура для расцепления 2-3-дерева.

Теорема 4.7. Процедура разбивает по листу а так, что все листья слева от а и сам лист а оказываются в одном а все листья справа от а — в другом. Эта процедура занимает время Порядок листьев сохраняется.

Доказательство. Из свойств процедуры ИМПЛАНТАЦИЯ вытекает, что деревья объединены правильно. Результат о времени работы получается из следующих соображений. Вначале число деревьев любой данной высоты не более 2, только деревьев высоты может быть 3. Когда два дерева соединяются, получается дерево, высота которого не более чем на единицу больше наибольшей из высот двух исходных деревьев. В случае когда получается дерево высоты, на единицу большей высоты любого из исходных деревьев, его корень имеет степень 2. Таким образом, если соединяются три дерева высоты то в результате получается дерево

высоты не более Следовательно, на каждой стадии процесса число деревьев одинаковой высоты не превосходит 3.

Время, требуемое для соединения двух деревьев разной высоты, пропорционально разности их высот, а одинаковой высоты — постоянно. Поэтому объединение всех деревьев происходит за время, пропорциональное сумме числа деревьев и наибольшей из разностей высот любых двух деревьев. Таким образом, всего тратится времени порядка высоты исходного дерева.

Заметим, что с помощью сцепляемой очереди последовательность можно вставить между парой элементов последовательности за время Если нужно вставить между элементами то можно применить операцию и разбить по элементу на две последовательности Затем применить операцию результатом которой будет последовательность наконец, операцию дающую нужную последовательность.