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


 

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

50954. Информационные ресурсы и информационные технологии 99 KB
  Создание WebстраницHTML Создание Web документов Применение языка HTML Публикация Web документов Обработка числовых данных в электронных таблицах общие сведения об электронных таблицах EXEL. Создание Web страниц HTML Размещение собственных материалов в Интернете включает два этапа: подготовку материалов и их публикацию. Подготовка материалов состоит в создании документов имеющих формат принятый в Интернете то есть Webстраниц написанных на языке HTML Публикация материалов то есть открытие к ним доступа осуществляется...
50955. Введение в дисциплину. Понятие информатики. Место информатики в ряду других фундаментальных наук 59 KB
  Направления для практических приложений: архитектура вычислительных систем приемы и методы построения систем предназначенных для автоматической обработки данных; интерфейсы вычислительных систем приемы и методы управления аппаратным и программным обеспечением; программирование приемы методы и средства разработки компьютерных программ; Преобразование данных приемы и методы преобразования структур данных; защита информации обобщение приемов разработка методов и средств защиты данных; автоматизация функционирование...
50956. Информационные процессы и информационные технологии. Информационный ресурс и его составляющие 96.5 KB
  Создание Web страниц HTML Размещение собственных материалов в Интернете включает два этапа: подготовку материалов и их публикацию. Подготовка материалов состоит в создании документов имеющих формат принятый в Интернете то есть Webстраниц написанных на языке HTML Публикация материалов то есть открытие к ним доступа осуществляется после решения организационных вопросов связанных с получением дискового пространства на Webсервере для их размещения. Создание Webдокументов Автономные Webдокументы используют язык HTML...
50957. Обработка данных. Основные виды обработки данных 87 KB
  Для реализации распределенной обработки данных были созданы многомашинные ассоциации структура которых разрабатывается по одному из следующих направлений: многомашинные вычислительные комплексы МВК; компьютерные вычислительные сети. Обобщенная структура компьютерной сети Компьютерные сети являются высшей формой многомашинных ассоциаций. Основные отличия компьютерной сети от многомашинного вычислительного комплекса: Размерность. Необходимость решения в сети задачи маршрутизации сообщений.
50958. Функциональная и структурная организации компьютера 63.5 KB
  Алгоритм решения задач имеет ряд своих обязательных свойств; дискретность разбиение процесса обработки информации на более простые этапы шаги выполнения выполнение которых компьютером или человеком не вызывает затруднений; определенность алгоритма однозначность выполнения каждого отдельного шага преобразования информации; выполнимость конечность действий алгоритма решения задач позволяющая получить желаемый результат при допустимых исходных данных за конечное число шагов; массовость пригодность алгоритма для решения...
50959. Информационные основы контроля работы цифрового автомата 165 KB
  При возникновении какоголибо нарушения нормального функционирования результат будет неверным однако пользователь об этом не узнает если не будут предусмотрены меты для создания системы обнаружения возможной ошибки а с другой стороны должны быть проработаны меры позволяющие исправить ошибки. Система контроля совокупность методов и средств обеспечивающих определение правильности работы автомата в целом или его отдельных узлов а также автоматическое исправление ошибки. Ошибки в работе цифрового автомата могут быть вызваны либо выходом...
50960. Каналы передачи данных 104 KB
  Рассматривают три основных параметра сигнала существенных для передачи информации по каналу. Первый важный параметр это время передачи сигнала Tс. Следовательно общее условие согласования сигнала с каналом передачи информации определяется соотношением Однако соотношение выражает необходимое но недостаточное условие согласования сигнала с каналом.
50961. Сигналы и их характеристики 367.5 KB
  Например при выборе прибора для контроля технологического процесса может потребоваться знание дисперсии сигнала; если сигнал используется для управления существенным является его мощность и так далее. Рассматривают три основных параметра сигнала существенных для передачи информации по каналу. Первый важный параметр это время передачи сигнала Tx . Второй характеристикой которую приходится учитывать является мощность Px сигнала передаваемого по каналу с определенным уровнем помех Pz .
50962. Информация, сообщения, сигналы 70 KB
  Структурная схема системы передачи информации Классификация сигналов по дискретнонепрерывному признаку Квантование и кодирование сигналов Квантование по уровню Квантование по времени Лекция №5 Тема: Информация сообщения сигналы Структурная схема системы передачи информации Теория информации это наука о получении преобразовании накоплении отображении и передаче информации. В настоящее время существуют различные определения информации. Структурная схема одной из характерных информационных систем в общем случае может быть...