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

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


 

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

10997. Философия и мировоззрение. Типы мировоззрений 28 KB
  Философия и мировоззрение. Мировоззрение– это сложное синтетическое интегральное образование общественного и индивидуального сознания. В нем присутствуют различные компоненты: знания убеждения верования настроения стремления ценности нормы идеалы и т.д. Мирово
10998. Основные особенности философского типа мышления 91.5 KB
  Основные особенности философского типа мышления: КОНЦЕПТУАЛЬНАЯ ОБОСНОВАННОСТЬ то есть последовательное проведение в решении мировоззренческих вопросов исходных однажды выбранных принципов их нельзя менять по ходу дела. В эти принципы конечно могут вноситься уточ...
10999. Функции философии 36 KB
  Функции философии Философия Пифагор автор слова фило любовь софи мудрость. С точки зрения Аристотеля мудрость означает знание общего в различных вещах знание первопричин действительности всеобщих свойств всеобщих законов всеобщих форм и структур действите
11000. Основные особенности досократовской философии 30.5 KB
  Основные особенности досократовской философии. Космоцентризм и основные понятия античной философииКосмос Природа Логос Эйдос Душа Спецификой греческой философии особенно в начальный период ее развития является стремление понять сущность природы космоса ми...
11003. Система и метод философии Гегеля. Диалектический метод Гегеля 25.46 KB
  Система и метод философии Гегеля. Выдающееся значение философии Гегеля заключалось в том что в ней в систематической форме было изложено диалектическое миропонимание и соответствующий ему диалектический метод исследования. Гегель разрабатывал д...
11004. Соотношение философии и науки по предмету. Предмет философии как отношение человека к миру 73.5 KB
  Соотношение философии и науки по предмету. Предмет философии как отношение человека к миру 1. Соотношение философии и науки по предмету. Множество определений философии. Существует множество определений философии и ее предмета1. Древнегреческий философ Платон пола...
11005. Жизнь и философствования Сократа 62 KB
  Жизнь и философствования Сократа Поворотным пунктом в развитии античной философии явились воззрения Сократа 469 – 399 до н.э.. Его имя стало нарицательным и служит для выражения иди мудрости. Сам Сократ ничего не писал был близким к народу мудрецом; философствовал на улиц...