Главная » Java, Структуры данных и алгоритмы » (2,4)-деревья

0

Многопроходные поисковые деревья, обеспечивающие небольшие размеры вторичных структур данных в каждом узле и сбалансированность первичного многопроходного дерева, называются ми, иногда 2—4 или 2-3-4-деревьями. Такая структура данных реализует поставленные цели при наличии всего двух простых свойств (см. рис. 9.14):

Size Property (размер) — каждый узел имеет максимум четыре дочерних элемента;

Depth Property (глубина) — все составные узлы имеют одинаковую глубину.

Снова будем исходить из того, что простые узлы пусты, и для простоты опишем методы поиска и обновления с учетом того, что простые узлы являются реальными, хотя такое требование и необязательно.

Соблюдение свойства размера для (2,4)-дерева позволяет сохранять простую структуру узлов многопроходного поискового дерева, а также дает возможность говорить об альтернативном термине «2-3-4-дерево», поскольку, согласно формулировке свойства, узел может иметь 2, 3 или 4 дочерних элемента. Еще одним составляющим этого определения является возможность представлять словарь D(v), хранящийся в каждом из составных узлов, с помощью вектора и по-прежнему затрачивать 0(1) времени на выполнение всех операций (так как dmax — 4). Свойство глубины, с другой стороны, позволяет соблюдать границу высоты (2,4)-дерева.

Рис. 9.14. (2,4)-дерево

Утверждение 9.4. Высота (2,4)-дерева, хранящего п элементов, составляет Q(log п).

Доказательство. Пусть h — высота (2,4)-дерева Г, хранящего п элементов. Предположим, что выполняются неравенства

Для доказательства заметим сначала, что, согласно свойству размера, возможно максимально 4 узла на глубине 1, на глубине 2 — максимально 42 узла и так далее. Таким образом, количество простых узлов в Г будет составлять максимум 4А. Аналогично, согласно свойству глубины и определению (2,4)-дерева, необходимо минимально иметь 2 узла на глубине 1, минимально 22 — на глубине 2 и так далее. То есть количество простых узлов в Т составит как минимум 2Л. Кроме того, согласно утверждению 9.3, количество простых узлов в Гсоставляет п + 1. В результате име- ем 2h < п + 1 и п + 1 < 4Л.

Логарифмируя обе части этих неравенств, получаем h < log{n+ 1) и log(n + 1) < 2А, что подтверждает предположения 9.6 и 9.7.

Утверждение 9.4 констатирует, что свойства размера и глубины позволяют эффективно поддерживать сбалансированность (раздел 9.3) многопроходного поискового дерева. Более того, это утверждение предполагает, что выполнение поиска в (2,4)-дереве занимает 0(log п) времени, а выбор специфической реализации вторичной структуры данных не является существенной деталью, поскольку максимальное количество дочерних элементов dmax остается постоянным (4). Таким образом можно, например, использовать простейшую реализацию упорядоченного словаря — поисковую таблицу — для каждой из вторичных структур.

Операции обновления

Соблюдение свойств размера и глубины в (2,4)-дереве требует, однако, ряда дополнительных действий после выполнения операций ввода и удаления.

Ввод

Чтобы ввести новый объект (к, х) с ключом к в (2,4)-дерево Г, вначале выполняется поиск к. Поскольку Т не содержит элементов с ключом к, поиск заканчивается безрезультатно на последнем простом узле z. Пусть v — родительский элемент узла ъ Введем новый объект в узел v и добавим новый дочерний элемент w (простой узел) в v слева от г. То есть добавим объект (к, х, w) в словарь D(v).

Предлагаемый метод ввода соблюдает свойство глубины, поскольку новый простой узел добавляется на уровень, где расположен уже существующий простой узел. Но при этом может нарушиться свойство размера, так как после ввода узел v из 4-узла может превратиться в 5-узел, что может повлечь изменение структуры дерева, и оно больше не будет (2,4)-де- ревом. Такое нарушение свойства размера называется переполнением значимости узла v, которое должно быть устранено для восстановления свойств (2,4)-дерева. Пусть v\, …,V5 будут дочерними элементами узла v, а к\, …, — ключами, хранящимися в v. Для устранения переполнения значимости узла v выполним следующую разделительную операцию (см. рис. 9.15):

•                замещаем v двумя узлами v’ и v’\ где

?                                  v’— 3-узел с дочерними элементами vb v2, v3, хранящими ключи к\ и к

?                                  v" — 2-узел с дочерними элементами v4, v5, хранящими ключ

•          если v был корнем Т\ создаем новый корневой узел и; иначе и будет родительским элементом v;

•          вводим ключ къ в и и определяем v’hv" дочерними элементами и так, что если v был дочерним элементом / узла w, то v’ и v" становятся дочерними элементами / и /1 + 1 узла и соответственно.

Последовательность действий при вводе в (2,4)-дерево показана на рис. 9.16.

Анализ ввода в (2,4)-дерево

Разделительная операция вызывает изменение постоянного количества узлов дерева и 0(1) объектов, хранящихся в этих узлах. Следовательно, она может быть реализована так, чтобы выполняться за 0(1) времени.

Рис. 9.15. Разделение узла: (а) переполнение 5-узла v; (b) третий ключ узла v, введенный в родительский элемент и узла v; (с) узел v, замещенный 3-узлом v’ и 2-узлом v"

