Реализация словаря 2 3 деревьями

Пример 3.9. Если в 2-3-дерево, изображенное на рис. 3.27,а, вставляется элемент 2, то получается 2-3-дерево, изображенное на рис. 3.27,б. 

Теперь предположим, что у f уже есть три листа l₁, l₂ и l₃. Сделаем l надлежащим сыном узла f. Теперь f имеет четырех сыновей. Чтобы сохранить 2-3-свойство, образуем новый узел g. Два левых сына оставим сыновьями узла f, а два правых переделаем в сыновей узла g. Затем сделаем g братом узла f, сделав его сыном отца узла f. Если отец узла f имел двух сыновей, то на этом мы остановимся. Если же трех, то надо рекурсивно повторять эту процедуру до тех пор, пока у всех узлов в дереве останется не более трех сыновей. Если у корня окажется четыре сына, образуем новый корень с двумя новыми сыновьями, каждый из которых будет иметь в качестве двух своих сыновей двух из четырех сыновей старого корня.

Пример 3.10. Если в 2-3-дерево на рис. 3.27,а, вставляется элемент 4, то новый лист с меткой 4 надо сделать самым левым сыном узла с. Поскольку у с уже есть три сына, строим новый узел с Затем делаем листья 4 и 5 сыновьями узла с, а листья 6 и 7 – сыновьями узла с’. Теперь делаем с’ сыном узла а. Но поскольку у а уже есть три сына, строим новый узел а‘. Делаем узлы b и с сыновьями старого узла а, а узлы с’ и d – сыновьями нового узла а‘. Наконец, образуем новый корень r и делаем а и а’ его сыновьями. Полученное дерево изображено на рис. 3.28. 

Алгоритм 3.4. Вставка нового элемента в 2-3-дерево

Вход. Непустое 2-3-дерево Т с корнем r и новый элемент аТ.

Выход. Преобразованное 2-3-дерево с новым листом, помеченным а.

Метод. По условию Т содержит хотя бы один элемент. Чтобы упростить описание алгоритма, опустим детали корректировки L и М.

1. Если Т состоит из единственного узла l с меткой b, образуем новый корень r‘. Образуем новый узел v с меткой а. Делаем l и v сыновьями корня r‘, причем l будет левым сыном, если b < а, и правым в противном случае.

2. Если Т содержит более одного узла, положим f = ПОИСК(а, r); процедура ПОИСК приведена на рис. 3.29. Образуем новый лист l с меткой а. Если у f два сына с метками b₁ и b₂,

procedure ПОИСК(а, r):

if любой сын узла г является листом then return r

пусть s_i будет i-м сыном, узла r;

if a  L[r] then return ПОИСК(a, s₁)

if у r два сына или a  M[r] then return ПОИСК(a, s₂)

else return ПОИСК(а, s₂)

procedure ДОБАВСЫНА (v):

образовать новый узел v‘

сделать двух самых правых сыновей узла v левым и правым сыновьями узла v‘;

if у v нет отца then

образовать новый корень r;

сделать v левым, а v ‘ правым сыном корня r

пусть f – отец узла v;

сделать v‘ сыном узла f, расположенным непосредственно справа от v,

if теперь у f четыре сына then ДОБАВСЫНА(f)

Рис. 3.30. Процедура ДОБАВСЫНА.

значения L и М, производятся процедурой ДОБАВСЫНА (здесь они опущены–предлагаем их в качестве упражнения). 

Теорема 3.6. Алгоритм 3.4 вставляет новый элемент в 2-3-дерево с п листьями за время, не превосходящее O(log n). Более того, этот алгоритм сохраняет порядок исходных листьев и структуру 2-3-дерева.

Доказательство. Очевидная индукция по числу вызовов процедуры ПОИСК показывает, что новый лист становится сыном того узла, какого надо. Порядок исходных листьев не затрагивается. Что касается времени работы, то в силу леммы 3.6 высота 2-3-дерева с п листьями не превосходит log п. Поскольку добавсына(v) рекурсивно вызывает себя только на отце узла v, может произойти не более log п рекурсивных вызовов. Каждый вызов ДОБАВСЫНА занимает постоянное время, так что общее время не превосходит O(log n). 

