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

0

Бинарные деревья представляют собой прекрасную структуру данных для хранения объектов упорядоченного словаря. Как отмечалось в п. 6.3.4, бинарным поисковым деревом является дерево Г, каждый составной узел v которого хранит объект (к,е) словаря D и

•                       |<слючи, хранящиеся в левой ветви v, меньше или равны к\

•                       ключи, хранящиеся в правой ветви v, больше или равны к.

Простые узлы Г не хранят никаких ключей или элементов Д а служат только в качестве заглушек. Простые узлы могут быть нулевыми или можно ссылаться на них, как на объект NULL_NODE, поскольку существует позиционный контейнер (positional wrapper) для любого простого узла, определяющего его родительский элемент. Для простоты обсуждения предполагаем, что простые узлы — Это обычные узлы дерева Г, в них ничего не хранится.

Независимо от представления пустых простых узлов, важным свойством бинарного поискового дерева является представление упорядоченного словаря. То есть бинарное поисковое дерево должно иерархически представлять упорядочение своих ключей через «родительско-дочерние» отношения. В частности, легко убедиться, что симметричный проход (см. п. 6.3.4) бинарного поискового дерева Т обследует все ключи его словаря в неубывающем порядке (см. рис. 9.2, а).

9-1-1- Поиск

Для выполнения операции findElement(A:) в словаре Д представленном бинарным деревом поиска Г, рассмотрим деребо Г как дерево решений (см. рис. 6.5). В таком случае задаваемый каждому составному узлу v запрос будет ключом поиска к, который меньше, равен или больше ключа, хранящегося в узле v, отмеченном с помощью key(v). При «меньше» поиск продолжается в левой ветви. При «равен» поиск успешно заканчивается. Если ответ «больше», то поиск продолжается в правой ветви. И наконец, если обнаружен простой узел, то поиск заканчивается безуспешно (см. рис. 9.2, Ь).

Рис. 9.2. (а) Бинарное поисковое дерево Г, представляющее упорядоченный словарь D с целочисленными ключами; (Ь) узлы дерева Т\ обследованные при (успешном) выполнении операции-findElement(76) над деревом D. Для простота показаны только ключи без элементов

Во фрагменте кода 9.1 приводится рекурсивный метод TreeSearch, в основу которого положена описанная стратегия поиска в бинарном дереве Т. Имея ключ поиска к и узел v дерева Г, метод TreeSearch возвращает узел (позицию) w ветви T(v) дерева Г, корнем которой является v, в двух следующих случаях:

•    w является составным узлом T(v), хранящим ключ к\

•          w является простым узлом Г(у), все составные узлы T(v), предшествующие w при симметричном обходе, имеют ключи менее к, а все составные узлы 7T(v), следующие за w при симметричном обходе, имеют ключи более к.

Таким образом, метод findElement(A:) может выполняться в словаре D при вызове метода TreeSearch(A:,7V.root()) в Т. Пусть w будет узлом Г, возвращаемым вызовом метода TreeSearch. Если узел w составной, то возвращается элемент, хранящийся в w; в противном случае возвращается NO_SUCH_KEY.

Алгоритм TreeSearch(A:,v):

Input: ключ поиска к и узел v бинарного дерева поиска Т.

Output: узел w ветви T(v) дерева Т\ корнем которого является узел v, при этом w либо составной узел, хранящий ключ к, либо простой узел, которому мог принадлежать объект с ключом к, если бы он существовал.

if v есть внешний узел then

return v if к = key(i/) then

return v else if к < key(v) then

return TreeSearch (k, 7".leftChild(v)) else

{при к > key(v)}

return TreeSearch(/c, T.rightChild(v)) Фрагмент кода 9.1. Рекурсивный проход бинарного поискового дерева

Анализ поиска в бинарном дереве

Анализ времени выполнения поиска в бинарном дереве Т выглядит достаточно просто. Рекурсивный алгоритм TreeSearch выполняет постоянное количество простейших операций для каждого рекурсивного вызова, выполняемого над дочерним элементом предыдущего узла. То есть TreeSearch вызывается к узлам маршрута дерева Г, начинающегося из корня и опускающегося каждый раз на один уровень. Таким образом, количество таких узлов ограничено чйслом h + 1, где h — высота Т. Другими словами, поскольку на каждый узел затрачивается 0(1) времени, метод findElement словаря D выполняется за 0(h) времени, где h — высота бинарного поискового дерева Т\ используемого для реализации /)(рис. 9.3).

Можно показать, что другой вариант этого алгоритма выполняет операции findAllElements(A:) за время 0(А + $), где s — количество элементов в возвращаемом итераторе. Тем не менее анализ данного метода несколько сложнее, а его детали оставлены для решения читателем в упражнении 3-9.1.

Естественно, и высота h дерева Г, и количество узлов п в дереве могут быть одинаково велики. Однако будем исходить из того, что обычно высота невелика. В разделе 9.2 показано, как поддерживать уровень верхней границы высоты поискового дерева Травным 0(log п). Прежде чем привести эту схему, опишем способы реализации методов обновления словаря.

