47317

Особенности дерева Фибоначчи, удаление вершины из AVL дерева

Доклад

Информатика, кибернетика и программирование

Дерево Фибоначчи несколько больше напоминает реальный куст, чем рассматривавшиеся ранее деревья, возможно, потому, что многие природные процессы удовлетворяют закону Фибоначчи

Русский

2014-03-31

49.19 KB

5 чел.

Особенности дерева Фибоначчи, удаление вершины из AVL дерева.

 Hаиболее асимметpичное АВЛ-деpево Th высоты h имеет наиболее асимметpичное АВЛ-деpево Th-1 высоты h-1 в качестве одного из своих поддеpевьев и наиболее асимметpичное АВЛ-деpево высоты h-2 в качестве дpугого. Подобные деpевья называются деpевьями Фибоначчи.

Дерево Фибоначчи несколько больше напоминает реальный куст, чем рассматривавшиеся ранее деревья, возможно, потому, что многие природные процессы удовлетворяют закону Фибоначчи.

Приведем формальное определение дерева Фибоначчи.

 Дерево Фибоначчи порядка k определяется следующим образом

  1. если k=0, то дерево Фибоначчи пусто;
  2. если k=1, то дерево Фибоначчи состоит из единственного узла, ключ которого содержит 1;
  3. если k >=2, то корень дерева Фибоначчи содержит ключ Fk, левое поддерево есть дерево Фибоначчи порядка k-1, правое поддерево есть дерево Фибоначчи порядка k-2 с ключами в узлах, увеличенными на Fk.

Здесь Fk - k-е число Фибоначчи: F0=1, F1=1, F2=2, F3=3, F4=5, F5=8, F6=13, ... (Заметим, что в математике рядом Фибоначчи называется последовательность u1, u2, ..., un,..., в которой u1=1, u2=1, un=un-1+un-2 для любого n>2, а члены этой последовательности - числами Фибоначчи.)

Изобpазим несколько деpевьев Фибоначчи pазной высоты:

Удаление элемента из AVL - дерева

При удалении узлов из AVL – дерева операция балансировки в основном остается такой же, что и при включении и заключается в однократном или двукратном повороте. При этом булевская переменная h, возвращаемая операцией удаления означает уменьшение высоты поддерева. При восходящем пересчете критерия сбалансированности выполняется балансировка тех узлов, у которых критерий стал равным +2 или -2. Балансировка выполняется с помощью тех же L - , R - , RL - и LR - поворотов.

 


 

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

36951. Вивчення універсального вимірювача Е7-11 при вимірюваннях індуктивності, ємності, опору, тангенса кута втрат й добротності елементів 378 KB
  Мета: Навчитись вимірювати індуктивність, ємність, опір, тангенса кута втрат й добротність елементів універсальним вимірювачем Е7-11.
36952. Проектування та створення баз даних у СУБД MS Access**. Створення табличних об’єктів засобами конструктора 858.5 KB
  Таблиці СУБД нормалізовані. Нормалізація процес видалення з таблиць даних що повторюються шляхом перенесення їх у інші таблиці записи яких не містять значень що дублюються. Структура реляційної таблиці визначається складом полів. Вміст поля подається у стовпці таблиці.
36953. Проведенння приймального суцільного контролю якості продукції 366.5 KB
  Підготувати прилад В7І6 до роботи і провести вимірювання опору резисторів на різких діапазонах. Підготувати прилад МО62 до роботи і провести вимірювання опору резисторів. 3 призначений для забезпечення високого вхідного опору приладу і перетворення величини вимірюваного опору в напругу. Перший каскад коефіцієнт підсилення якого дорівнює одиниці призначений для перетворення вимірюваного опору в напругу із цією метою на його виході автоматично.
36954. СУБД MS Access**. Сортування, пошук та відбір записів у таблиці. Конструювання запитів 1.34 MB
  Звичайний фільтр викликається послідовністю команд Записи Фильтр Изменить фильтр. Розширений Записи Фильтр Расширенный фильтр. Записи формуються шляхом обєднання записів таблиць що використовуються у запиті. Умови відбору сформульовані у запиті дозволяють фільтрувати записи що складають результат обєднання таблиць.
36955. Дослідження активних фільтрів на операційних підсилювачах у середовищі Electronics Workbench 95 KB
  Розрахувати номінали елементів наступних кіл: Примітка: для кожної зі схем доцільно обрати Ф а решту елементів розрахувати виходячи з вимог завдання варіанту; а ФНЧ першого порядку на неінвертуючій ланці з частотою зрізу і коефіцієнтом підсилення ; б ФВЧ першого порядку на неінвертуючій ланці з частотою зрізу і коефіцієнтом підсилення ; в ФНЧ другого порядку на неінвертуючій ланці з частотою зрізу і коефіцієнтом підсилення ; г ФВЧ другого порядку на неінвертуючій ланці з частотою зрізу і коефіцієнтом підсилення ; д СФ на...
36957. Дослідження надійності нерезервованої системи 36.8 KB
  При постійних інтенсивностях відмов елементах де інтенсивність відмови системи. Ризик системи Rct і обчислюються по наступним формулам: де Qct=1Pct вірогідність відмови системи протягом часу t; qit вірогідність відмови iго елементу системи протягом часу t. Якщо елементи системи рівно надійні то співвідношення Rct до має вигляд: .
36958. Волоконно-оптические системы передачи повышенной пропускной способности 676 KB
  Основным преимуществом ВОЛС к высокой помехоустойчивостью; качества длинной линии передачи и корреляция; параметры стабильности воспроизведения канала; Цифровой строительство сети; И самое главное - очень технико-экономические показатели
36959. Спрощена інструкція по роботі з інформаційною системою для бізнес-планування Project Expert 790 KB
  Вікно Новый проект назву проекту наприклад Проект підприємства з випуску офісних меблів; варіант довільну назву варіанта наприклад: 1 або Оптимістичний; прізвище автора код спеціальності та номер групи наприклад Іванов І. В результаті зявиться робоче вікно Содержание рис. Робоче вікно Содержание Примітка: протягом подальшої роботи над проектом слід час від часу зберігати файл проекту. Робоче вікно Валюта проекта 2.