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

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


 

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

25833. Аудит учета затрат, включаемых в себестоимость продукции (работ, услуг) 40.5 KB
  Себестоимость продукции один из показателей эффективности производства выявляющий во что обходится организации изготовление и сбыт продукции. Себестоимость широко применяется для экономического обоснования решений о производстве новой или прекращении выпуска старой продукции; для определения эффективности мероприятий научнотехнического прогресса рентабельности продукции резервов снижения затрат и др. Все затраты организации на производство определяют производственную себестоимость продукции.
25834. Проверка правильности определения налогооблагаемой базы 50.5 KB
  Проверяется правильность определения имущества не облагаемого налогом Проверяется соответствие ставки используемой банком установленной законодательством Проверка правильности исчисления налога на имущество исходя из ставки и налоговой базы. Не признаются налогоплательщиками организации являющиеся организаторами Олимпийских игр и Паралимпийских игр в соответствии со статьей 3 Федерального закона Об организации и о проведении XXII Олимпийских зимних игр и XI Паралимпийских зимних игр 2014 года в городе Сочи развитии города Сочи как...
25835. Структура и свойства конструкционных сплавов цветных металлов 973.5 KB
  Микроструктура металла (от микро... и лат. structura — строение), строение металла, выявляемое с помощью микроскопа (оптического или электронного). Микроскоп для исследования металла впервые применил П. П. Аносов (1831) при изучении булатной стали. Металлы и сплавы состоят из большого числа кристаллов неправильной формы (зёрен)
25836. Сплавы цветных металлов, обрабатываемые давлением 319.5 KB
  К цветным металлам и сплавам относятся практически все металлы и сплавы, за исключением железа и его сплавов, образующих группу чёрных металлов. Цветные металлы встречаются реже, чем железо и часто их добыча стоит значительно дороже, чем добыча железа. Однако цветные металлы часто обладают такими свойствами, какие у железа не обнаруживаются, и это оправдывает их применение.
25837. Аудит операций на расчетном, валютном и других счетах банка 37.5 KB
  Целью аудиторской проверки операций по расчетному валютному и других счетам в банке является формирование мнения о достоверности бухгалтерской отчетности по разделу Денежные средства и соответствии применяемой методики учета денежных средств на счетах в банке действующим в Российской Федерации нормативным документам. Аудитор при проверке операций по счетам в банке должен учитывать основные нормативные документы регулирующие порядок проведения операций на расчетном валютном и других счетах в банках и бухгалтерский учет этих операций....
25838. Аудит прочих доходов и расходов 58.5 KB
  Целью аудиторской проверки прочих доходов и расходов является формирование мнения о правильности учета прочих доходов и расходов. Задача аудиторской проверки прочих доходов и расходов состоит из следующих вопросов на которые должен ответить аудитор: Бухгалтерский учет прочих доходов и расходов соответствует положениям нормативных актов Данные аналитического и синтетического учета по счету 91 Прочие доходы и расходы соответствуют данным главной книги и баланса Корреспонденция счетов по счету 91 Прочие доходы и расходы составлена в...
25839. Учет расчетов по авансам выданным и полученным 36.5 KB
  Согласно положениям Плана счетов Инструкции по применению Плана счетов бухгалтерский учет сумм полученных и или выданных авансов организуется на балансовых счетах связанных с расчетами за отгруженную продукцию выполненные работы оказанные услуги. Для учета сумм авансовых платежей предварительной оплаты к балансовым счетам открываются обособленные субсчета учета. В частности суммы выданных поставщикам и подрядчикам авансов учитываются обособленно на балансовом счете 60 Расчеты с поставщиками и подрядчиками суммы полученных...
25840. Аудит расчетов по авансам выданным 27.5 KB
  Так например выдавая авансы поставщику предприятие изымает из оборота денежные средства до момента поступления ТМЦ выполнения работ оказания услуг также возрастает вероятность непоступления данных ценностей на предприятие вопреки договору поставки. На счете 61 €œРасчеты по авансам выданным€ обобщается информация о расчетах по выданным авансам под поставку продукции либо под выполнение работ а также по оплате продукции и работ принятых от заказчиков по частичной готовности. Суммы выданных авансов а также произведенной оплаты и работ...
25841. Аудит расчетов по претензиям 30 KB
  Можно выделить несколько видов претензий: при выявлении ошибок в счетах поставщиков неправильно указаны тарифы и цены арифметические ошибки и др. Аудитору необходимо проверить: обоснованность своевременность и правильность оформления документов несоблюдение сроков предъявления претензий может быть использовано для сокрытия фактов хищения материальных ценностей так как при отказе в удовлетворении претензий числящиеся суммы списываются на издержки производства; обоснованность претензий предъявляемых к проверяемому предприятию в случае...