Главная » Java, Структуры данных и алгоритмы » Многопроходные поисковые деревья

0

Некоторые из структур данных, описываемых в этой главе, представляют собой многопроходные деревья, то есть деревья с составными узлами, имеющими два и более дочерних элемента. В этом разделе приведен способ применения многопроходных деревьев в качестве поисковых,

Рис. 9.12. Время выполнения поиска и обновления в AVL-дереве. Затраты времени составляют 0(1) для каждого уровня и состоят из затрат на направленную вниз фазу, традиционно включающую поиск, и направленную вверх фазу, включающую обновление значений высоты и трехуровневые реструктуризации (ротации)

включая способы хранения объектов и поисковые операции. Напомним, что понятие объект, сохраняемый в поисковом дереве, означает пару (к,х), где к — ключ, ах — элемент, соответствующий этому ключу. В настоящем разделе описывается способ обновлений в многопроходных деревьях. Конкретные же детали методов обновления зависят от дополнительных свойств, которые будут введены для многопроходных деревьев и обсуждаются в разделах 9.4 и 9.6.

Определение

Пусть v — узел упорядоченного дерева. Если v имеет d дочерних элементов, назовем его d-узлом. Многопроходным поисковым деревом будем считать упорядоченное дерево Г, имеющее следующие свойства (как показано на рис. 9.13, а:

•          каждый составной узел дерева Г имеет по крайней мере два дочерних элемента, то есть каждый составной узел является af-узлом, где d> 2;

•          каждый составной узел дерева Тхранит набор объектов в виде (к,х), где к — ключ, а х — элемент;

•          каждый flf-узел v дерева Тс дочерними элементами vh v2, vd, хранит d – 1 элементов (к\у х^, (kd_ ь xd_ {), где kj < … < kd_ ь

•          будем считать, что к0 = -оо, a kd = -юо. Для каждого объекта (к,х), хранящегося в узле ветви v, произрастающей из v„ / = 1, …, d, имеем ki.j < к < kj.

Таким образом в наборе ключей, хранящихся в v, содержащем специальные функциональные ключи ко = -оо и kd = +оо, каждый ключ к, содержащийся в ветви дерева Т, произрастающей из дочернего узла v/, должен «находиться между» двумя ключами, имеющимися в v. Исходя из этого, можно вывести правило, что узел с d дочерними элементами хранит d – 1 обычных ключей. Этот же вывод служит основанием алгоритма поиска в многопроходном поисковом дереве.

Согласно вышеприведенному определению, простые узлы многопроходного поискового дерева являются «заглушками». Таким образом, бинарное поисковое дерево рассматривается (раздел 9.1) как особый случай использования многопроходного поискового дерева, в котором каждый составной узел хранит один объект и имеет два дочерних элемента. В крайнем случае многопроходное поисковое дерево может иметъ только один составной узел, хранящий все объекты. Кроме того, поскольку простые узлы могут быть null или ссылками на объект NULL_NODE, следует простой вывод, что они в принципе являются узлами, в которых ничего не хранится.

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

 

 

Рис. 9.13. (а) Многопроходное поисковое дерево Т\ (Ь) маршрут поиска в Г для ключа 12 (безуспешный поиск); (с) маршрут поиска в Г для ключа 24 (успешный поиск)

Утверждение 9.3. Многопроходное поисковое дерево, сохраняющее п элементов, имеет п + 1 простых узлов.

Доказательство этого утверждения оставляем для упражнения 3-9.14.

Поиск в многопроходном дереве

* Осуществить поиск элемента с ключом к достаточно просто с помощью многопроходного поискового дерева Г, начиная от корня Т (см. рис. 9.13, Ь-с). Проходя через d-узел v, ключ к сравнивается с ключами к\, kd- ь хранящимися в v. При к = для ^некоторого / поиск успешно завершается. Если ключи не равны, переходим к дочернему узлу V/ узла v, где к[_\ < к < ki (напомним, что в рассматриваемом случае ко = -оо и kj = +оо). При достижении простого узла, где ничего не хранится, поиск завершается безрезультатно.

Структуры данных для многопроходных деревьев

В разделе 6.4 обсуждались различные способы представления обычных деревьев. Каждое из этих представлений может использоваться и для многопроходных поисковых деревьев. Единственное, что при этом требуется, — это добавить в каждый узел некоторую дополнительную информацию в виде набора объектов (включая ключи), ассоциируемых с данным узлом. А точнее, необходимо добавить ссылку на некий контейнер, хранящий объекты узла v.

При использовании бинарного дерева для представления упорядоченного словаря D осуществляется сохранение ссылки на единственный объект каждого составного узла. При использовании для этого многопроходного поискового дерева необходимо хранить ссылку на упорядоченный набор объектов, ассоциируемый с v в каждом составном узле v дерева Т. Такое объяснение может выглядеть как замкнутый цикл, поскольку для представления упорядоченного словаря требуется представление упорядоченного словаря. Однако избежать такой циклической формулировки можно с помощью вспомогательного механизма, в котором используется менее сложное решение проблемы для получения более эффективного решения. В данном случае вспомогательный механизм включает представление упорядоченного множества, ассоциируемого с каждым составным узлом, использующим словарную структуру данных, которая уже создана (к примеру, поисковая таблица на основе вектора, описанная в разделе 8.5). В частности, исходя из того, что уже имеется способ реализации упорядоченных словарей, можно реализовать многопроходное поисковое дерево, взяв дерево Ти сохранив такой словарь в каждый d-узел v дерева Т.

Словарь, который сохраняется в каждом узле v, будет называться вторичной структурой данных, так как применяется для поддержки большей, первичной структуры данных. Словарь, хранящийся в узле v, обозначим как D(v). Объекты, хранящиеся в Z)(v), позволят определить дочерний элемент, к которому следует перейти в процессе поиска. А именно, для каждого узла v дерева Тс дочерними элементами v\, vd и объектами (к\,х\), …, (kd_\, Xd-\) в словаре D(v) сохраняются объекты (к\, х\, v\), (къ хъ v2), …, (kd_ ь xd_ ь Vd- 1), null, vd).

Применяя такую реализацию многопроходного поискового дерева, обработка rf-узла v в процессе поиска элемента дерева Т с ключом к может быть выполнена с помощью поисковой операции для нахождения объекта (?/, Xj, v/) в D(v) с наименьшим ключом, большим или равным к, как в операции closestElemAfter(/:) (см. раздел 8.4). Здесь различаются два случая:

•          если к < kh обрабатываем дочерний элемент v, продолжая поиск (заметим, что при возврате специального ключа kd = +00 все ключи, хранящиеся в узле v, будут меньше к, и поиск продолжается в дочернем элементе vd);

•     если к = kh то поиск успешно заканчивается.

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

Теперь определим время, требующееся для выполнения поиска в Т. Время, затрачиваемое на один d-узел дерева Тв процессе поиска, зависит от реализации вторичной структуры D(v). Если D(v) реализован в виде векторной сортированной последовательности (то есть поисковой таблицы), то обработка v будет выполняться за 0(log d) времени. Если же ЕКу) реализован с помощью несортированной последовательности (то есть регистрационным файлом), то обработка v займет 0(d) времени. Пусть dmax обозначает максимальное количество дочерних элементов любого узла дерева Т, a h — его высоту. Время поиска в многопроходном г1оисковом дереве составит 0(hdmax) или 0(h log dmax) в зависимости от особенностей реализации вторичной структуры узлов дерева Т (словарей D(v)). Если dmax является постоянным, время выполнения поиска составит 0(h) независимо от реализации вторичной структуры.

Таким образом, первой задачей при работе с многопроходным поисковым деревом является сохранение высоты дерева как можно меньшей, то есть требуется, чтобы h являлась логарифмической функцией п количества всех объектов словаря. Такое поисковое дерево с логарифмической высотой называется сбалансированным поисковым деревом (balanced search tree). Рассмотрим далее сбалансированное поисковое дерево, dmax которого равен 4.

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

По теме:

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