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

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


 

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

41009. Поняття про педагогічні конфлікти: специфіка, функції 154.5 KB
  Природа педагогічного конфлікту має суттєві відмінності порівняно з іншими видами конфліктів зумовлені тим що в конфліктну взаємодію включені дитина і дорослий а не просто дві рівноцінні дорослі людини що мають певний досвід розум волю саморегуляцію і інші якості набуті в ході життя В. Тому велика кількість літератури з питань конфліктів не завжди сприяє педагогічному успіху у вирішенні проблеми педагогічного конфлікту. Більше того необхідність вивчення педагогічних конфліктів диктується гостротою соціальнопсихологічних ситуацій в...
41010. ЕТЮД НА ПОДІЮ, ЯКУ ВИРАЖЕНО «ЛАНЦЮГОМ ПСИХОФІЗИЧНИХ ДІЙ» НА ОСНОВІ ЛІТЕРАТУРНОГО ТВОРУ 235.5 KB
  Якщо у вправі студенти освоюють той або інший навик узятий ізольовано як такий то етюд це завжди якась історія відрізок життя в основі якого лежить подія. В таких етюдах особливо важливим є момент сприйняття факту: детальна розшифровка миті життя що передбачає рух думки внутрішній монолог внутрішню боротьбу мотивів розробку психофізичної реакції на подію темпоритму існування. В кінці життя Костянтин Сергійович Станіславський стверджував що надзадача і наскрізна дія головне в мистецтві. Необхідно виробити в собі звичку постійно...
41011. Походження і головні етапи розвитку культури 37 KB
  Виникнення мистецтва.Основні види мистецтва.Походження мистецтва.Види і функції мистецтва.Виготовлення знарядь праці передбачає ускладнення центральної нервової системи, передовсім головного мозку,здатність до точніших рухів,але не розвиток м’язів
41012. Медичні та соціальні проблеми вживання психоактивних речовин 74.5 KB
  Крім цього у хворих які зловживають психоактивніми речовинами набагато частіше розвиваються ураження шлунковокишкового тракту панкреатити гастрити пептичні виразки шлунка й ін. Одним з визначальних завдань наркології є лікування хворих на алкоголізм наркоманію та токсикоманію. Оскільки зловживання алкоголем у хворих на алкоголізм є безпосереднім проявом патологічного потягу до алкоголю його клінічні форми теж належать до істотних характеристик захворювання. Висока смертність хворих на наркоманії токсикоманію обумовлена...
41013. Психологічні особливості проходження інтервю та самопрезентаціявості проходження інтервю та самопрезентація 81.5 KB
  Інтервю з роботодавцями – це важливий етап при влаштуванні на роботу. Інтервю є найбільш широко використовуваним методом відбору. До інтервю зазвичай допускається 20-30% від загального числа кандидатів, що залишилися після попередніх етапів відбору.
41014. РАННЄ ХРИСТИЯНСТВО 43.5 KB
  Ісус Христос засновник християнства. Ісус Христос: свідоцтва про життя. Засновником нової релігії виступив Ісус Христос. Христос згадується у Таціта Светонія Плінія Молодшого а також у іудейського історика Иосифа Флавія.
41015. СЕМАНТИКА ПРЕДЛОЖЕНИЯ 80 KB
  Пропозиция это модель называемого предложением объективного содержания воплощение некоего положения дел в действительности в отвлечении от всех субъективных смыслов и от той проекции которую придаёт ему та или иная формальная организация. Пропозиция отражает структуру события ситуации. Таким образом каждая пропозиция являясь моделью ситуации имеет свою структуру вершиной которой выступает предикат. Пропозиция имеет в языке разные формы воплощения.
41016. Специфіка історичного розвитку української культури 34 KB
  Автохтонні джерела української культури 2. Самодостатні історичні типи української культури. Автохтонні джерела української культури Коріння української культури стародавнє але надзвичайно міцне.
41017. Аналіз фінансового стану підприємства 160.5 KB
  Значення завдання та джерела інформації для аналізу фінансового стану підприємства. Коефіцієнти фінансової стійкості підприємства їх економічний зміст методи розрахунку та аналізу. Значення завдання та джерела інформації для аналізу фінансового стану підприємства Фінансовий стан підприємства це його здатність фінансувати свою діяльність.