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

0

Результаты анализа производительности AVL-дерева выглядят следующим образом. Операции findElement, insertltem и removeElement проходят узлы на пути от корня к листу, добавляя, возможно, и их соседние узлы, и затрачивают на каждый узел 0(1) времени. Таким образом, поскольку высота Г составляет 0(log п), и в соответствии с утверждением 9.2, каждая из этих операций занимает 0(log ri) времени. Детали реализации и анализа операций findAHElements и removeAllElements интересны как упражнения. В табл. 9.2 сведены показатели словаря, реализованного с помощью AVL-дерева. Иллюстрация производительности приводится на рис. 9.12.

Операции

Время

size, isEmpty

findElement, insertltem, removeElement findAHElements, removeAllElements

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

Таблица 9.2. Производительность «-элементного словаря, реализованного AVL-дере- вом, где s — размер возвращаемых методами findAHElements и removeAllElements итераторов. Занимаемое место есть 0(п)

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

По теме:

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