53488

Процедура вставки вершин в AVL дерева и ее особенности

Доклад

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

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

Русский

2014-04-01

19.29 KB

0 чел.

Процедура вставки вершин в AVL дерева и ее особенности.

Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей (данный процесс описан Николасом Виртом в «Алгоритмы и структуры данных»):

  1. Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
  2. Включения новой вершины в дерево и определения результирующих показателей балансировки.
  3. «Отступления» назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо — балансировка.

Будем возвращать в качестве результата функции, уменьшилась высота дерева или нет. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { hl — высота левого поддерева, hr — высота правого поддерева } Включение вершины в левое поддерево приведет к

  1. hl < hr: выравняется hl = hr. Ничего делать не нужно.
  2. hl = hr: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.
  3. hl > hr: теперь hl — hr = 2, — требуется балансировка.

В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.


 

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

19126. ПРОБЛЕМЫ ОБОСНОВАНИЯ РАБОТОСПОСОБНОСТИ ТВЭЛОВ 235.5 KB
  ЛЕКЦИЯ 6 ПРОБЛЕМЫ ОБОСНОВАНИЯ РАБОТОСПОСОБНОСТИ ТВЭЛОВ Тепловыделяющие элементы ядерных реакторов эксплуатируются в сложных условиях совместного воздействия радиационного излучения высоких температур механических напряжений и коррозионных сред. Выбор надежно...
19127. ПРОБЛЕМЫ ОБОСНОВАНИЯ РАБОТОСПОСОБНОСТИ ТВЭЛОВ 6.67 MB
  ЛЕКЦИЯ 7 ПРОБЛЕМЫ ОБОСНОВАНИЯ РАБОТОСПОСОБНОСТИ ТВЭЛОВ Работоспособность конструкции твэла может быть обоснована экспериментальными или расчетными методами. Экспериментальные методы обоснования работоспособности и надежности конструкции требуют массового обл
19128. РАСПРЕДЕЛЕНИЕ ТЕМПЕРАТУР ПО ВЫСОТЕ АКТИВНОЙ ЗОНЫ 134 KB
  ЛЕКЦИЯ 8 РАСПРЕДЕЛЕНИЕ ТЕМПЕРАТУР ПО ВЫСОТЕ АКТИВНОЙ ЗОНЫ РАСПРЕДЕЛЕНИЕ ЭНЕРГОВЫДЕЛЕНИЯ В АКТИВНОЙ ЗОНЕ Создание реактора с максимально выровненным и стабильным полем энерговыделения в течении кампании одна из важнейших задач оптимизации активной зоны. Выра...
19129. Компоновка и геометрические характеристики ТВС 608 KB
  ЛЕКЦИЯ 9 Компоновка и геометрические характеристики ТВС Для удобства перегрузок топлива транспортировки и организации охлаждения твэлы объединяются в ТВС. Основные требования к ТВС заключаются в следующем: обеспечение установленного физическим расчетом ре
19130. ГЕОМЕТРИЧЕСКИЕ ХАРАКТЕРИСТИКИ ТВС И ОБЪЕМНЫЙ СОСТАВ РАБОЧЕЙ ЯЧЕЙКИ 320 KB
  ЛЕКЦИЯ 10 ГЕОМЕТРИЧЕСКИЕ ХАРАКТЕРИСТИКИ ТВС И ОБЪЕМНЫЙ СОСТАВ РАБОЧЕЙ ЯЧЕЙКИ В предыдущей лекции представлена методика определения диаметра твэлов и числа ячеек для их размещения в ТВС. Целью настоящей лекции является компоновка ТВС расчет ее геометрических х
19131. ТЕПЛОГИДРАЛИЧЕСКИЙ РАСЧЕТ ТВС 529.5 KB
  ЛЕКЦИЯ 11 ТЕПЛОГИДРАЛИЧЕСКИЙ РАСЧЕТ ТВС Теплогидравлический расчет ТВС реактора на быстрых нейтронах Рассмотрим ТВС реактора на быстрых нейтронах распределение тепловыделения в активной части которой подчиняется закону косинуса. Пусть даны геометрия ТВС
19132. ДОПУСТИМАЯ МОЩНОСТЬ ТВЭЛА И ТВС 374.5 KB
  ЛЕКЦИЯ 12 ДОПУСТИМАЯ МОЩНОСТЬ ТВЭЛА И ТВС Допустимая мощность твэлов и ТВС в стационарных условиях эксплуатации определяется: предельными температурами эксплуатации оболочки твэла и элементов конструкции ТВС: предельными температурами эксплуатации
19133. АНАЛИЗ НАПРЯЖЕННО-ДЕФОРМИРОВАННОГО СОСТОЯНИЯ ТВЭЛОВ ЭНЕРГЕТИЧЕСКИХ РЕАКТОРОВ 536 KB
  Лекция 13 АНАЛИЗ НАПРЯЖЕННОДЕФОРМИРОВАННОГО СОСТОЯНИЯ ТВЭЛОВ ЭНЕРГЕТИЧЕСКИХ РЕАКТОРОВ Основы расчета на прочность Расчет на прочность важнейший этап конструирования элементов активной зоны ядерного реактора: на его основе выбираются их основные размеры ге
19134. Приближенные методы анализа напряжений и деформаций в оболочке в стационарных условиях эксплуатации твэла 663 KB
  ЛЕКЦИЯ 14 Приближенные методы анализа напряжений и деформаций в оболочке в стационарных условиях эксплуатации твэла В стационарных режимах эксплуатации при наличие зазора на оболочку действует давление равное разнице давлений теплоносителя и смеси газов внутри т