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

0

Человеку свойственен выбор. Всегда хочется иметь несколько вариантов решения возникающих проблем, так как можно ознакомиться с преимуществами и последствиями каждого из них. Эта глава посвящена изучению разных способов решения проблем, обсуждавшихся в предыдущей главе — реализации упорядоченных словарей (глава 8). Конкретно исследуем несколько альтернативных структур данных на основе деревьев, используемых для реализации упорядоченных словарей.

Эта глава начинается анализом бинарных поисковых деревьев в разделе 9.1, затем объясняется поддержка ими простых древовидных реализаций упорядоченных словарей, не гарантирующих эффективного выполнения. Тем не менее они служат основой большого количества вариантов реализации словарей. Некоторые из них обсуждаются в этой главе. Одной из классических реализаций является AVL-дерево, представленное в разделе 9.2. Это бинарное поисковое дерево, способное выполнять операции поиска и обновления за время, пропорциональное 0(log п).

В-разделе 9.3 приведена концепция многопроходного поискового дерева, представляющего собой упорядоченное дерево, в котором каждый составной узел может хранить несколько объектов и иметь несколько дочерних элементов. Многопроходное поисковое дерево является обобщенным представлением бинарного поискового дерева, рассматриваемого в разделе 9.1, и, как и бинарное дерево, может быть превращено с помощью соответствующих дополнительных средств в удобную для словарей структуру данных. Преимуществом использования таких многопроходных деревьев является то, что для хранения объектов они зачастую обходятся меньшим количеством составных узлов, чем бинарные поисковые деревья. Но точно так же, как и бинарным деревьям, многопроходным деревьям требуются дополнительные методы для обеспечения эффективной работы со всеми словарными методами.

В разделе 9.4 обсуждаются (2,4)-деревья (иногда обозначаемые как 2-4-деревья), известные также как 2-3-4-деревья. Это многопроходные поисковые деревья, составные узлы которых имеют одинаковую глубину, хранят 1, 2 или 3 ключа и имеют соответственно 2, 3 или 4 дочерних элемента. Преимущество таких деревьев заключается в наличии простых интуитивно понятных алгоритмов ввода и удаления ключей. Методы обновления реорганизуют (2,4)-деревья с помощью естественных операций, разбивающих и разграничивающих стоящие рядом узлы или перемещая в них ключи. (2,4)-дерево, хранящее п элементов, использует 0(п) пространства и поддерживает поиск, ввод и удаление максимально за 0(log п) времени.

В разделе 9.5 представлены красно-черные деревья. Это бинарные поисковые деревья, узлы которых представляются окрашенными в красный и черный цвета таким образом, что цветовая схема обеспечивает логарифмическую высоту. Между красно-черными и (2,4)-деревьями существует простое, с точки зрения сопоставления значений и цветов,, соответствие. Использование такого соответствия мотивирует и обеспечивает интуитивно понятную возможность работы с более сложными алгоритмами ввода и удаления в красно-черных деревьях, которые построены на принципах ротации и перекрашивания. Как и AVL-деревья, красно-чер- ные деревья, хранящие п объектов, используют О(п) пространства и поддерживают операции поиска, ввода и удаления максимально за 0(log п) времени. Преимуществом красно-черных деревьев перед AVL-деревьями является возможность реструктуризации после каждого ввода или удаления за всего 0(1) ротацию (хотя и более сложными операциями).

И наконец, в разделе 9.6 обсуждается внешний поиск, то есть поиск во внешней памяти (которой обычно служит диск). Рассмотрено так называемое В-дерево, многопроходное дерево, которое может использоваться для хранения и поиска объектов, сводя к минимуму количество операций ввода/вывода (I/O).

Существует достаточно большое количество поисковых деревьев, в том числе обсуждаемых в настоящей главе, и авторы понимают, что читатель или преподаватель, располагающие ограниченным временем, посчитают необходимым ознакомиться только с несколькими специальными темами. По этой причине на рис. 9.1 приводится концептуальное строение разделов данной главы. Таким образом читатель может сконцентрировать внимание на бинарных поисковых деревьях и затем изучить AVL-деревья, (2,4)-деревья (возможно, совместно с красно-черными деревьями) и/или внешний поиск.

Рис. 9.1. Связь между разделами главы

. Поскольку все структуры данных, обсуждаемые в данной главе, реализуют АТД «упорядоченный словарь», предварительно и кратко ознакомимся с основными методами:

•          findAllElements(A;): возвращает итератор всех элементов с ключами, равными к\

•          insertItem(A:,e): вводит объект с элементом е и ключом к (при его наличии) и возвращает его элемент;

•                       removeElement(A;): удаляет объект с ключом к\

•          removeAllElements(A;): удаляет все объекты с ключом к, возвращает итератор их элементов.

Методы findElement и removeElement возвращают NO_SUCH_KEY, если к не найден. АТД «упорядоченный словарь» также включает поисковые методы closestKeyBefore(A;), closestElemBefore(A;), closestKeyAfter(/:) и closestElemAfter(A:), но их выполнение аналогично findElement. Так что в этой главе сконцентрируем внимание на findElement как на основной поисковой операции в упорядоченном словаре.

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

По теме:

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