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

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


 

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

36572. Структурный тип строка. Основы обработки строк 29 KB
  Основы обработки строк. Строки относятся к важным средствам представления нечисловой информации и обработка строк имеет широкие приложения во многих областях использования нечисловой информации редактирование текстов логический анализ автоматизация перевода распознавание текстов и др. Поскольку строки указанного типа являются разновидностями массива для них можно применять всё что применимо к массивам.
36573. Расчёт электроснабжения района 2.81 MB
  Определение расчетной нагрузки коммунально-бытовых, промышленных потребителей; выбора номинальной мощности трансформаторов; определения сечения линий как высокого, так и низкого напряжения; определения величины недоотпущенной электроэнергии; определения годовых потерь электрической энергии в линии 35 кВ
36574. Структурный тип массив. Обработка массивов 31 KB
  Такие операторы присваивания могут использоваться для копирования одного массива в другой. Однако над массивами не определены отношения. Кроме того, в Турбо Паскале нельзя использовать выражения над массивами.
36575. Структурный тип маcсив. Описание мас и доступ к эл мас 33 KB
  Идея массива состоит в том чтобы объединить в одно целое фиксированное количество элементов одного и того же типа. Общая форма описания массива имеет вид: type имя типамассива = rry [ тип индекса ] of тип элементов ; где: имя типамассива имя выбираемое программистом. тип индекса любой порядковый тип кроме longint или типдиапазон.
36576. Оператор выбора CASE OF 31 KB
  Оператор выбора является обобщением оператора ifthenelse на случай выбора одного из нескольких возможных продолжений выполнения программы. Выбор осуществляется по ключу выбора селектору. Синтаксическая структура этого оператора такова: cse ключ выбора of константа выбора 1 : оператор 1 ; .
36577. Концепция типа данных. простой тип данных 38 KB
  К любому порядковому типу применимы следующие функции: OrdX порядковый номер значения выражения Х этого типа; PredX предыдущее значение выражения Х этого типа; SuccX следующее значение выражения Х этого типа; HighX наибольшее значение диапазона аргумента Х; LowX наименьшее значение диапазона аргумента Х; Функция Ord определена для любого значения порядкового типа причём нумерация значений начинается от номера 0 номера наименьшего значения типа. Функции Pred и Succ не определены соответственно для левой и правой границы...
36578. Концепция типа данных. Тип данных в ТР 29.5 KB
  Тип данных в ТР. Ранее мы познакомились с некоторыми стандартными типами данных: числовыми символьным строковым и булевским. Стандартные типы данных это лишь частный случай общей концепции типа данных Паскаля.
36579. Оператор итерационного цикла ( repeat , while ) 31 KB
  В каждом операторе итерационного цикла будем различать условие и тело цикла повторяющееся действие. Тело цикла whiledo это один оператор записанный после do а для цикла repetuntil тело цикла может быть и последовательностью операторов записанных между repet и until. Если условие есть true выполняется тело цикла и повторно вычисляется значение условия.
36580. Композиция условий и операторов. Оператор условного перехода 32.5 KB
  Оператор условного перехода. Композиция условий и операторов. Простые операторы несмотря на свою важность недостаточны для того чтобы представлять любые алгоритмы задач.