53486

Процедура правого поворота для AVL дерева и ее особенности

Доклад

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

В 1962 году советские математики Адельсон-Вельский Г.М. и Ландис Е.А. предложили метод балансировки, требующий после включения или исключения узла лишь локальные изменения вдоль пути от корня к данному узлу, то есть времени не более O(log2n)

Русский

2014-04-01

41.46 KB

0 чел.

Процедура правого поворота для AVL дерева и ее особенности.

В 1962 году советские математики Адельсон-Вельский Г.М. и Ландис Е.А. предложили метод балансировки, требующий после включения или исключения узла лишь локальные изменения вдоль пути от корня к данному узлу, то есть времени не более O(log2n). При этом деревьям разрешается отклоняться от идеальной сбалансированности, но в небольшой степени, чтобы среднее время доступа к узлам было лишь немногим больше, чем в идеально сбалансированном дереве. Такие деревья называются АВЛ-деревьями.

Критерий сбалансированности АВЛ-дерева. Дерево называется сбалансированным тогда и только тогда, когда для каждого его узла высоты его левого и правого поддеревьев отличаются не более чем на единицу.

Примеры АВЛ-сбалансированных деревьев:

Примеры деревьев, не являющихся АВЛ-сбалансированными:Уровень 0

Балансировка выполняется с помощью действий, называемых поворотами узлов. Рассмотрим алгоритмы поворотов, используя указатели p, p1, p2 и считая, что p указывает на узел с нарушенной балансировкой.

Одинарный RR-поворот. Выполняется, когда <перевес> идет по пути R-R от узла с нарушенной балансировкой.

Двойной RL-поворот. Выполняется, когда <перевес> идет по пути R-L от узла с нарушенной балансировкой.

При включении узлов повороты выполняются для ближайшего узла к включенному с нарушенной балансировкой. То есть если после включения узла в дереве образуется несколько узлов с нарушенной балансировкой, поворот выполняется для того, который находится ниже (то есть ближе к включенному). После балансировки этого узла восстанавливается баланс и выше расположенных узлов.


 

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

66209. ВИХОВАННЯ І ШКОЛА В ЕПОХУ СЕРЕДНЬОВІЧЧЯ 64.5 KB
  Навчання починали з механічного заучування на латині молитов і 150 псалмів а потім вивчали латинську азбуку читання і письмо. Виникла така форма навчання як учнівство. Найкращим методом навчання вважався пошук найкоротшого шляху досягнення знань.
66210. Технология найма и отбора персонала 79.5 KB
  Цель набора персонала состоит в создании резерва кандидатов на все рабочие места с учетом в том числе и будущих организационных и кадровых изменений увольнений перемещений уходов на пенсию окончаний сроков контрактов изменений направлений...
66211. Модель проектной группы MSF для небольших команд 66 KB
  Задачи ролевых групп Группа Управление программой : управляет процессом разработки с целью получения готового продукта в отведенные сроки; регулирует взаимоотношения и коммуникацию внутри проектной группы; следит за временным графиком проекта и готовит отчетность о его состоянии...
66212. СТАНОВЛЕННЯ І РОЗВИТОК ЗАРУБІЖНОЇ ПЕДАГОГІЧНОЇ НАУКИ І ПРАКТИКИ У 17 – 19 СТОЛІТТЯХ 71 KB
  Вона була незалежна від церкви і держави існувала на пожертвування і високу плату за навчання. Єдиних навчальних планів не було кожна школа складала програму навчання на власний розсуд. Уряди численних німецьких держав ставились вимоги до організації початкових шкіл у містах і селах навчання хлопчиків...
66213. Сущность и основные формы адаптации персонала 54.5 KB
  Организация процесса адаптации Понятие цели и основные направления адаптации После заключения трудового контракта человек приступает к выполнению трудовых обязанностей. При этом человек проходит через период адаптации.
66215. РЕФОРМАТОРСЬКА ПЕДАГОГІКА ЗАРУБІЖНИХ КРАЇН НАПРИКІНЦІ 19 – НА ПОЧАТКУ 20 СТОЛІТТЯ 86.5 KB
  Перед масовою народною школою постало завдання розробити нові форми навчання і виховання з метою підняття рівня освіти. При Феррі 1832-1893 було запроваджено автономію університетів розроблено нові навчальні плани середньої школи в яких більше уваги приділялось вивченню природничих наук...
66216. Деловая оценка персонала в организации 60.5 KB
  Структура процесса требования к проведению аттестации Понятие виды функции оценки персонала Деловая оценка – процесс определения эффективности деятельности сотрудников в ходе реализации задач организации. Объектом аттестации может быть отдельный сотрудник рабочее место соответствие его требованиям...