40. Вставка элемента в 2-3 дерево.
Начинается процесс так же как и процесс поиска, если поиск показывает, что элемент уже есть, то работа прекращается, иначе должны добавить.
Пусть в процессе поиска мы добрались до узла node, который предшествует листьям, если node имеет 2-х сыновей, то x делаем 3-м сыном, при этом новый лист располагается, так, чтобы все сыновья располагались слева на право, в порядке возрастания ключа.
Например при вставки элемента 18 в дерево 4.12 получим:
Рис. 4.13
В последнем промежутке ключь нужно менять.
Рассмотрим случай, когда x оказывается 4-м сыном листом некоторого промежуточного узла node. Пусть например в дерево на рисунке 4.13 x = 10. В этом случае на этапе поиска мы окажемся во 2-м узле 2-го уровня, у которого уже есть 3 сына, разбиваем его, один как node, а другой mode`. Два наименьших листа сыновья node, т.к node был разбит на 2, у его родителя p может оказаться 4 сына, тогда мы его тоже разбиваем. Если p-корень, то мы разобьем на 2 узла и образуем новый корень.
Рассмотрим пример вставки элемента 10 на рис. 4.13:
Рис. 4.14
*здесь сохраняем старые данные, т.к дерево придется перестроить
Корень имеет 4-х сыновей, поэтому разбиваем на 2 узла и строим новый корень.
Рис. 4.15
Пересчитаем промежуточные данные, если до поступления в хранилище в нем был 1-н элемент, то нужно сформировать дерево с корнем и 2-мя листьями. Все элементы на уровне листьев будут располагаться в порядке возрастания.
41. Удаление элемента из 2-3 дерева
В начале ищем элемент x в дереве и после нахождения удаляем лист. Если удаляемый лист имеет 1-го брата, то получим узел node на предпоследнем уровне с 1-м сыном, что не допустимо. Если node – корень, то сын становится корнем. Пусть node – не корень. Родители node – p. Если этот родитель имеет еще сына расположенного слева и пусть этот сын имеет 3-х сыновей, тогда старший по ключу становится сыном node.
Родитель p имеет еще сына справа от node имеющего 3-х сыновей, тогда младший по значению ключа становится сыном node.
Если эти варианты не реализуются, т.е другие сыновья имеют только 2х сыновей, то сын node становится сыном одного из братьев, а node удаляется.
Рассмотрим случайное удаление элемента 10 из рис. 4.15, получим:
Рис. 4.16
Обратим внимание, что в этом дереве содержаться также элементы, что и на рис. 4.13, но структуры разные. Причем иллюстрируя неоднозначность структуры при фиксированном наборе.
Пусть теперь необходимо удалить элемент 7 из дерева, после его удаления его родитель будет иметь 1-го сына – элемент 8 => этого сына нужно присоединить к 1-му из братьев родителя, а самого родителя удалить:
Рис. 4.17
В результате появится промежуточный узел с 1-м сыном, что не допустимо в 2-3 дереве. Поэтому данный узел удаляем, а единственного сына делаем сыном узла расположенным справа. Однако этот последний узел становится единственным сыном своего родителя, причем его родитель – корень. Поэтому удаляем корень и получаем дерево такой структуры:
Рис. 4.18
42. Остовные деревья минимальной стоимости (одмс) – основные понятия. Основное свойство одмс (с доказательством).
Пусть задан неориентированный граф G (V, Х). Вещественно заданную функцию c(x), которая задана на множестве ребер Х будем называть стоимостью ребер. Остовным графом G называется свободное дерево, т.е дерево без корня, содержащее все вершины графа G и только эти вершины, и множество ребер которого является подмножеством множества X ребер графа G. Стоимость остовного дерева определяется как сумма стоимостей его ребер. Существенный интерес представляют остовные деревья минимальной стоимости (ОДМС).
На рис. 5.1 показан граф и его ОДМС.
Рис. 5.1
Одной из практических задач для которой могут быть полезны ОДМС является задача минимализации коммуникационной сети. В этой задачи вершиной обозначаются города, а линиями – коммуникационные сети. Требуется построить коммуникационную сеть, связывающую 2 города и имеющую минимальную стоимость.
Обозначим через U произвольное подмножество множества V вершин графов. Пусть {u, v} – это ребро наименьшей стоимости серди ребер у которых 1-я и 2-я вершины берутся из u € U, v € V/U, тогда существует ОДМС графа G содержащим ребро {u, v}.
Доказательство (метод от противного):
Предположим, что существует остовное дерево минимальной стоимости T=(V, X`) и такое ребро {u, v} наименьшей стоимости среди ребер у которых u € U, v € V/U и при этом {u, v} не принадлежит X` и не входит в состав другого ОДМС.
Любое дерево обладает следующими свойствами:
Дерево с n вершинами имеет (n-1) ребер
Если в дерево добавить новое ребро не увеличивая число вершин, то в графе появится цикл
Если учесть 2-е из этих свойств, то добавление в T ребра {u, v} приведет к образованию цикла, этот цикл будет содержать ребро {u, v} и еще какое-то ребро {u`, v`}, при этом u` € U, v` € V/U. Удалим ребро {u, v} => цикл будет разорван => образуем новое остовное дерево, стоимость которого будет не больше стоимости дерева T, т.к стоимость {u, v} не может быть больше {u`, v`}. Таким образом мы приходим к противоречию со сделанным предположением:
Либо ребро {u, v} принадлежит X` и T – ОДМС
Либо стоимость ребра {u, v} = стоимости ребра {u`, v`}, но тогда существует другое ОДМС T*, которому принадлежит ребро {u, v}
Либо T – не ОДМС, тогда все предположение не верно