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

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


 

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

80558. Непрямі податки, податки і платежі за майно і ресурси підприємств 239.5 KB
  Акцизний збір — це непрямий податок, що встановлюється на підакцизні товари та включається в їхню ціну. Акцизний збір (далі – АЗ) – специфічний акциз, що застосовується для обмеженої кількості товарів, які називаються підакцизними.
80559. Місцеві податки і збори. Спрощена система оподаткування 160 KB
  Особливості їх стягнення і впливу на фінансовогосподарську діяльність субєктів господарювання полягають у такому: Місцеві податки і збори включають до складу валових витрат що вираховуються зі скоригованого валового доходу а отже зменшують суму оподатковуваного прибутку. Місцеві податки і збори субєкти господарювання відносятьна собівартість продукції робіт послуг що впливає на формування бухгалтерського прибутку. Платниками цього податку є субєкти підприємницької діяльності їхні філії відділення представництва постійні...
80560. Визначення потреби в оборотних коштах 42.5 KB
  Нормування незавершеного виробництва і готової продукції. Аналогічно нормується запас палива за видами на виробничі і невиробничі цілі норматив на тару з урахуванням часу виготовлення або транспортування прошивки та інших стадій підготовки до запакування продукції. Усі витрати на початі але незавершені вироби у цехах майстернях інших виробничих приміщеннях після видачі зі складу матеріалів до моменту передачі продукції на склад визначаються вартістю незавершеного виробництва. Нароматив незавершеного виробинцтва залежить від: обсягу і...
80561. Використання і контроль обігового капіталу 72 KB
  Ефективність використання оборотного капітал може бути досягнення шляхом прискорення їх обертання. Шляхи прискорення обігу оборотних активів для вивільнення оборотних коштів
80562. Банківське кредитування підприємств 165.5 KB
  Слово «кредит» походить від латинського, що означає борг, позика. В сучасному понятті кредит - це капітал, який береться під позику у вигляді грошової форми і надається в тимчасове використання госпорганам на умовах забезпеченості, повернення, терміновості, оплати та цільового використання.
80563. Небанківське і міжнародне кредитування підприємств 280 KB
  Комерційний кредит — це одна з найперших форм кредитних відносин в економіці, саме він породив вексельний обіг і тим самим сприяв розвитку безготівкового грошового обігу. Основна мета комерційного кредиту — прискорення процесу реалізації товарів і отримання закладеного в них прибутку.
80564. Фінансове забезпечення інвестиційної діяльності 104 KB
  Згідно закону України Про інвестиційну діяльність інвестиції усі види майнових та інтелектуальних цінностей що вкладаються в обєкти підприємницької та фінансової діяльності в результаті чого створюється прибуток або досягається соціальний ефект. інвестиції це вкладення капіталу в обєкти підприємницької діяльності з метою забезпечення його зростання у майбутньому. Інвестиції розрізняють за видами. Фінансові інвестиції це активи які утримує підприємство з метою отримання прибутку за рахунок відсотків дивідендів зростання вартості...
80565. Оцінка ефективності інвестицій 180 KB
  Ефективність дохідність довготермінових облігацій може бути виміряна у вигляді: купонної дохідності норма відсотка облігації; ставки розміщення річної ставки складних відсотків. Ставка розміщення найбільш точно характеризує реальну фінансову ефективність облігації враховуючи всі види доходів від неї. Отже завдання вимірювання фінансової ефективності облігації зводиться до обчислення ставки розміщення у вигляді річної ставки складних відсотків. Нарахування відсотків за цією ставкою на ціну придбання облігації яка може відрізнятись від...
80566. Особливості фінансів малого бізнесу 232 KB
  Малий бізнес є найбільш поширеним сектором економіки. Відмінності між цими трьома видами бізнесу обумовлені різним рівнем суспільного поділу праці, характером спеціалізації га усуспільнення виробництва, а також вибором технологічного типу виробничого процесу.