47287

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

Доклад

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

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

Русский

2014-03-31

76.6 KB

0 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

83606. Пояснения о стадийности разработки ПСД (проектно-сметной документации) 31.71 KB
  Для разработки проектной документации заказчик должен заключить договор с проектной или проектностроительной организацией другими юридическими или физическими лицами получившими в установленном порядке лицензию на право проектирования данного вида объектов в соответствии с законодательством. Разработка проектной документации может вестись в одну или две стадии. В состав проектной документации при двухстадийном проектировании входят архитектурный и строительный проекты а при одностадийном строительный проект с выделением утверждаемой...
83607. Классификация систем электроснабжения и их специфические особенности 34.96 KB
  Система электроснабжения совокупность источников и систем преобразования передачи и распределения электрической энергии. Система электроснабжения не включает в себя потребителей или приёмников эл. К системам электроснабжения СЭС предъявляются следующие основные требования: Надёжность системы и бесперебойность электроснабжения потребителей.
83608. Приведение однофазной нагрузки к условной трехфазной мощности 35.82 KB
  Если неравномерность превышает 15 то расчетная нагрузка определяется по одной из рассмотренных ниже методик: При числе однофазных приемников до трех условная трехфазная номинальная мощность Р3усл определяется: при включении электроприемников на фазное напряжение: Р3усл= 3Р1ф.нб мощность наиболее загруженной фазы; при включении на линейное напряжение: Р3усл= Р1ф.нб для одного электроприемника Р3усл= 3Р1ф.
83609. Методы расчета электрических нагрузок 39.5 KB
  Расчет электрических нагрузок выполняется с целью правильного выбора сечений линий и распределительных устройств, коммутационных и защитных аппаратов, числа и мощности трансформаторов на разных уровнях системы электроснабжения. В зависимости от места определения расчетных нагрузок и необходимой
83610. Классификация характеристик помещений 31.22 KB
  Применение или хранение на производстве взрывающихся и воспламеняющихся при определенных условиях веществ определяет их категорию по взрыво и пожароопасности. Всего предусмотрено пять категорий пожароопасности: А Б В Г Д. Категории пожароопасности Категории А и Б по взрыво пожароопасности присваиваются производствам на которых возможна нештатная ситуация воспламенения и при этом существует угроза взрыва с избыточным давлением более 5 кПа. Категория пожароопасности А На взрывоопасных производствах категории А в качестве причины...
83611. Определение расчетных нагрузок для жилого городского района напряжением до 1 кВ 39.53 KB
  Расчетная электрическая нагрузка квартир Pкв кВт приведенная к вводу жилого дома определяется по формуле Pкв = Pкв.1 кВт квартира; n количество квартир. Расчетная нагрузка силовых электроприемников Pс кВт приведенная к вводу жилого дома определяется по формуле Pс = Pр.л кВт определяется по формуле где kc коэффициент спроса по табл.
83612. Категории электроприёмников, надёжность электроснабжения 30.34 KB
  В отношении обеспечения надежности электроснабжения потребителей разделяют на следующие три категории:Потребители I категории электроприемники перерыв электроснабжения которых может повлечь за собой: опасность для жизни людей значительный ущерб народному хозяйству; повреждение дорогостоящего основного оборудования массовый брак продукции расстройство сложного технологического процесса нарушение функционирования особо важных элементов коммунального хозяйства.Из состава электроприемников I категории выделяют особую группу...
83613. Определение расчетных нагрузок для сельской местности напряжением до 1 кВ 50.72 KB
  В результате протяженность сетей на единицу мощности потребителя во много раз превышает эту величину в других отраслях народного хозяйства а стоимость электроснабжения в сельском хозяйстве составляет до 6575 от общей стоимости электрификации включая затраты на приобретение рабочих машин. Определяются суммарные мощности: 5. Определяют расчётную нагрузку осветительных приёмников цеха определяется по установленной мощности и коэффициенту спроса кВт РРО 5. Определяют отдельно дневную и вечернюю полные мощности: 6.
83614. Выбор разъединителей, отделителей и короткозамыкателей 41.03 KB
  Условиями выбора разъединителей являются где номинальное напряжение сети кВ; номинальное напряжение электрического аппарата или токоведущих частей кВ; максимально возможный ток в месте установки разъединителей в рабочем режиме кА; номинальный ток электрического аппарата или токоведущих частей кА. Условия проверки электродинамической стойкости разъединителей: по способности выдерживать ударный ток Условия проверки термической стойкости разъединителей Короткозамыкатели и отделители это специальные разъединители имеющие...