Рис. 9.3. Время выполнения поиска в бинарном поисковом дереве. На рисунке используются стандартные сокращения представления дерева в виде треугольника и маршрута из корня в виде зигзагообразной линии

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

Бинарные поисковые деревья предоставляют возможность реализации операций insertltem и removeElement с помощью достаточно простых, но не тривиальных алгоритмов.

Ввод

Для выполнения операции insertltem(/;,e) в словаре D, реализованном бинарным поисковым деревом Г, вызовем метод TreeSearch(&,r.root()). Пусть w будет узлом, возвращаемым методом TreeSearch.

•          Если w — простой узел (не содержащий объекта с ключом к), то он замещается новым составным узлом и>, хранящим объект (к,е)ч и двумя простыми дочерними элементами с помощью операции expandExternal(w) (см. п. 6.3.1). Заметим, что w вполне уместен для ввода объекта с ключом к.

•          Если w — составной узел (там хранится другой объект с ключом к), то вызывается TreeSearch(^rightChild(>v)) (или, соответственно, TreeSearch(?,teftChild(>v))), и алгоритм рекурсивно применяется к узлу, возвращаемому методом TreeSearch.

Приведенный выше алгоритм последовательно проходит маршрут от корня Г вниз к простому узлу, который замещается новым составным узлом, содержащим новый объект. Следовательно, ввод добавляет новый элемент в нижний уровень поискового дерева Т. Пример ввода в бинарное поисковое дерево приведен на рис. 9.4.

Рис. 9.4. Ввод объекта с ключом 78 в поисковое дерево рис. 9.2: (а) поиск позиции для ввода; (Ь) полученное в результате дерево

Анализ алгоритма ввода аналогичен анализу алгоритма поиска. Количество пройденных узлов в максимальном случае соответствует высоте h дерева Т. К тому же, исходя из реализации Т связной структурой (см. п. 6.4.2), на обращение к каждому узлу требуется 0(1) времени. Таким образом, метод insertltem выполняется за 0(h) времени.

Удаление

Реализация операции removeElement(A;) в словаре D, реализованном бинарным поисковым деревом Г, несколько сложнее, поскольку следует избавляться от лишних «дыр» в дереве Т. Операция начинается достаточно просто выполнением алгоритма TreeSearch(A;, r.root()) в дереве Т для поиска узла, хранящего ключ к. Если TreeSearch возвращает простой узел, это означает отсутствие объекта с ключом к в словаре D, то есть возвращается специальный элемент NO_SUCH_KEY, работа завершается. Если же TreeSearch возвращает составной узел и>, то это означает наличие в нем предназначенного для удаления объекта.

При этом возможны два варианта (по уровню сложности):

Рис. 9.5. Удаление из бинарного поискового дерева (рис. 9.4, Ь), где валяемый ключ 32 хранится в узле w, имеющем простые дочерние элементы: (а) до удаления; (Ь) после удаления

? находится первый составной узел у, следующий сразу за w при симметричном проходе Т. Узел у — самый левый составной узел в правой ветви w, и он отыскивается, начиная от правого дочернего элемента w, затем вниз по Г (по левой ветви поддерева). Левый дочерний элемент х узла у также является простым узлом, следующим сразу за w при симметричном проходе Т\

Рис. 9.6. Удаление из бинарного поискового дерева (рис. 9.4, Ь), где удаляемый ключ 65 хранится в узле, имеющем два составных дочерних элемента: (а) до удаления; (Ь) после удаления

?         сохраняем элемент, находящийся в w, во временной переменной t и переносим объект из у в w. В результате такого действия бывший в w объект удаляется;

?         удаляем узлы х и у из Тс помощью операции removeAboveExternal(x). В результате у замещается на соседний узел х, и х и у (оба) удаляются из Г;

?         возвращаем элемент, ранее хранившийся в w и сохраненный во временной переменной t.

Анализ алгоритма удаления аналогичен анализу алгоритма ввода и поиска. На обход каждого узла затрачивается 0(1) времени, и, в крайнем случае, количество пройденных узлов соответствует высоте h дерева Т. Таким образом, в словаре D, реализованном бинарным поисковым деревом Г, метод removeElement выполняется за 0(h) времени, где h — высота Т.

Очень просто можно показать, что любой из вариантов данного алгоритма выполняет операцию removeAllElements(к) за время 0(h + s), где s — количество элементов в возвращаемом итераторе. Подробности оставлены для упражнения 3-9.2.

Сравнение лучшего и худшего вариантов

Рис. 9.7. Пример бинарного поискового дерева с линейной высотой, полученной в результате ввода ключей в возрастающем порядке

Бинарное поисковое дерево Т представляет вполне приемлемую реализацию упорядоченного словаря с количеством элементов п, но при условии, что его высота будет сравнительно небольшой. В лучшем случае высота h дерева Тбудет иметь размер h = Tlog^+l)], что соответствует логарифмическому времени выполнения для всех словарных операций. Однако в худшем случае Т будет иметь высоту п. Следовательно, дерево будет выглядеть и вести себя как упорядоченная последовательность. Такая ситуация может возникнуть в результате, например, ввода набора ключей в возрастающем или убывающем порядке (см. рис. 9.7).

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

По теме:

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