1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 36
Текст из файла (страница 36)
Аналогично соединяются деревья, расположенные справа от пути. Необходимые детали даны в процедуре ДЕЛЕНИЕ (рис. 4.34). 1гр ГЛ, 4. СТРУКТУРЪ| ДАННЫХ ДЛЯ ЗАДАЧ С МНОЖЕСТВАМИ ргосеппге ДЕЛЕНИЕ(а, Т): Ьей1п на пути из узла КОРЕНЬ(Т1 к листу с меткой а удалить все узлы, кроме этого листа: сопнпеп1 В данный момент дерево Т оказалось разделенным на два леса — левый, состоящий из всех деревьев, листья которых лежат слева от а, и из узла с меткой а, и правый, состоящий из всех деревьев, листья которых лежат справа от а; ТУЫ!е в левом лесу более одного дерева йо Ьея! п пусть Т' и Т" — два самых правых дерева в левом лесу; ИМПЛАНТАЦИЯ(Т', Т') ') епй; |УЫ!е в правом лесу более одного дерева йо Ьея)п пусть Т' и Т' — два самых левых дерева в правом лесу; ИМПЛАНТАЦИЯ(Т', Т ) епй епй ') Результат процедуры ИМПЛАНТАЦИЯ(Т', Т ) отнести к левому лесу.
Аналогично прн применения к деревьям на правого леса результат процедуры ИМПЛАНТАЦИЯ относится к правому лесу. Рнс. 4.34. Процедура для расцеплення 3-3-дерева. Теорема 4.7, Процедура ДЕЛЕНИЕ разбивает 2-3-дерево Т по листу а так, члю все листья слева от а и сам лист а оказываются в одном 2-3-дереве„а все листья справа от а — в другом. Эта процедура занимает время 0(ВЫСОТА(Т)). Порядок листьев сохраняется.
Д о к а з а т е л ь с т в о. Из свойств процедуры ИМПЛАНТАЦИЯ вытекает, что деревья объединены правильно. Результат о времени работы получается из следукнцих соображений. Вначале число деревьев любой данной высоты не более 2, только деревьев высоты О может быть 3. Когда два дерева соединяются, получается дерево, высота которого не более чем на единицу больше наибольшей из высот двух исходных деревьев. В случае когда получается дерево высоты, на единицу большей высоты любого из исходных деревьев, его корень имеет степень 2. Таким образом, если соединяются три дерева высоты Ь, то в результате получается дерево тва ь!3. РАзвивнив высоты не более Ь+1. Следовательно, на каждой стадии процесса число деревьев одинаковой высоты не превосходит 3.
Время, требуемое для соединения двух деревьев разной высоты, пропорционально разности их высот, а одинаковой высоты— постоянно. Поэтому объединение всех деревьев происходит за время, пропорциональное сумме числа деревьев и наибольшей из разностей высот любых двух деревьев. Таким образом, всего тратится времени порядка высоты исходного дерева. С) Заметим, что с помощью сцепляемой очереди последовательность 5, можно вставить между парой элементов последовательности 5, за время 0(МАХ (!оя!5,1, 1од!5,!)). Если 5,=Ь„Ь„... ..., Ь„, 5,=а„а„..., а и 5, нужно вставить между элементами а; и а;~„то можно применить операцию РАСЦЕПИТЬ(а!, 5,) и разбить 5, по элементу а, на две последовательности 5;=а„ ..., а! и 5 =а!.!„..., а„.
Затем применить операцию СЦЕПИТЬ(5;, 5,), результатом которой будет последовательность 5,=а„..., а!, Ь„..., Ь„, и, наконец, операцию СЦЕПИТЬ(5„5",), дающую нужную последовательность. 4Л3. Рл!ЗВИЕНИЕ Рассмотрим специальный тнп расцепления, называемый разбиением.
Задача разбиения множества возникает довольно часто, и решение, которое мы продемонстрируем здесь, поучительно само по себе. Пусть даны множество 5 и разбиение п множества 5 на непересекающиеся блоки („„..., Вр). Кроме того, дана функция ), отображающая 5 на 5. Наша задача состоит в том, чтобы найти такое грубейшее (с наименьшим числом блоков) разбиение и'=(Е„Е„..., Е ) множества 5, что 1) и' — подразбиение разбиения и (т. е.
каждое множество Е, является подмножеством некоторого блока Ву), 2) если а и Ь принадлежат Еь то г" (а) и )'(Ь) принадлежат Еэ для некоторого 1. Будем называть и' грубейшим разбиением множества 5, совместимым с и и Г. Очевидное решение. состоит в повторном утончении блоков исходного разбиения следующим способом. Пусть В! — какой- нибудь блок.
Рассмотрим )(а) для каждого а из Вь Разобьем В, так, чтобы два элемента а и Ь попадали в один блок тогда и только тогда, когда ~(а) и г(Ь) оба принадлежат некоторому блоку В;. Процесс повторяется до тех пор, пока уже нельзя будет проводить дальнейшие утончения. Этот метод дает алгоритм сложности 0(п'), поскольку каждое утончение занимает время 0(п), а всего может «и гл. е стггктггы длниых для зхдлч с множаствлми быть 0(п) утончений. Пример 4.13 показывает, что действительно может потребоваться квадратичное число шагов.
Пример 4.13. Пусть 5=(1, 2,..., и) и В,=(1, 2,..., и — 1), В,=(а) — исходное разбиение. Пусть 1 — такая функция на 5, что 1(!)=!+1 для 1(1<п и [(п)=п. При первой итерации В, разбиваем на (1, 2,..., а — 2) и (и — 1). Эта итерация занимает п — ! шагов, поскольку надо просмотреть каждый элемент в В,. При следующей итерации разбиваем (1, 2, ..., а — 2) на (1, 2, ... л — 3) н (а — 2).
Продолжая в том же духе, выполняем всего и — 2 итерации, причем 1-я итерация занимает и — ! шагов. Следовательно, всего требуется л-2 ~ч,' („.) 1~ — ~> с=~ шагов. Окончательным разбиением будет Е,=(1) для !(и-.п. П Недостаток этого метода состоит в том, что утончение блока может потребовать 0(п) шагов, даже если из него удаляется только один элемент. Сейчас мы опишем алгоритм разбиения, который для разделения блока на два подблока требует время, пропорциональное размеру меньшего подблока. Этот подход приводит к алгоритму сложности 0(а [сап). Для каждого блока В~5 положим )-'(В)=(Ь[Г(Ь) ~ В). Вместо того чтобы разбивать В~ по значениям 1(а) для аЕВь разобьем относительно В, те блоки Вь которые содержат хотя бы один элемент из 1 "(В,) и один элемент не из ~-'(В ).
Иными словами, каждый такой блок В, разбивается на множества (Ь[Ь Е В! и 1(Ь) Е В,) и (Ь [Ь Е В~ и )(Ь) ( В;). Как только проведено разбиение относительно блока В„больше уже не нужно проводить разбиения относительно него, пока он сам не будет расщеплен. Если вначале 1(Ь) Е В~ для каждого элемента Ь ЕВ~ и В, расщеплен на В; и В",, то можно разбить В; относительно В; или В; и получить при этом один и тот же результат, поскольку (Ь[ЬбВ~ и [(Ь)ЕВ;) совпадает с В; — (Ь[ЬЕВ, и 
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
