47287

Алгоритм пересчета балансов вершин выделенного пути и его особенности

Доклад

Информатика, кибернетика и программирование

После добавления нового элемента необходимо обновить коэффициенты сбалансированности родительских узлов Если любой родительский узел принял значение -2 или 2, то необходимо выполнить балансировку поддерева путем поворота

Русский

2014-03-31

76.6 KB

0 чел.

Алгоритм пересчета балансов вершин выделенного пути и его особенности.

Основная идея

Если вставка или удаление элемента приводит к нарушению сбалансированности дерева то выполняется его балансировка 

 Коэффициент сбалансированности узла

это разность высот его левого и правого поддеревьев 

В АВЛ дереве коэффициент сбалансированности любого

узла принимает значения из множества {-1, 0, 1}

Балансировка дерева

После добавления нового элемента необходимо обновить коэффициенты сбалансированности родительских узлов Если любой родительский узел принял значение -2 или 2, то необходимо выполнить балансировку поддерева путем поворота

Типы поворотов:

Одиночный правый поворот

Одиночный левый поворот

Двойной лево -правый поворот

Двойной право- левый поворот


 

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

3543. Тенденции развития печатной техники 342.84 KB
  Тенденции современного рынка печатной продукции оказали большое влияние и на развитие полиграфической техники. Всем понятно, что типографии будут приобретать то оборудование, которое позволит им успешнее работать на рынке в сложившейся ситу...
3544. СМИ как инструмент PR в условиях региона (на примере города Брянска) 1.48 MB
  Актуальность исследования. Одной из основных форм PR-деятельности является подготовка текстовых материалов для целевой общественности и для СМИ. PR-материалы любой организации создаются с целью продвижения информации для достижения понимани...
3545. Реконструкция газоочистных устройств ТЭЦ г. Анжеро-Судженск 2.9 MB
  Энергия – это движущая сила любого производства. Тот факт, что в распоряжении человека оказалось большое количество относительно дешевой энергии, в значительной степени способствовало индустриализации и развитию общества. Топливно-энер...
3546. Холодная штамповка 142.5 KB
  Холодная штамповка - одна из самых прогрессивных технологий получения заготовок, ;а в ряде случаев и готовых деталей изделий машиностроения, приборостроения, радиоэлектронных и вычислительных средств. По данным приборостроительных и ма...
3547. Машины для дробления, сортировки и мойки каменных материалов 131 KB
  Строительные машины в настоящее время неотъемлемая часть в любой сфере косвенно или прямо связанной со строительством. Позволяют улучшить и проконтролировать качество строительства. Ускорить сроки строительства. Облегчить труд человека в ка...
3548. Основные пути увеличения прибыли на предприятии ООО Гриант 114.5 KB
  Основную цель деятельности любого производителя (фирмы, делового предприятия) составляет максимизация прибыли. Возможности её получения ограничены, во-первых, издержками производства и, во-вторых, спросом на произведенную продукцию. Произво...
3549. Понятие социальной группы. Классификация групп 77 KB
  Понятие социальной группы. Классификация групп Общество – это не просто совокупность отдельных людей. Среди больших социальных общностей классы, социальные слои, сословия. Каждый человек принадлежит к какой-либо из этих социальных групп или мож...
3550. Теории экономического цикла и их эволюция 136 KB
  Новые реалии экономики побуждают к некоторому переосмыслению многих, казалось бы, вполне устоявшихся трактовок теоретических проблем. Одна из них циклы и кризисы. Сегодня их объяснение освобождается от политизированных оценок, в частности о...
3551. Технология машиностроения 43.5 KB
  Технология машиностроения Введение Технология машиностроения как отрасль науки. Особенности технологии машиностроения как учебной дисциплины. Содержание дисциплины "Основы технологии машиностроения". Перспективы развития технологии машиностроения. П...