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), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.


 

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

12560. Типовые звенья и их характеристики 285.76 KB
  МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторной работе по теме: Типовые звенья и их характеристики по дисциплине: Основы теории управления 1 Цель работы: Изучение теоретических сведений об элементарных и типовых звеньях систем автоматического управления. Закрепление те...
12561. ОПРЕДЕЛЕНИЕ ПАРАМЕТРОВ ПОТЕНЦИАЛОВ ЛЕННАРДА-ДЖОНСА ИЗ ВТОРОГО ВИРИАЛЬНОГО КОЭФФИЦИЕНТА 122 KB
  ОТЧЕТ по лабораторной работе №6 ОПРЕДЕЛЕНИЕ ПАРАМЕТРОВ ПОТЕНЦИАЛОВ ЛЕННАРДАДЖОНСА ИЗ ВТОРОГО ВИРИАЛЬНОГО КОЭФФИЦИЕНТА ВВЕДЕНИЕ В настоящей работе на основании исследования микроскопических свойств газа рассчитываются параметры потенциала ЛеннардаДжонса п...
12562. ОПРЕДЕЛЕНИЕ ПАРАМЕТРОВ ПОТЕНЦИАЛОВ ЛЕННАРДА-ДЖОНСА 422 KB
  ОТЧЕТ по лабораторной работе №6 ОПРЕДЕЛЕНИЕ ПАРАМЕТРОВ ПОТЕНЦИАЛОВ ЛЕННАРДАДЖОНСА ВВЕДЕНИЕ В настоящей работе на основании исследования макроскопических свойств газа рассчитываются параметры потенциала ЛеннардаДжонса применяемого в классических и кванто
12563. СОПРОТИВЛЕНИЕ ОБТЕКАЕМЫХ ТЕЛ 1.2 MB
  СОПРОТИВЛЕНИЕ ОБТЕКАЕМЫХ ТЕЛ Отчет по лабораторной работе № 6М ВВЕДЕНИЕ Определение силы с которой жидкость действует на обтекаемое тело является одной из основных задач механики сплошных сред. В данной работе эта сила определяется экспериментально на моделях в д
12564. Адиабата. Измерение показателя адиабаты акустическим методом 611 KB
  Колебательное движение с малыми амплитудами в сжимаемой жидкости называют акустическими волнами. Процесс распространения акустических волн в идеально сжимаемой жидкости списывается поведением во времени и пространстве основных акустических параметров
12565. ЯВЛЕНИЕ МАГНИТОСТРИКЦИИ 733.5 KB
  ОТЧЕТ по лабораторной работе №4 ЯВЛЕНИЕ МАГНИТОСТРИКЦИИ ВВЕДЕНИЕ Явление магнитострикции заключается в изменении формы и размеров ферромагнетика при изменении его намагниченности в магнитном поле. Магнитострикция позволяет выяснить природу сил которые опред...
12566. ИЗМЕРЕНИЕ КОЭФФИЦИЕНТА СОПРОТИВЛЕНИЯ ПРИ ТЕЧЕНИИ ВОЗДУХА В ЦИЛИНДРИЧЕСКОЙ ТРУБКЕ 298.5 KB
  ОТЧЕТ по лабораторной работе №4М ИЗМЕРЕНИЕ КОЭФФИЦИЕНТА СОПРОТИВЛЕНИЯ ПРИ ТЕЧЕНИИ ВОЗДУХА В ЦИЛИНДРИЧЕСКОЙ ТРУБКЕ ВВЕДЕНИЕ Цель данной лабораторной работы заключается в ознакомлении студентов с основными закономерностями и параметрами характеризующими теч
12567. ТЕПЛОЕМКОСТЬ КРИСТАЛЛИЧЕСКИХ ТЕЛ 653 KB
  ОТЧЕТ по лабораторной работе №3 ТЕПЛОЕМКОСТЬ КРИСТАЛЛИЧЕСКИХ ТЕЛ ВВЕДЕНИЕ Цель работы – ознакомление с микроскопической теорией теплоемкости кристаллических тел ознакомление с установкой для измерения теплоемкости и измерение теплоемкости двух образцов. ...
12568. БАРОЭФФЕКТ ПРИ ВЗАИМНОЙ ДИФФУЗИИ ГАЗОВ 137.5 KB
  ОТЧЕТ по лабораторной работе №2М БАРОЭФФЕКТ ПРИ ВЗАИМНОЙ ДИФФУЗИИ ГАЗОВ ВВЕДЕНИЕ Целью данной лабораторной работы является ознакомление с явлением бароэффекта при взаимной диффузии газов а также приобретение знаний и навыков в работе с ...