43964

AVL дерево как инструмент повышения эффективности поиска. Оценки сложности поиска

Доклад

Информатика, кибернетика и программирование

Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале разумно сбалансированное дерево имеет высоту порядка O(log2n)...

Русский

2014-03-31

17.8 KB

11 чел.

AVL дерево как инструмент повышения эффективности поиска. Оценки сложности поиска

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.

Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале разумно сбалансированное дерево имеет высоту порядка O(log2n). Однако при некотором стечении обстоятельств дерево может оказаться вырожденным. Тогда высота его будет O(n), и доступ к данным существенно замедлится.

Разница во времени доступа будет гораздо заметнее при большем числе узлов. Например, в идеально сбалансированном дереве из 1023 узлов время доступа в худшем случае будет равно 10 единицам времени, в среднем: единицам времени.

А в вырожденном дереве из 1023 узлов потребуется в худшем случае 1023 единицы времени, в среднем - 512 единиц времени. Поэтому при работе с деревьями поиска больших размеров крайне желательно, чтобы они были близки к сбалансированным.

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

Для AVL-дерева не существует наихудшего случая, так как оно является почти полным бинарным деревом. Сложность операции поиска составляет O(log2n). Опыт показывает, что повороты требуются примерно в половине случаев вставок и удалений. Сложность балансировки обусловливает применение AVL-деревьев только там, где поиск является доминирующей операцией.

Очевидно, что операции вставки и удаления (а также более простая операция поиска) выполняются за время пропорциональное высоте дерева, т.к. в процессе выполнения этих операций производится спуск из корня к заданному узлу, и на каждом уровне выполняется некоторое фиксированное число действий. А в силу того, что АВЛ-дерево является сбалансированным, его высота зависит логарифмически от числа узлов. Таким образом, время выполнения всех трех базовых операций гарантированно логарифмически зависит от числа узлов дерева.


 

А также другие работы, которые могут Вас заинтересовать

65141. Новое в изучении Новгород-северских подражаний джучидским дирхемам третей четверти XIV века 104.5 KB
  Целью настоящей работы является поиск критериев надежного определения монет – подражаний денгам Мухаммеда Буляка (чекан Орды 772,773 и 777 годы хиджры), чеканенных на территории Новгород-Северского княжества в 1370-1380-е годы.
65142. НОВЫЙ ТИП СЕРЕБРЯНЫХ МОНЕТ УЗБЕКА, ЧЕКАНЕННЫХ В БУЛГАРЕ 53.5 KB
  Хромов 25 октября 2001 года Обрабатывая анонимные и анэпиграфные монеты 13 века из Волжско-Булгарского региона мной было обнаружено две серебряные монеты дирхемы неопубликованного ранее типа.
65143. О монетной чеканке на территории Киевского княжества в 50-е годы XIV века («киевские» подражания монетам Джанибека) 154 KB
  астоящий доклад является доработанным вариантом авторского доклада на XII Всероссийской нумизматической конференции. Более подробная разбивка типов монет на варианты стала возможным благодаря новым находкам публикуемых монет. Цифра в скобках указывает на порядковый номер монеты в весовой шкале для варианта, поэтому с добавлением новых монет до выхода их полного Каталога может изменяться
65144. Ранний монгольский доспех (IX – первая половина XIV в.) 916 KB
  Ранний монгольский доспех IX первая половина XIV в. Доспех монголов создавших в XIII первой половине XIV в. Хотя два свитка отнюдь не современники Ляо копия из музея Метрополитэн в Нью Йорке датируется XIV в. По вещественным и изобразительным источникам мы используем копию XIV в.
65145. Рыцарские доспехи XIV века из Азова 277.5 KB
  В 1979 г. в Азове при раскопках жилища золотоордынского времени, погибшего в результате пожара, был обнаружен компактной массой комплект железных предметов, составлявших защитные доспехи воина, и снаряжение его коня.
65146. ЗАЩИТНОЕ ВООРУЖЕНИЕ СТЕПНОЙ ЗОНЫ ЕВРАЗИИ И ПРИМЫКАЮЩИХ К НЕЙ ТЕРРИТОРИЙ В I ТЫСЯЧЕЛЕТИИ НАШЕЙ ЭРЫ 624.5 KB
  Наиболее масштабные работы по интересующей теме принадлежат, пожалуй, О. Гамберу, и Ю. С. Худякову, хотя исследователи являют полную противоположность друг другу. Маститый венский оружиевед строит свои выводы на основании широчайшего обзора материалов: с территории от Британии до Японии...
65147. Куликовская битва 1380 год. Русский и золотоордынский воины 610.5 KB
  Куликовская битва — одно из важнейших событий в средневековой отечественной истории — сыграла серьезную роль в процессе освобождения Руси от татаро-монгольского ига, в процессе консолидации русских государств-княжеств вокруг одного из них...
65148. Загадочная война Субэдэя с русскими 95.5 KB
  Это с одной стороны а с другой что за загадочные Тулисыгэ русский город и Елебань владетель или господин племени русских Попытавшись прояснить вопрос во втором жизнеописании Субэдэя в Юань ши их по ошибке оказалось два созданных разными...
65149. О ДАТАХ ЖИЗНИ ЧИНГИСХАНА 112 KB
  Если относительно смерти Чингисхана существует общепринятая дата август 1227 года которая подтверждена всеми основными источниками то относительно его рождения до сих пор нет такого согласия ни в источниках ни в исследованиях ни в официозе.