43964

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

Доклад

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

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

Русский

2014-03-31

17.8 KB

12 чел.

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

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

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

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

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

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

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

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

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


 

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

44501. Визначений інтеграл та його застосування 3.14 MB
  Значний внесок у розв’язання проблеми про площу круга зробив видатний грецький математик IV ст. до н.е. Євдокс Книдський. Він вписував в круг правильний многокутник, а потім доводив, що за рахунок збільшення кількості сторін многокутника (відповідно зменшенням їх довжин) можна добитися того
44502. НАЦІОНАЛЬНА ЕКОНОМІКА 432.5 KB
  Метою практикуму є оволодіння знаннями та навичками практичних розрахунків, що здійснюють державні органи управління в процесі обґрунтування заходів державного втручання в економіку та особисто в діяльність окремих підприємницьких структур.
44503. Самай сүйек өзектері, олардың маңызы 15.31 KB
  Гуманисты были творцами новой системы знания в центре которого стояла проблема человека его земного предназначения термин humnist полагает П. Мишле выдвинул принципиально отличное от средневекового решения проблемы отношения человека к миру. Бурдаха где он писал что новое понимание искусства литературы науки новая концепция человека не вступали в противоречие в христианской религией ибо были предопределены ее пышным цветением в XIII в. Наиболее значительной для Тоффанина была идея божественности человека.
44504. Дабыл қуысы, қабырғалары, құрамы, қатынастары, отит кезіндегі асқынулар 16.68 KB
  Отит-құлақтың қабынуы. қөбіне ортаңғы құлақтың қабыну кездеседі-лабиринтит. Ортаңғы отит қоздырғышы кокктар-пнвмококк, стафилококк, гемофильді таяқшалар. Көбіне жоғары тыныс алу жолдарының асқынуларынан кейн п. б
44505. Көзұясы, қабырғаларының құрылысы, тесіктері, олардың маңызы 15.81 KB
  Начинается серия войн с Византией велись они с переменным успехом но в целом удачно для Болгарии. престиж Болгарии как международной державы был высок. Послов Болгарии за императорским столом сажали выше чем послов германского императора Оттона I. в Болгарии появилось богомильское движение дуализм.
44506. Қанат-таңдай шұңқыры, оның қабырғалары, тесіктері, қатынастары. Самай шұңқыры. Самайасты шұңқыры 15.81 KB
  Медиальды қабырғасы-төбе сүйегінің сыртқы бетінің сыналық бұрышының маңындағы төменгң бөлігінен, самай сүйектің қабықшалы бөлгінің сыртқы бетінен, сына сүйектің улкен қанатының саай шұңқырына қараған бетінен құралған
44507. Ми сауыты негізінің сыртқы беткейі 16.56 KB
  Шүйде сүйегі-os occipitale, ми саутының артқы қапталында орн. сыртқа беті-дөңестеу, ішкі беті-ойыстау келген тақ сүйек. Шүйде сүйектің артқы жағында ми сауытын омыртқа өзекшесімен жалғастырушы шүйделік үлкен тесік-foramen magnum, бүйір қапталында сигма тәрізді қойнаудың жүлгесі-sulcus sinus sigmoideus, орналасқан.
44508. Ми сауыты негізінің ішкі беткейі, тесіктері, маңызы 16.32 KB
  Түрік ершігінің бүйір бөлігінде-нервтік өрім жүлгесі-sulcus coroticus, орн. алд немесе мұрын қуысына қараған бетінде-сына сүйек қырқасы-crista sphenoidalis, ол кеңсірік сүйегінің қанатымен-ala vomeris, беттесіп кеңсірік-ілмектік өзекшені-canalis vomeroorastralis, құрайды. Сына сүйек қойнауы-sinus sphenoidalis
44509. Биотехнические системы 5.73 MB
  Биотехнические системы – особый класс больших систем, в которых биологические и технические элементы связаны в едином контуре управления, причем роль управляющего звена в них могут играть как технические, так и биологические звенья. Создание таких систем является сложной задачей, использующей целый арсенал отдельных приемов, методов и подходов