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 tree

В информатике , А 2-3 — дерево представляет собой древовидную структуру данных , где каждый узел с детьми ( внутренний узел ) имеет либо двух детей (2-узел) и один элемент данных или трех детей (3-узлы) и два элемента данных. Дерево 2–3 — это B-дерево порядка 3. Узлы вне дерева ( листовые узлы ) не имеют дочерних элементов и одного или двух элементов данных. 2–3 дерева были изобретены Джоном Хопкрофтом в 1970 году.

Требуется сбалансировать 2–3 дерева, то есть каждый лист находится на одном уровне. Отсюда следует, что каждое правое, центральное и левое поддерево узла содержит одинаковый или почти одинаковый объем данных.

Определения

Мы говорим, что внутренний узел является 2-узлом, если он имеет один элемент данных и два потомка.

Мы говорим, что внутренний узел является 3-узлом, если он имеет два элемента данных и три дочерних узла .

4-узел , с элементами три данных, могут временно создаваться во время манипуляций с деревом , но никогда не постоянно хранится в дереве.

Мы говорим , что T является 2-3 — деревом тогда и только тогда , когда один из следующего утверждения:

• Т пусто. Другими словами, у T нет узлов.
• T — это 2-узел с элементом данных a . Если у T есть левый дочерний элемент p и правый дочерний элемент q , то
  • p и q — 2–3 дерева одинаковой высоты ;
  • a больше, чем каждый элемент в p ; а также
  • a меньше, чем каждый элемент данных в q .
  • p , q и r — 2–3 дерева одинаковой высоты;
  • a больше каждого элемента данных в p и меньше каждого элемента данных в q ; а также
  • b больше каждого элемента данных в q и меньше каждого элемента данных в r .

  Характеристики

  • Каждый внутренний узел является двух- или трехузловым.
  • Все листья находятся на одном уровне.
  • Все данные хранятся в отсортированном порядке.

  Операции

  Поиск

  Поиск элемента в дереве 2–3 аналогичен поиску элемента в двоичном дереве поиска . Поскольку элементы данных в каждом узле упорядочены, функция поиска будет направлена ​​на правильное поддерево и, в конечном итоге, на правильный узел, содержащий элемент.

  1. Пусть T будет 2–3 деревом, а d — элементом данных, который мы хотим найти. Если T пусто, значит, d нет в T, и мы закончили.
  2. Пусть т быть корнем Т .
  3. Предположим, что t — лист.
     • Если d не в т , то d не в T . В противном случае, д в Т . Нам не нужны дальнейшие шаги, и все готово.
  4. Предположим, что t — 2-узел с левым дочерним элементом p и правым дочерним элементом q . Пусть a будет элементом данных в t . Есть три случая:
     • Если d равно a , то мы нашли d в T и все готово.
     • Если , то установите для T значение p , которое по определению является деревом 2–3, и вернитесь к шагу 2. d
     • Если , а затем установить Т к ц и вернуться к шагу 2. d > а a>
  5. Предположим, что t — 3-узел с левым дочерним элементом p , средним дочерним элементом q и правым дочерним элементом r . Пусть a и b — два элемента данных t , где . Есть четыре случая: а < б
     • Если d равно a или b , то d находится в T, и все готово.
     • Если , то установите T на p и вернитесь к шагу 2. d
     • Если , а затем установить Т к ц и вернуться к шагу 2. а
     • Если , то установите T на r и вернитесь к шагу 2. d > б b>

  Вставка

  Вставка сохраняет сбалансированное свойство дерева.

  Чтобы вставить в 2-узел, новый ключ добавляется к 2-узлу в соответствующем порядке.

  Чтобы вставить в 3-узел, может потребоваться дополнительная работа в зависимости от расположения 3-узла. Если дерево состоит только из трех узлов, этот узел разбивается на три двухузла с соответствующими ключами и дочерними элементами.

  Если целевой узел является 3-узлом, а родительский — 2-узлом, ключ вставляется в 3-узел, чтобы создать временный 4-узел. На иллюстрации ключ 10 вставлен в 2-узел с 6 и 9. Средний ключ — 9, и он повышается до родительского 2-узла. В результате остается 3-узел из 6 и 10, который разделяется на два 2-узла, которые являются дочерними по отношению к родительскому 3-узлу.

  Если целевой узел является 3-узлом, а родительский — 3-узлом, создается временный 4-узел, который затем разделяется, как указано выше. Этот процесс продолжается вверх по дереву до корня. Если корень должен быть разделен, то следует процесс одного 3-узла: временный 4-узловый корень разбивается на три 2-узла, один из которых считается корнем. Эта операция увеличивает высоту дерева на единицу.

  Параллельные операции

  Поскольку 2–3 дерева аналогичны по структуре красно-черным деревьям , параллельные алгоритмы для красно-черных деревьев можно применять и к 2–3 деревьям.

  Источник

  Читайте также:  Масло чайного дерева при грибке ногтей рук