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-деревьев только там, где поиск является доминирующей операцией.

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


 

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

52925. Речовий етикет і загальна культура молодших школярів 9.99 MB
  Виявити, теоретично обґрунтувати педагогічні умови формування базової культури учнів початкової школи й емпірично довести ефективність їх реалізації
52926. Сценарій уроку - гри „Еврика” 60 KB
  Як називається чотирикутник у якого сторони протилежні паралельні 2. Як називається паралелограм у якого всі сторони рівні 6. 7 Як називається паралелограм у якого діагоналі перпендикулярні 8. Як називається відрізок що сполучає протилежні вершини 10.
52928. Сценарій пісенного конкурсу «Євробачення – 2012» 71.5 KB
  Ведучий 1: Увага Увага Починаємо пісенний конкурс гімназійної молоді Євробачення 2012 звучить патетична мелодія Ведучий 2: Дім наш рідний – Україна Ріки гори і озера У Європу несемо ми Жовтосинії знамена. Ведучий 1: Бо є доля в нас єдина...
52929. Донецк -- один из городов-хозяев Евро-2012» для 5 класса 97.5 KB
  Донецк один из городов хозяев Евро 2012 Цель: познакомить детей с Донецком городом где будет проходить Евро 2012 с его историей значимыми местами города выда ющимися людьми Донбасса прославившими родной край Украину; развивать познавательный интерес желание и возможность прославить родной город своими достижениями; ...
52931. Поняття допоміжного алгоритму. Алгоритми-процедури та алгоритми-функції. Створення програм з використанням функцій 12.67 MB
  Алгоритмипроцедури та алгоритмифункції. Мета: навчаюча дати поняття про допоміжні алгоритми типи допоміжних алгоритмів навчити оформлювати підпрограмифункції мовою Паскаль; розвиваюча активізувати пізнавальну діяльність учнів; розвивати логічне мислення; застосовувати набуті знання до розв’язування конкретних завдань; розвивати абстрактне і логічне мислення; виховна виховувати інформаційноосвічену людину; виховувати самостійність в роботі і...
52932. Перспективи входження України до Євросоюзу 66 KB
  Перспективи входження України до Євросоюзу. розкрити місце України у розширенні Євросоюзу. розкрити причини низького рівня розвитку економіки України. показати шляхи економічного розвитку та зростання України.
52933. Поурочні плани для курсу за вибором «Євроклуб» 762 KB
  Виховання учнів здійснюється через систему особистісних стосунків із новою культурою і процесом оволодіння нею. Виховна мета це виховання в учнів: позитивного ставлення до іноземної мови як засобу спілкування; розуміння сучасних інтеграційних процесів та тенденцій; поваги до народу носія цієї мови толерантного ставлення до його культури звичаїв і способу життя; культури спілкування прийнятої в сучасному цивілізованому світі; емоційноціннісного ставлення до всього що нас оточує; розуміння важливості оволодіння іноземною мовою...