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. Правое поддерево было длинее, имеем расбалансировку.

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


 

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

20455. Кнопкові форми 24.5 KB
  На кнопкову форму виносять форми які відкривають формизвіти або активізують інші кнопкові формизакривабть поточну базу даних. Кнопокі форми можуть містити малюнкинаписи тощо. Кнопкові форми можна створити за допомогою диспетчера кнопкових форм за його допомогою на форму можна помістити до 8 кнопок.
20456. Комбінований метод хорд та дотичних 35.5 KB
  Характерна особливість методів дотичних і хорд та що послідовності їх наближень монотонні. Причому якщо для даного рівняння послідовність наближень методу хорд монотонно спадна то послідовність наближень методу дотичних – монотонно зростаюча і навпаки. У даному випадку за початкове наближення в методі хорд вибирають точку x=a а в методі дотичних – точку b.
20457. Множина́ 41.69 KB
  Основні поняття: Множина вважається означеною якщо про кожен об'єкт що розглядається можна казати що він або належить або не належить множині. Наприклад: ℕ множина натуральних чисел ℤ множина цілих чисел ℚ множина раціональних чисел ℝ множина дійсних чисел ℂ множина комплексних чисел. Нехай А множина. Множина B всі елементи якої належать множині А називають підмножиною множини A або частиною множини А і позначають цей факт символами B ⊆ A A ⊇ B.
20458. Основні задачі та проблеми проектування програмних продуктів 13.41 KB
  Пр428 Основні задачі та проблеми проектування програмних продуктів. Проектування – це процес розробки проекту тобто комплекту документації призначену для створення проекту його удосконалення та ліквідації а також для перевірки або відтворення проміжних і кінцевих рішень. Проектування – тривалий процес і включає етапи від підготовки технічного завдання до випробування. Процес створення програмного забезпечення ПЗ також включає в себе методи проектування.
20459. Каскадна (послідовна) модель 22.61 KB
  Вона передбачає послідовне виконання всіх етапів проекту в строго фіксованому порядку. Вимоги визначені на стадії формування вимог строго документуються у вигляді технічного завдання і фіксуються на весь час розробки проекту. Етапи проекту відповідно до каскадної моделлю: Формування вимог; Проектування; Реалізація; Тестування; Впровадження; Експлуатація та супровід. Недоліки: В Водоспадної моделі перехід від однієї фази проекту до іншого передбачає повну коректність результату виходу попередньої фази.
20460. Доповнення та різниця множин 18.86 KB
  Якщо A ⊂ U то елементи множини U які не належать А називаються доповненням множини А до множини U і позначають як CUA або UCA. Якщо A ⊂ U B ⊂ U то доповнення множини B до А називають різницею множин А та B саме в такому порядку і позначають А B або АB тобто A B = {x:x ∈ A ∧ x ∉ B}. Деякі властивості операції доповнення: A ∪ A′ = U A ∩ A′ = ∅ A′′ = A A − B = A ∩ B′ Об'єднання множин Об'єднанням множин А та B називається множина яка складається з усіх тих елементів які належать хоча б одній з множин A B: A ∪ B = {x: x ∈ A ∨ A...
20461. Життєвий цикл програмного забезпечення 58.5 KB
  Проектування: визначення структури системи та її проектуваннярозбиття програмної системи на окремі компоненти та проектування з визначенням ключових елементів структури даних. Тестування і верифікація: тестування вихідного текста;участь користувачів і колективів у всіх перевірках системи. Експлуатація і супроводження:використання готової програмної системи; оцінка її ефективності;усунення знайдених в процесі експлуатації помилок; внесення необхідних змін для підтримки актуальності програмної системи;д перевірка коректності внесених змін .
20462. Расчет характеристик вычислительных систем на основе стохастических сетей 239.66 KB
  В данной работе определяются характеристики вычислительной системы, модель замкнутой стохастической сети которой... Исходными данными для расчета являются следующие величины:
20463. Бу́лева фу́нкція (функція алгебри логіки, логічна функція) 22.02 KB
  Булева функція задається у вигляді таблиці або графіка зі стандартним лексикографічним розташуванням наборів аргументів. Нульарними булевими функціями є сталі 0 і 1. Функції 0 і 1 називаються тотожними нулем і одиницею функція x тотожною запереченням.