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 от узла с нарушенной балансировкой.

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


 

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

15660. БАЗОВЫЕ И СТРАТЕГИЧЕСКИЕ ПРОЦЕССЫ РАСПОЗНАВАНИЯ СЕМАНТИЧЕСКИХ ОТНОШЕНИЙ 193.5 KB
  БАЗОВЫЕ И СТРАТЕГИЧЕСКИЕ ПРОЦЕССЫ РАСПОЗНАВАНИЯ СЕМАНТИЧЕСКИХ ОТНОШЕНИЙ В работе представлены результаты исследования процессов базовой и стратегической организации познавательных процессов на примере задач семантического решения. Испытуемые должны были оцениват
15661. ПСИХОФИЗИОЛОГИЯ. О ЗАВИСИМОСТИ ОБЪЕМА ПАМЯТИ ОТ РАЗМЕРА АЛФАВИТА СТИМУЛОВ 157 KB
  ПСИХОФИЗИОЛОГИЯ. О ЗАВИСИМОСТИ ОБЪЕМА ПАМЯТИ ОТ РАЗМЕРА АЛФАВИТА СТИМУЛОВ В экспериментальном исследовании обнаружено что объем сенсорной памяти на цифры вычисленный по методике частичного отчета равен объему кратковременной памяти измеренному по методике полног
15662. ОБЪЕМ ПАМЯТИ И РАЗМЕР АЛФАВИТА СТИМУЛОВ 100.5 KB
  ОБЪЕМ ПАМЯТИ И РАЗМЕР АЛФАВИТА СТИМУЛОВ Не смотря на многолетнюю историю экспериментальных исследований психология памяти до сих пор остается ареной теоретических споров и столкновения разных концепций. Одной из горячо обсуждаемых проблем является даже то сколько в...
15663. ОНТОЛОГИЯ СПОРТА И ФИЗИЧЕСКОГО ВОСПИТАНИЯ КАК ФЕНОМЕНОВ ЭКЗИСТЕНЦИАЛИСТСКОЙ КУЛЬТУРЫ 91 KB
  ОНТОЛОГИЯ СПОРТА И ФИЗИЧЕСКОГО ВОСПИТАНИЯ КАК ФЕНОМЕНОВ ЭКЗИСТЕНЦИАЛИСТСКОЙ КУЛЬТУРЫ Ибрагимов М.М. Национальный университет физического воспитания и спорта Украины Постановка проблемы. В первую очередь следует отметить что историографический анализ спорта обна...
15664. СОВА МИНЕРВЫ и АПОЛЛОН или ДВА СПОСОБА ФИЛОСОФСКОГО ОСМЫСЛЕНИЯ СПОРТА 124 KB
  СОВА МИНЕРВЫ и АПОЛЛОН или ДВА СПОСОБА ФИЛОСОФСКОГО ОСМЫСЛЕНИЯ СПОРТА Аннотация: В статье Сова Минервы и Аполлон или два способа философского осмысления спорта кандидата философских наук профессора Ибрагимова М.М. Национальный университет физического воспитания и...
15665. ИДЕЯ СПОРТА В СОВРЕМЕННОМ СОЦИАЛЬНО-ФИЛОСОФСКОМ ДИСКУРСЕ 107.5 KB
  ИДЕЯ СПОРТА В СОВРЕМЕННОМ СОЦИАЛЬНОФИЛОСОФСКОМ ДИСКУРСЕ М.М.Ибрагимов Постановка проблемы. Современный спорт как и другие формы жизнедеятельности носит духовнопрактический характер поскольку имеет целеполагающую идею образующую в развитии общества физкульту...
15666. ФИЛОСОФИЯ СПОРТА: ВЫМИРАНИЕ ИЛИ ОБНОВЛЕНИЕ ЕГО ИДЕАЛОВ 59 KB
  ФИЛОСОФИЯ СПОРТА: ВЫМИРАНИЕ ИЛИ ОБНОВЛЕНИЕ ЕГО ИДЕАЛОВ Ибрагимов М.М. Каждая эпоха приобретая новые идеи приобретает и новые глаза Г.Гейне Введение. Возникшей в начале ХХI века новый этап глобальных информационных технологий кризис во всех сферах материальной...
15667. ФИЛОСОФИЯ СПОРТА: ПРЕДМЕТ, СТРУКТУРА И ПРОБЛЕМЫ МЕТОДОЛОГИИ 140 KB
  ФИЛОСОФИЯ СПОРТА: ПРЕДМЕТ СТРУКТУРА И ПРОБЛЕМЫ МЕТОДОЛОГИИ. Ибрагимов Михаил Михайлович ациональный университет физического воспитания и спорта Украины Аннотация. Ибрагимов М.М. Философия спорта: предмет структура и проблемы методологии // Актуальні проблеми
15668. ФІЛОСОФІЯ СПОРТУ: ЧИ БУДЕ ПЛІДНОЮ ФІЛОСОФІЯ НА НИВІ СПОРТУ 127 KB
  Філософія спорту ФІЛОСОФІЯ СПОРТУ: ЧИ БУДЕ ПЛІДНОЮ ФІЛОСОФІЯ НА НИВІ СПОРТУ Михайло Ібрагімов Анотація. В статті мова йде про аналітичну підготовчу роботу до формування нової міждисциплінарної галузі знань філософії спорту яка б завершила ієрархію гуманітарн