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


 

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

48217. ТЕОРИЯ ГОСУДАРСТВА И ПРАВА 3.94 MB
  Теория государства и права: Курс лекций Под ред. ПРЕДИСЛОВИЕ Литература по общей теории государства и права пока еще не отражает в полной мере тех глубоких перемен которые происходят сегодня в России. Книга рассчитана как на студентов первых курсов только начинающих изучать основы теории государства и права так и на студентоввыпускников уже получивших необходимую подготовку.
48218. Теория массовой коммуникации 388 KB
  Массовая коммуникация - процесс распространения информации с помощью технических средств (пресса, радио, телевидение и др.) на численно большие, рассредоточенные аудитории
48219. ТЕОРІЯ ЕЛЕКТРИЧНИХ КІЛ 4.42 MB
  Теорія та розрахунок трифазних лінійних кіл На попередніх лекціях ми розглядали кола однофазного змінного струму а саме такі кола в яких кожне джерело енергії створює лише одну синусоїдну ЕРС. Але на практиці основна кількість електричної енергії генерується і споживається в формі трифазного струму. Шестифазні струми використовуються при перетворенні змінного струму в постійний. Позитивний напрям фазних ЕРС приймаємо від кінця обмотки до початку напруги від початку до кінця а позитивний напрям струму співпадає з позитивним напрямом...
48220. ПРЕДМЕТ І МЕТОД СТАТИСТИКИ 1.61 MB
  Основні категорії статистики З питанням про предмет статистики пов'язані поняття статистичної закономірності та статистичної сукупності. Згідно з цими принципами закони суспільного розвитку виразно виявляються лише в досить численній сукупності подій. 2Закономірності розподілу елементів сукупності. Склад елементів і спосіб їх об'єднання визначають структуру сукупності.
48221. ОРГАНІЗАЦІЯ ТА ПЛАНУВАННЯ ВИРОБНИЦТВА 667.5 KB
  Системи договірних відносин на оптовому ринку електроенергії. У загальному розумінні поняття енергетичний ринок можна трактувати як місце зустрічі продавця енергії та її покупця. Таким чином енергетичний ринок у широкому розумінні містить таких учасників ринку як підприємства видобувачі паливноенергетичних ресурсів організації що переробляють ці ресурси постачальники кінцевої енергії споживачі енергії а також підприємства що виготовляють товари та надають послуги які забезпечують процес виробництва енергії наприклад основні фонди...
48222. Технічна механіка 8.62 MB
  Технічна механіка є фундаментальною загальнотехнічною дисципліною, невід’ємною складовою системи підготовки інженерно-технічних працівників. Під час вивчення курсу студенти оволодівають знаннями законів рівноваги та руху матеріальних тіл, методів розрахунку елементів конструкцій, машин та споруд на міцність, жорсткість, стійкість, основами проектування деталей, вузлів машин. Знання дисципліни необхідні спеціалістам, які повинні організовувати належну експлуатацію й обслуговування сучасної залізничної техніки, удосконалювати її конструкцію та технології застосування.
48223. ТЕРМИЧЕСКИЕ МЕТОДЫ ОЧИСТКИ ВОД 81.5 KB
  Установки термического обезвреживания минерализованных сточных вод должны соответствовать следующим основным требованиям: I обеспечивать снижение концентрации вредных веществ в очищаемой воде до значений меньших ПДК; 2 иметь незначительную чувствительность к составу стоков; 3 обеспечивать надежность и экономичность в работе; 4. Концентрирование сточных вод Многокорпусные выпарные установки. На практике используют однокорпусные и многокорпусные выпарные установки включающие аппараты с естественной и принудительной циркуляцией. Наибольшее...
48224. Основні підходи до визначення поняття парламентаризму 56 KB
  : Поняття П = відображає з одно боку місце парламенту в мехзмі поділу влади і в цьому значенні наближене до політичного режиму а з іншого принципи устрою парламенту. влади: У вузькому розумінні: оргція і функціонування органу законодавчої влади що хться верховенством парламенту наявністю в нього виключних прерогатив і повноважень Журавський В. влади з особливою активною 1998 роллю парламенту. влади з вагомою і значною роллю парламенту передбаченими Кцією можливостями його активного впливу на сусп.