Элемент а можно удалить из 2-3-дерева способом, по существу обратным к вставке. Пусть а – метка листа l. Рассмотрим отдельно три случая.

Случай 1. Если l – корень, удаляем его. (В этом случае а был единственным элементом в дереве.)

Случай 2. Если l – сын узла, имеющего трех сыновей, удаляем его.

Случай 3. Если l – сын узла, имеющего двух сыновей s и l, то может быть одно из двух:

а) f – корень; удаляем l и f и делаем корнем второго сына s;

б) f – не корень. Допустим, что f имеет брата 1 слева от себя. Случай, когда брат находится справа, рассматривается аналогично. Если у g только два сына, делаем узел s самым правым сыном узла g, удаляем l и рекурсивно вызываем процедуру удаления, чтобы удалить f. Если у g три сына, то самого правого сына делаем левым сыном узла f и удаляем l.

Пример 3.11. Из 2-3-дерева на рис. 3.28 удалим элемент 4. Лист с меткой 4 является сыном узла с, у которого два сына. Поэтому делаем лист с меткой 5 самым правым сыном узла b, удаляем лист с меткой 4 и затем рекурсивно удаляем узел с.

Узел с – сын узла а, у которого два сына. Узел а’ – правый брат узла а. Поэтому по симметрии делаем b самым левым сыном узла а удаляем с и затем рекурсивно удаляем а.

Узел а – сын корня. Применяя случай За, делаем а’ корнем остающегося дерева (рис. 3.31). 

Формальную детализацию процесса, а также доказательство того, что на 2-3-дереве с п листьями его можно выполнить не более чем за O(log n) шагов, оставляем в качестве упражнения.

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

Исследуем теперь операцию MIN. Наименьший элемент в 2-3-дереве расположен в самом левом листе, который, конечно, можно найти за O(log п) шагов. Поэтому любую последовательность из п операций ВСТАВИТЬ, УДАЛИТЬ и MIN можно с помощью 2-3-дерева выполнить за время O(п log п). Тем самым обосновано наше утверждение о том, что 2-3-дерево может служить для реализации очереди с приоритетами с производительностью O(п log п). Для этой же цели годятся также сортирующее дерево, используемое в алгоритме Сортдеревом, и АВЛ-дерево, обсуждаемое в упр. 3.30– 3.33.

Источник

Атд словарь. реализация словаря 2-3 деревьями.

2-3 деревом называется дерево, в котором каждый внутренний узел имеет двух или трех сыновей, а длины всех путей от корня в листья совпадают между собой. Поскольку в процессе поиска необходимо делать выбор между тремя сыновьями, в 2-3 дереве каждый внутренний узел дерева хранит не один, а два ключа. Линейно упорядоченное множество S можно представить 2-3 деревом, приписав его элементы листьям дерева с использованием заданного порядка. Каждый внутренний узел v содержит две метки L(v) и M(v) , где L(v) — наибольший элемент, приписанный листьям самого левого сына вершины v , M(v) — наибольший элемент, приписанный листьям второго сына этой вершины. Используя эти метки для поиска, легко решить задачу НАЙТИ за время пропорциональное высоте дерева (O(log(n)) ). 2-3 деревья служат хорошей структурой данных для АТД со следующим набором операций:

2. ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ

3. ВСТАВИТЬ, УДАЛИТЬ, ОБЪЕДИНИТЬ, НАЙТИ С МИНИМАЛЬНЫМ

4. ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ, СЦЕПИТЬ, РАСЦЕПИТЬ

Как уже упоминалось выше, АТД с набором операций из множества 1 называется

Словарем, из множества 2 – Очередью с приоритетами, 3 – Сливаемым деревом, 4 –

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

