53495

Алгоритм вставки вершины AVL дерево. Случай одного (левого) поворота

Доклад

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

Следовать по пути поиска, пока не окажется, что узла нет в дереве. Включить новый узел и определить показатель сбалансированности. Пройти обратно по пути поиска, определяя сбалансированность.

Русский

2014-04-01

129.41 KB

1 чел.

Алгоритм вставки вершины AVL дерево. Случай одного (левого) поворота.

Алгоритм добавления узла в AVL дерево

3 этапа:

  1. Следовать по пути поиска, пока не окажется, что узла нет в дереве.
  2. Включить новый узел и определить показатель сбалансированности.
  3. Пройти обратно по пути поиска, определяя сбалансированность.

Включение узла:

  1. Выполнить вставку в бинарное дерево.
  2. Если вставка в левое поддерево, то имеют место 3 случая:
  3. Если правое поддерево было длиннее, то стало сбалансированным.
  4. Если был баланс, то левое поддерево выросло, и нужно проверить балансировку выше.
  5. Левое поддерево было длинее, имеем расбалансировку.
  6. Если в правое:
  7. Если левое поддерево было длиннее, то стало сбалансированным.
  8. Если был баланс, то правое поддерево выросло, и нужно проверить балансировку выше.
  9. Правое поддерево было длинее, имеем расбалансировку.

Случай левого поворота


 

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

44996. ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ СУЧАСНИХ ПК 58 KB
  Програмне забезпечення ПК – це сукупність системних, прикладних та програм технічного обслуговування ПК. Вони дають змогу найбільш ефективно використовувати ресурси ПК при розв’язанні практичних задач. Основними вимогами до програмного забезпечення ПК...
44997. Финансовые службы, их задачи и функции 48 KB
  Финансовые службы их задачи и функции План Финансовые службы предприятия Финансовые службы предприятия Деятельность финансовых служб подчинена главной цели обеспечению финансовой стабильности созданию устойчивых предпосылок для экономического роста и получения прибыли Задачи финансовых служб: организация взаимоотношений предприятия с другими субъектами хозяйствования поиск внутренних и внешних краткосрочных и долгосрочных источников финансирования выбор наиболее оптимального их сочетания своевременное обеспечение финансовыми...
44998. Разработка программы маркетинговых коммуникаций для ООО «Тойота Центр Кунцево»нсовое 2.1 MB
  Исследованы теоретические основы разработки программ маркетинговых коммуникаций для автодилеров; проанализирована внешняя маркетинговая среда автомобильного салона «Тойота» (Москва); оценено положение на рынке автомобильного салона «Тойота» (Москва) и проанализирована его маркетинговая деятельность...
44999. МЕТОДИКА ЛОГОПЕДИЧЕСКОГО ВОЗДЕЙСТВИЯ ПРИ ДИСЛАЛИИ 106 KB
  Развитие фонематического восприятия детей в ходе подготовительного этапа логопедического воздействия. Формирование артикуляторных, дыхательных и голосовых умений и навыков в ходе подготовительного этапа логопедического воздействия. Развитие мелкой моторики рук в ходе подготовительного этапа логопедического воздействия.
45000. ЗАХИСТ ПРАВ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ 98.5 KB
  Створення обєкта інтелектуальної власності розпочинається з ідеї. Наприклад, це може бути ідея винаходу або художнього твору. У підприємницькій діяльності ідеї, як правило, направлені на підвищення конкурентоспроможності технологій або виробів
45001. Расходы и доходы организаций 195.5 KB
  Расходы и доходы организаций План Классификация затрат 2. Классификация затрат В процессе осуществления производственно-хозяйственной и финансовой деятельности предприятия несут определенные расходы. расходы связанные с извлечением прибыли 2. расходы не связанные с извлечением прибыли 3.
45002. Прибыль организации 776 KB
  Экономическое содержание функции и виды прибыли Методы планирования прибыли. Факторы роста прибыли Распределение использование прибыли на предприятии
45003. СПЕКТРАЛЬНЫЙ АНАЛИЗ 296.5 KB
  Сущность и физические основы метода Спектральный анализ это способ определения химического состава и концентрации отдельных элементов в веществе по его спектру излучения или поглощения. Спектры излучения или поглощения представляют собой распределения интенсивности испускаемого или поглощаемого веществом излучения по длинам волн или частотам. При исследовании спектров понятие интенсивности употребляют чаще как величину пропорциональную мощности излучения приходящейся на рассматриваемую спектральную линию и выражают ее в относительных...
45004. ИЗУЧЕНИЕ ЯВЛЕНИЯ ВНЕШНЕГО ФОТОЭФФЕКТА. ОПРЕДЕЛЕНИЕ ПОСТОЯННОЙ ПЛАНКА 224.5 KB
  Снять зависимость задерживающего напряжения от частоты излучения. Поглощение оптического излучения веществом часто сопровождается электрическими явлениями которые получили название фотоэлектрического фотоэффекта. ВНЕШНИМ ФОТОЭФФЕКТОМ называется явление испускания электронов веществом под действием электромагнитного излучения. Характер зависимости фототока I от разности потенциалов между анодом и катодом U при постоянной интенсивности падающего на фотокатод монохроматического излучения приведен на Рис .