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

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


 

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

46549. ТЕХНОЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕ АТП НА АВТОМОБИЛЕЙ 1.67 MB
  Важнейшими направлениями в проектировании должны быть типизация проектных решений на базе унификации объемно-планировочных решений, а также широкое применение типовых проектов. В целях сокращения трудоемкости и сроков проектирования, повышения экономичности проектных решений,
46550. Общая характеристика ФЗ "об окружающей среде" 19.85 KB
  Общая характеристика ФЗ об окружающей среде Определенный комплекс мер соответствующий законодательным нормам и принципам предназначенный для ограничения отрицательного влияния деятельности человека на природу называется охрана окружающей среды или в научной сфере прикладной экологией. Стоит отметить что проблема загрязнения окружающей среды несмотря на серьезную борьбу с ней с каждым днем становится все сильней Законодательная база в сфере охраны окружающей среды весьма широка. В отличие от осуществления деятельности в области...
46551. Система планов на предприятии и их взаимосвязь 41 KB
  ехнико-экономическое планирование предусматривает разработку целостной системы показателей развития техники и экономики предприятия в их единстве и взаимозависимости как по месту, так и по времени действия. В ходе данного этапа планирования обосновываются оптимальные объемы производства на основе учета взаимодействия спроса и предложения на продукцию и услуги
46552. Основные закономерности изнашивания. Работоспособность деталей и узлов машин 19.89 KB
  Виды изнашивания в машинах Механическое изнашивание изнашивание в результате механических воздействий. Абразивное изнашивание механическое изнашивание материала в результате режущего или царапающего действия твердых тел или частиц. Абразивная эрозия гидро и газоабразивное изнашивание основной вид изнашивания деталей насосов трубопроводов арматуры дымососов вентиляторов эжекторов пескоструйныхаппаратов в результате воздействия твердых тел или частиц увлекаемых потоком жидкости или газа. Усталостное изнашивание часто является...
46553. Смазочные материалы. Назначение. Классификация. Основные параметры и свойства смазочных материалов 22.23 KB
  Полутвёрдыми полужидкими расплавленные металлы солидолы консталины и др жидкими автомобильные и другие машинные масла газообразными углекислый газ азот инертные газы. Растительные масла получают путем переработки семян определенных растений. животные масла вырабатывают из животных жиров баранье и говяжье сало технический рыбий жир костное и спермацетовые масла и др. органические масла по сравнению с нефтяными обладают более высокими смазывающими свойствами и более низкой термической устойчивостью.
46554. THE ADVERB 19.95 KB
  The adverb is a word denoting circumstances or characteristics which attend or modify an action, state, or quality. It may also intensify a quality or characteristics From this definition it is difficult to define dverbs s clss becuse they comprise most heterogeneous group of words nd there is considerble overlp between the clss nd other word clsses. longside such undoubtful dverbs s here now often seldom lwys there re mny others which lso function s words of other clsses. Thus dverbs like ded ded tired cler to get cler wy clen I've clen forgotten slow esy he would sy tht slow nd esy coincide with corresponding djectives ded body cler wters clen hnds. dverbs like pst bove re...
46555. Система Управления БД 19.99 KB
  БД это именованная совокупность данных отражающая состояние объектов и их отношений в заданной предметной области. Банк данных является современной формой организации хранения и доступа к информации. Банк данных это система специальным образом организованных данных баз данных программных технических языковых организационнометодических средств предназначенных для обеспечения централизованного накопления и коллективного многоцелевого использования данных. Банк данных является сложной системой включающей в себя все обеспечивающие...
46556. Затратный подход к оценке предприятия 20.02 KB
  Суть данного подхода заключается в том что сначала оцениваются и суммируются все активы предприятия нематериальные активы здания машины оборудование запасы дебиторская задолженность финансовые вложения и т. Далее из полученной суммы вычитают текущую стоимость обязательств предприятия. Итоговая величина показывает стоимость собственного капитала предприятия.