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

0

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

Утверждение 9.1. Бинарное поисковое дерево Т высотой h для п объектов «ключ-элемент» требует О(п) места и выполняет операции АТД «словарь» за следующее время:

•       операции size и isEmpty за 0(1) времени;

•       операции findElement, insertltem и removeElement каждая за 0(h) времени;

•                  операции findAIIEIements и removeAIIEIements каждая за 0(h + s) времени, где я — размер возвращаемого итератора.

Метод

Время

size, isEmpty

findElement, insertltem, removeElement findAIIEIements, removeAIIEIements

0(1) 0(h) 0(h + s)

Таблица 9.1. Время выполнения основных методов бинарного поискового дерева. Текущая высота дерева обозначена А, размер возвращаемого методами findAIIEIements и removeAIIEIements итератора — s. Занимаемое пространство составляет 0(п), где п — количество хранящихся в словаре объектов

Сравнение операций поиска и обновления показывает значительные отличия времени их выполнения в зависимости от высоты дерева. Однако в среднем бинарное поисковое дерево с п ключами и произвольным количеством их ввода й удаЛешя Ймеет предполагаемую высоту 0(log п).

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

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

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

По теме:

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