Рис. 9.16. Последовательность действий при вводе в (2,4)-дерево: (а) первоначальный вид дерева с одним объектом; (Ь) ввод объекта 6; (с) ввод 12; (d) ввод 15, вызывающий переполнение; (е) разделение, в результате которого появляется новый корневой узел; (0 после разделения; (g) ввод 3; (h) ввод 5, вызывающий переполнение; (i) разделение; (j) после разделения; (к) ввод 10; (1) ввод 8

В результате разделительной операции в узле v может произойти новое переполнение, но уже в родительском узле и. Если такое переполнение имеет место,- оно в свою очередь вызывает разделение узла и (см. рис. 9.17). Разделительная операция либо устраняет переполнение, либо продвигает переполнение в родительский элемент текущего узла. Следовательно, количество разделительных операций ограничено высотой дерева, которая равна 0(log п), согласно утверждению 9.4. Из этого следует, что общее время выполнения ввода в (2,4)-дереве есть 0(log п).

Рис. 9.17. Ввод в (2,4)-дерево, вызывающий цепь разделительных операций: (а) до ввода; (Ь) ввод 17, вызвавший переполнение; (с) разделение; (d) новое переполнение после разделения; (е) следующее разделение, создающее новый корневой узел; (f) результат

Удаление

Рассмотрим теперь удаление объекта с ключом к из (2,4)-дерева Т. Эта операция начинается с поиска в дереве Г объекта с ключом к. Удаление такого объекта из (2,4)-дерева всегда можно свести к ситуации, когда удаляемый объект находится в узле v, дочерние элементы которого являются простыми узлами. Например, допустим, что объект с ключом к, который нужно удалить, хранится в объекте (kj, Xj) узла z, имеющего только составные дочерние элементы. В этом случае объект (kj, xt) заменяется на подходящий объект, хранящийся в узле v с простыми дочерними элементами в следующем порядке (рис. 9.18, d):

1.    Отыскивается самый правый составной узел v ветви, корнем которой является дочерний элемент / узла z, с условием, что дочерние элементы узла v являются простыми узлами.

2.     Объект (kj, Xj) в узле z заменяется на последний объект узла v.

При наличии удаляемого объекта в узле v с простыми дочерними элементами (либо он там уже был, либо его туда перебросили) производится обычное удаление объекта из v (то есть из словаря Z)(v)), и узел / составного узла v удаляется.

Удаление объекта (и дочернего элемента) из узла v происходит с соблюдением свойства глубины, поскольку всегда удаляется простой дочерний элемент узла v, у которого имеются только простые дочерние элементы. Однако удаление такого простого узла может привести к нарушению свойства размера узла v, то есть если v был 2-узлом, то теперь он превращается в пустой 1-узел (рис. 9.18, d-e), что не разрешено в (2,4)-де- реве. Такой тип нарушения свойства размера называется потерей значимости (underflow) узла v. Для устранения этого выясняем, есть ли по соседству 3- или 4-узлы. При наличии такого узла w выполняем переводную операцию, при которой дочерний элемент узла w передвигается в узел v, ключ узла w — в родительский узел и узлов v и w, а ключ узла и — в узел v (см. рис. 9.18, Ь-с). Если узел v имеет всего один соседний узел или оба расположенных рядом узла являются 2-узлами, то выполняется операция слияния, при которой v объединяется с соседним узлом, создавая новый узел v’, а ключ перемещается из родительского узла и прежнего узла v в новый узел v’ (см. рис. 9.19, e-f).

Операция слияния в узле v может снова вызвать потерю значимости в родительском узле и узла v (рис. 9.19). Следовательно, в соответствии с утверждением 9.4, количество операций слияния будет ограничено высотой дерева, составляющей 0(log п). Если потеря значимости начинает распространяться вверх к корню, то корень просто удалится (см. рис. 9.19, c-d). Последовательность удалений из (2,4)-дерева изображена на рис. 9.18 и 9.19.

Рис. 9.18. Последовательность удалений из (2,4)-дерева: (а) удаление 4, вызывающее потерю значимости; (Ь) переводная операция; (с) после переводной операции; (d) удаление 12, вызывающее потерю; (е) операция слияния; (0 после слияния; (g) удаление 13; (h) после удаления 13

 

Рис. 9.19. Продвижение операции слияния в (2,4)-дереве: (а) удаление 14, вызывающее потерю значимости; (Ь) слияние, вызывающее очередную потерю значимости; (с) следующее слияние, вызывающее удаление корня; (d) результат

Производительность

В табл. 9.3 приведены результаты анализа временя выполнения основных операций словаря, реализованного (2,4)-деревом. Анализ основан на следующих положениях: .

•                                    высота (2,4)-дерева, хранящего п объектов, согласно утверждению 9.4, составляет 0(log п)\

•                        разделение, перемещение и слияние занимают 0(1) времени;

•                        поиск, ввод или удаление объекта требуют прохода 0(log п) объектов.

Операции

Время

size, isEmpty findElement, insertltem, removeElement findAIIEIements, removeAIIEIements

0(1) 0(log ri) 0(log n+s)

Таблица 9.3. Производительность «-элементного словаря, реализованного (2,^-деревом, где s — размер возвращаемых методами findElements и remove All Elements итераторов. Размер занимаемого дискового пространства составляет 0(п)

Таким образом, обеспечивают быстрый поиск и обновление. Кроме того, появляется еще одна интересная возможность применения, которая рассматривается ниже.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии