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

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


 

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

47093. Граница деятельности государства. Расходы, связанные с вмешательством государства в экономику. Эффективность государственного сектора 55.36 KB
  Исторически первым возникло натуральное производство при котором продукты труда предназначались для внутрихозяйственного потребления. Общественное разделение труда в натуральном хозяйстве было развито слабо. К примеру внутри латифундий имело место разделение труда между рабами которые исполняли различные виды работ. Но разделения труда между хозяйственными единицами не существовало был лишь идентичный набор видов работ.
47094. Ресурсы и человеческий капитал 58.68 KB
  Отраслевой рынок и дифференциация продукта Как показывает практика трудно найти на отраслевом рынке два одинаковых товара не из одной партии. установления степени дифференциации продукта. В зависимости от того насколько модифицируются различные свойства продукта выделяют четыре'главных вида дифференциации продукта. Вовторых существуют различия в качестве продукта: например туфли могут быть сделаны из натуральной кожи или кожезаменителя.
47095. Последовательное заполнение электронных уравнений атомов 55.7 KB
  принцип Пауликоторый часто называют еще принципом запрета ограничивает число электронов которые могут находиться на одной орбитали. Согласно принципу Паули на любой орбитали может находиться не более двух электронов и то лишь в том случае если они имеют противоположные спины неодинаковые спиновые числа. Поэтому в атоме не должно быть двух электронов с одинаковыми четырьмя квантовыми числами n l ml ms 3.Согласно правилу Гунда заселение орбиталей относящихся к одному и тому же энергетическому подуровню начинается одиночными...
47101. Агрохимическая служба в стране. Почвенный покров полярных и субполярных областей 53 KB
  Им был предложен термин элементарный почвенный ареал ЭПА это почвы относящиеся к какойлибо одной классификационной единице наиболее низкого ранга разряда занимающие пространство со всех сторон ограниченное другими ЭПА или непочвенными образованиями. Агрохимические картограммы это карты землепользования хозяйства где условными обозначениями указано содержание доступных форм питательных элементовазот фосфор калий микроэлементы гумус а также кислотность емкость катионного обмена степень насыщенности почвы основаниями....