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


 

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

5341. Прогнозирование производства продукции скотоводства в племзаводе по разведению черно-пестрого скота с поголовьем коров 1000 голов, удоем 7000 кг молока в год на одну корову 216.5 KB
  Скотоводство является превалирующей отраслью животноводства. Традиционно в России разведением племенного скота занимались наиболее зажиточные крестьяне, помещики, также высокая культура скотоводства всегда поддерживалась в монастырских хозя...
5342. Разработка комплексного проекта свиноводческой фермы с годовой производительностью 25 000 ц свинины в живой массе 278.5 KB
  Введение. Свиноводство имеет большое народно-хозяйственное значение. На долю его приходится свыше 20% валовой продукции животноводства и 10% всей продукции сельского хозяйства. Высокая плодовитость свиней, короткий эмбриональный период, скороспелост...
5343. Комплексная оценка метеорологической обстановки по заданной воздушной трассе 76 KB
  Оценка характера синоптической обстановки. В районе ИПМ (Берлин) находится неустойчивая холодная воздушная масса. Берлин находится в тыловой части циклона, в центре которого давление 990. Далее маршрут проходит через холодный фронт, далее тёплый...
5344. Микропроцессорное устройство Измерения частоты вращения ротора двигателя 99 KB
  Объектом проектирования является измеритель частоты вращения ротора двигателя. Цель работы – создание микропроцессорного комплекса измерения частоты вращения ротора двигателя . В результате проектирования разработана принципиальная...
5345. Работа со списками в MS EXCEL 206.5 KB
  Работа со списками в MS EXCEL Цель: Приобрести навыки поиска и агрегирования данных в списке. Краткая теория Компьютерные информационные технологии широко используются для анализа данных и подготовку управленческих решений на основе экономико ...
5346. Финансовый анализ. Технология подбора параметра 196.5 KB
  Финансовый анализ. Технология подбора параметра Цель работы: приобрести навыки решения задач финансового менеджмента с использованием встроенных функций MS Excel. Краткая теория ФИНАНСОВЫЕ ФУНКЦИИ В MS Excel встроен ряд функций, позволяющий...
5347. Работа с базами данных в MS EXCEL 55.5 KB
  Работа с базами данных в MSEXCEL Цель: Приобрести навыки использования встроенных функций МS Ехсеl для работы со списками. Краткая теория Информационная технология обработки данных в информационных системах предполагает их хранение и обработку...
5348. Информационная технология поиска решения 89 KB
  Информационная технология поиска решения Цель работы: ознакомиться со средствами поиска решения MS Excel на примере задач линейного программирования. Краткая теория Методы линейного программирования эффективно используются для решения задач опт...
5349. Частотный анализ в среде MS Excel 108 KB
  Частотный анализ в среде MS Excel Цель работы: Приобрести навыки решения задач частотного анализа с помощью функции рабочего листа анализа MS Excel. Краткая теория При анализе экономических показателей часто возникает вопрос, как часто вст...