43964

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

Доклад

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

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

Русский

2014-03-31

17.8 KB

14 чел.

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

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

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

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

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

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

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

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

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


 

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

59420. Рідна мова - краю батьківського пісня 42.5 KB
  Рідна мова Рідна мова Що в єдине нас злива Перша пісня колискова. 3й учень: В кому думка прагне слова Хто в майбутнім хоче жить Той всім серцем закричить: В рідній школі рідна мова В рідній школі рідна мова...
59421. Свято української писанки 48.5 KB
  Церква пристосувала язичний культ писанки як знака сонця і оновлення життя і ввела його у свято Великодня як символ Христового воскресіння. 1 ведуча: Існує багато легенд про писанки і крашанки. Наші предки вірили у чарівну силу писанки і крашанки.
59422. Сценарій лялькового спектаклю: Сигареті – ні! 31.5 KB
  Дія ІІВедучий: Хто стрибає так завзято Це ж бо зайчики-близнята. Один зайчик тікає а другий підходить до Лисички Зайчик: Ти лисичко все торгуєш І без діла не сумуєш Лисичка: Так Ведучий: Йому лисичка каже Лисичка: В магазині я на стражі. Дія ІІІ Ведучий: В магазинчик лісовий Іде Півник молодий.
59423. Сценарій свята присвяченого Дню літньої людини 37 KB
  Виходять ведуча з дівчинкою у дівчинки в руках червона троянда. Коли восени раптом наступає весна а взимку розпускаються троянди бере троянду в дівчинки символ вірності й любові ДІВЧИНКА: А коли ж таке трапляється ВЕДУЧА: Таке трапляється копи людина любить.
59424. Нестандартний урок-гра з геометрії у 5 класі “Турнiр допитливих” 281 KB
  Журі рахує бали або в цілому оцінює виступ в кожному з турів для команди а також для найбільш активних учасників змагання якщо зрозуміло що конкретні бали зароблені для команди одним із учасників то для нього відкривається особистий рахунок до якого бали додаються протягом гри....
59425. Cценарій: Дорога і діти 40.5 KB
  Правила руху в нашій країні Для пішоходів усюди єдині Знати добре їх всі повинні: І дівчатка і хлопятка І зайці і тигренятка А також дорослі люди От тоді порядок буде. Всім місця вистачить.
59426. СВЯТО-КОНКУРС: МІС РОСИНКА 41.5 KB
  Доброго дня шановні пані та панове Ведуча 2: Раді бачити вас при доброму здоров та гарному настрої Ведуча 1: Весна уквітчана духмяна принесла свято у садок. Ведуча 2: На свято Міс Росинка зібрались ці дівчатка. Ведуча 1: Бо кожна з них у групі пройшла всі перешкоди щоб стати Міс росинка й дістати нагороди.
59427. Українські вечорниці “Пісенне село” 1.78 MB
  Святково прибрана світлиця. В кутку — макет сільської хати з соломяною стріхою, пліт, лавочка, на якій сидить бабуся, виготовлені мальви, соняшники, на плоті висять глечики.
59428. Нашому роду – нема переводу 45.5 KB
  Сумна, трагічна історія нашої землі, нашої України. Скільки разів топтали нашу землю чоботи чужинців, скільки разів червоніла вона від крові і промокала від сліз! Україна! Європейські правителі мали за честь одружуватися з українками.