43964

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

Доклад

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

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

Русский

2014-03-31

17.8 KB

13 чел.

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

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

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

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

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

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

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

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

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


 

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

22740. Канада і НАФТА 44 KB
  Канада і НАФТА. Североамериканскиое соглашение о свободной торговле НАФТА между Канадой Соединенными Штатами Америки и Мексикой вступило в силу 1 января 1994 года. Созданное для поощрения увеличения торговли и инвестиций между партнерами по НАФТА Соглашение содержит грандиозный план уничтожения тарифов и сокращения нетарифных барьеров наряду с обстоятельными положениями по ведению бизнеса в зоне свбодной торговли. НАФТА увеличила доступ Канады на американский и мексиканский рынки а также повысила привлекательность канадской экономики для...
22741. Латиноамериканський курс адміністрації Дж. Картера 23.5 KB
  Планы укрепления агрессивной межамериканской военной системы консолидации правых режимов на континенте были приняты на вооружение и администрацией США во главе с Дж. Столкнувшись с падением престижа США в Латинской Америке и стремясь укрепить здесь свои позиции официальный Вашингтон возвестил о пересмотре политики в отношении латиноамериканских государств. Дипломатия США стала усиленно афишировать свой постоянный интерес к этим странам. Президент США Дж.
22742. Етапи війни США у Кореї 82 KB
  Етапи війни США у Кореї. Поэтому сейчас взрывы в Японии рассматривались как начало атомного шантажа США. Эта ошибка в переоценке своих сил вынудили США заплатить за нее очень дорого сначала в Корее а затем во Вьетнаме. Дело состояло в следующем: СССР допустив США в Корею справедливо считала что американцы в свою очередь выделят СССР зону оккупации в Японии.
22743. Основні напрямки зовнішньої політики США на початку 70-х рр 31 KB
  Зайнявши Білий дім 37й американський президент уже в липні 1969 року проголосив нову стратегію США у в'єтнамській війні яка отримала назву доктрини Ніксона . Вже в червні 1969 року почалася евакуація півмільйонного американського контингенту з Південного В'єтнаму. На травень 1972 року тут залишалось 69 тисяч американців. на думку деяких істориків змусило Ханой підписати у Парижі 27 січня 1973 року угоду про припинення військових дій та відновлення миру у В'єтнамі .
22744. Посилення холодної війни США проти соціалістичних країн у період першого президентства Д. Ейзенхауера 31 KB
  Посилення холодної війни США проти соціалістичних країн у період першого президентства Д. Они пожинали плоды послевоенного экономического подъема когда материальное благополучие США еще больше возросло. В 60е годы политизированное студенчество выступило против международной роли США особенно в разрушительной войне во Вьетнаме. Сама жизнь подводила граждан США к поискам нового социального равновесия в стране.
22745. Африканська політика адміністрації Дж. Картера 26.5 KB
  Киссинджер пытались наладить отношения с будущими партнёрами национальноосвободительными силами на юге Африки которые стремились расширить круг своих сторонников на международной арене использовать противоречия международного сообщества с Южной Родезией ЮАР и с колониальными властями Португальской Африки. В частности во время поездки по странам Африки в апрелемае 1976г. Киссинджера в ходе его поездки по странам Африки как прямое указание к действиям. Весомым практическим результатом этой политики для Африки стали посреднические усилия...
22746. Умисел як форма вини 128.5 KB
  Вина - це завжди умисел або необережність. Лише за наявності вини особи щодо вчиненої нею дії (бездіяльності) можна говорити про склад злочину як підставу кримінальної відповідальності.
22747. Доктрина Ейзенхауера 22 KB
  €œДоктрина Ейзенхауера€. У боротьбі за крісло у Білому домі Дуайт Ейзенхауер використав нову зовнішньополітичну доктрину замінивши політику стримування політикою відкидання звільнення ' від комунізму її теоретиком був Дж.Кеннана що у зовнішніх справах Ейзенхауер був людиною гострого політичного розуму і передбачуваності. Президент зазнав нищівної критики військові вимагали збільшення фінансування на звичайні озброєння але Ейзенхауер вистояв.
22748. Політика США щодо СРСР у першій половині 80-х рр 27.5 KB
  Політика США щодо СРСР у першій половині 80х рр. У зовнішньополітичній діяльності президента Рейгана варто розрізнити два періоди відповідно до термінів президентства: 19811984 рокичас різкої конфронтації з СРСР курсу на військову перевагу США у світі домінування силових методів у розв'язанні міжнародних конфліктів дії доктрини Рейгана доктрини неоглобалізму тобто протистояння з СРСР у будьякому куточку планети; 19851989 рокиперіод пошуку шляхів для виходу із політики глобального протистояння з СРСР нормалізації...