Словари и очереди с приоритетами.Рассмотрим реализацию операции ВСТАВИТЬ в 2-3 дерево. Сначала поиском по дереву определяется место для нового элемента a в последовательности меток листьев дерева. Для этого ищут узел f дерева, имеющий двух или трех сыновей, к листьям которог необходимо приписать a . Если у узла f два сына, то a становится третьим сыном, причем a вставляется с учетом отношения линейного порядка на листьях дерева. В зависимости от позиции элемента a последовательности сыновей вершины f , производится коррекция ее меток L( f ) и M( f ) таким образом, чтобы они отражали порядок следования сыновей вершины f . Далее с учетом этой информации необходимо рекурсивно подправить метки вершин (предков узла f ), лежащих на пути от вершины f к корню дерева. Если после добавления вершины a , число листьев вершины f становится равным 4, то вершину f расщепляют на два узла f и g с общим отцом, оставляя двух левых сыновей вершине f , а двух правых относя вершине g . Поскольку вершины f и g , имеют общего отца q , проверяют число сыновей у вершины q . Если q имеет не более трех сыновей, процесс расщепления завершается, если числосыновей равно 4, то вершина q ,аналогично f расщепляется на две, каждая из которых имеет двух сыновей, и процесс продолжается по направлению к корню дерева. Как и в первом случае в процессе

приведения дерева к виду 2-3 дерева, необходимо откорректировать метки вершин на пути от вершины f к корню. Общее время операции по вставке элемента в n –элементное множество равно O(log n) шагов. Процесс удаления вершины из дерева является обратным к операции вставки. Пусть удаляемый элемент a принадлежит листу z . Рассмотрим три случая: 1. Если z является корнем дерева, то он удаляется, и мы получаем пустое дерево. 2. Если z имеет двух братьев, то z удаляется, и далее производится корректировка меток вершин, лежащих на пути от отца вершины z до корня дерева. 3. Если z сын узла f , имеющего двух сыновей s и z , то возможно два варианта продолжения: a) f — корень, удаляем z и f , корнем дерева становится s . b) f — не корень. Если f имеет слева от себя брата g 28, то подсчитывается число сыновей вершины g . Если у g два сына, делаем узел s самым правым сыном вершины g , удаляем z и рекурсивно вызываем процедуру удаления узла f . Если у g три сына, то самого правого сына делаем левым сыном узла f , и удаляем z . Далее проводится корректировка меток

вершин, лежащих на пути от g (возможно и f ) до корня дерева.

Показано [2], что операция удалить элемент из множества, содержащего n элементов, также занимает O(log n) времени. Таким образом, для словаря 2-3 дерево представляет структуру, позволяющую обеспечить выполнение последовательности из n операций ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ за O(nlog n) шагов. Рассмотрим одно из возможных представлений в виде 2-3 дерева уже знакомого нам

Проиллюстрируем вставку и удаление элемента на следующих примерах. Добавляя элемент 5, получим

Вершина (6:7) содержит 4 сына и должна быть расщеплена на две вершины (5:6) и (7:9), каждая из которых имеет отцом вершину (9:11). Далее поднимаясь на один уровень вверх, исследуем вершину (9:11). Поскольку эта вершина содержит 4 сына, она также расщепляется на две вершины. Исследование вершины верхнего уровня (15:30) показывает, что она удовлетворяет условиям определения 2-3 дерева. И хотя на данном шаге процесс корректировки структуры дерева может быть прерван, процесс корректировки меток продолжается до корня дерева. Результат построения показан на рисунке ниже:

Из получившейся структуры удалим вершину 11. Поскольку после удаления вершина(10:11) имеет единственного сына, то второго сына заимствуем от вершины (12:13) с корректировкой соответствующих меток. Далее необходимо откорректировать метки вершин, находящихся на пути от отца вершин (10:11) и (12:13) до корня дерева.

Что касается очередей с приоритетами, то выполнение операции МИНИМУМ требует O(log n) шагов(минимальный элемент является крайним слева в упорядоченном списке листьев).Следовательно,2-3 деревья служат для реализации АТД Очередь с приоритетами с производительностью O(nlog n) , где n общее число запросов.

Статьи к прочтению:

Словарь данных в Oracle(DICT)

Похожие статьи:

• Задача поиска. деревья бинарного поиска (дбп). операции над ними. Бинарное дерево поиска – это бинарное упорядоченное дерево, у которого каждой вершине приписан уникальный ключ поиска, причем выполнено соотношение:…
• По методу бинарного дерева Можно сократить время поиска искомого элемента в таблице идентификаторов, не увеличивая значительно время, необходимое на ее заполнение. Для этого надо…

Источник