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 - поворотов.

 


 

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

81112. Написание слов с удвоенными буквами в корне 46.5 KB
  Учить учащихся произносить и правильно писать слова с удвоенными согласными буквами в корне слова; развивать поисково-познавательную активность и самостоятельность детей; путем наблюдения над словом вывести что долгий согласный звук на письме обозначается двумя одинаковыми буквами...
81113. Письмове додавання трицифрових чисел з переходом через розряд. Легенди про весняні квіти 37 KB
  Мета: пояснити прийом додавання трицифрових чисел з переходом через десяток; опрацювати складання задачі за коротким записом; вдосконалювати обчислювальні навички; розширити знання дітей про легенди. Обладнання: картки для усних обчислень, демонстраційні слайди, індивідуальні картки, маршрутна карта.
81114. Потреби у безпеці. Захист від стихійних лих, пожеж, злочинів. Допомога при нещасних випадках 40.5 KB
  Мета: Ознайомити учнів з потребами в безпеці, формувати вміння захищатися від небезпеки і надавати першу допомогу при нещасних випадках; розвивати логічне мислення, зв’язне мислення, зв’язне мовлення; виховувати взаємодопомогу, співчуття. Обладнання: зошит «Цікава економіка», картки, малюнки.
81115. Пізнай себе. Характер і здоров’я 36 KB
  Мета уроку: сформувати уявлення про якості особистості; сприяти пізнанню себе, своїх внутрішніх характеристик; виховувати бажання самовдосконалюватися; розвивати вміння контролювати свої емоції; навчитися виховувати позитивні риси характеру і вміння стримувати негативні.
81116. Places of interest in London 57.5 KB
  London is the capital of Great Britain. It is one of the most interesting places in the world. About eight million people live here. There is a big river in London – Thames. There are lots of Bridges over the river. Tower Bridge is the most famous. It is more than 100 years old.
81117. Конспект урока по обучению грамоте с использованием ИКТ. Буквы Ш, ш 946 KB
  Цели: познакомить с согласным звуком и буквами, активизировать словарный запас. Развивать речь, мышление, внимание, память, фонематический слух, познавательную активность. Воспитывать положительные черты личности.
81118. Засвоєння таблиці множення числа 8. Задачі на зведення до одиниці 29.38 KB
  Мета. Засвоїти таблицю множення числа 8, удосконалювати вміння розв’язувати задачі на зведення до одиниці, розвивати логічне мислення, увагу, виховувати інтерес до вивчення математики. Обладнання: таблиці для усної лічби, малюнки овочів.
81119. Корисні копалини в рідному краї 56.5 KB
  Діти а чи вмієти ви правильно сидіти за партою Покажіть мені як же потрібно сидіти за партою. Діти давайте перевіримо чи всі готові до нашого уроку Для уроку нам знадобляться підручник з природознавства зошит ручка олівець.
81120. Здоров’я дитини – радість родини 46 KB
  Мета. Ознайомити з поняттям здоров’я, здорові діти - радість родини. Розвивати у дітей активну життєву позицію, бажання бути здоровим: займатися фізкультурою, дотримуватися чистоти, гартувати своє тіло. Виховувати охайність.