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

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


 

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

43553. Проект Внутрігосподарського землеустрою СВК „Надія” 236.5 KB
  Ружинський район входить до складу лісостепової зони України, яка характеризується достатньою кількістю опадів, помірною зимою, досить теплим літом. Переважаючі вітри: влітку – південно західні, взимку – східні та південно-східні.
43554. Тепловой расчет конвективной туннельной сушильной установки 3.04 MB
  Выполнить тепловой расчет конвективной туннельной сушильной установки, определить длительность сушки, размеры установки, выбрать вентилятор для подачи наружного воздуха, дымосос и циклон, на основании следующих данных.
43555. Модуль 2ННК-М 402 KB
  Для проведення ГК в свердловину опускають детектор γ-опромінення і електронну схему, яка перетворює зареєстровані γ-кванти в імпульси напруги. В інших типах РК вимірюється штучна радіоактивність,створена в породах джерелом гамма (ГГК) або нейтронного стаціонарного (ННК-НТ), ННК-Т, НГК і імпульсного (ІННК,ІНГК) випромінювання.
43556. Створення приймача амплітудно-модульованих сигналів 4.37 MB
  Вибір та розрахунок вибіркових систем тракту проміжної частоти Склад комплекту: пристрій має самостійне призначення може працювати з підсилювачем звукової частоти;Допоміжне обладнання: блок живлення від мережі змінного струму 220В 50Гц; стандартні зєднання з підсилювачем звукової частоти. Необхідну вибірність по сусідньому каналу отримують в каскаді перетворювача частоти за допомогою або фільтрів зосередженої селекції або пєзоелектричних фільтрів а вибірність по дзеркальному каналу забезпечується вхідним колом.
43557. Проектирование базы данных для Excel и Access 107 KB
  Для Excel: подготовить таблицу и заполнить ее данными с использованием стандартной формы по тематике задания не менее 10 строк в таблице; описать и выполнить в режиме вычислений функции информационной технологии необходимые вычисления фильтрацию данных сортировку данных подведение итогов; разработать схемы алгоритмов реализующих функции информационной технологии и составить соответствующие им коды приложений на языке программирования VB. Для ccess: разработать связанные таблицы; создать...
43558. РАСЧЕТ КАМЕРЫ ПРЕДВАРИТЕЛЬНОГО ОХЛАЖДЕНИЯ УСТАНОВКИ ПРОИЗВОДСТВА ПИГМЕНТНОГО ДИОКСИДА ТИТАНА 244.5 KB
  Техническую двуокись титана получают методом высокотемпературного парофазного гидролиза из очищенного тетрахлорида титана. Полученный диоксид титана охлаждается проходя через камеру предварительного охлаждения трубную камеру циклон и осаждается в бункерах этих аппаратов. Из...
43559. Детали машин. Проектирование привода к конвейеру по схем 413 KB
  Выбор эл. двигателя и кинематический расчет. Расчет ременной передачи. Расчет редуктора. Расчет валов. Расчет элементов корпуса редуктора. Расчет шпоночных соединений. Расчет подшипников. Выбор смазки. Спецификация на редуктор.
43560. Расчет динамических и топливо экономических характеристик автомобиля УАЗ-469 716.5 KB
  Исходные данные курсовой работы Расчет динамических и топливо экономических характеристик автомобиля УАЗ469 Номер варианта 02 Марка автомобиля УАЗ469 Колесная формула 4Х4 Тип двигателя : четырехтактный карбюраторный Дорожные условия эксплуатации автомобиля коэффициент сопротивления качения fk = 006; угол подъема α=20 Технические характеристика автомобиля. № п п Наименование параметра Обозначение Единица измерения Значение параметров 1 Полный вес: на переднюю ось на заднюю ось G G1 G2 кН кН кН 2450 1020 1430 2...
43561. ТЕОРИЯ ТЕЛЕТРАФИКА 2.49 MB
  Постановка задачи Задание на курсовую работу Разработка обобщенной функциональной схемы ЦОВ Определение характеристик ЦОВ Разработка алгоритмов обработки вызовов поступающих на ЦОВ Разработка структурной схемы ЦОВ Разработка сценариев взаимодействия ЦОВ с сетями общего пользования 15 8 Список сокращений и обозначений Список литературы Введение Целью настоящей курсовой работы является получение знаний о принципах функционирования современных центров обслуживания...