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

 


 

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

53346. Історичне значення запровадження християнства 48.5 KB
  Історичне значення запровадження християнства Очікуванні результати: визначити історичні корені хрещення Київської Русі; визначити значення хрещення для історії держави та людства; розвивати вміння логічного мислення; порівнювати історичні факти; впроваджувати в практику щоденного життя моральноетичні і духовні цінності християнства; виховувати повагу до історичних постатей та православної віри. Тип уроку: комбінований Форма уроку: урокподорож Обладнання: відеофільм Хрещення Русі портрет В. Великий почав князювати Яку...
53347. Основні принципи будови та функціонування World Wide Web, протокол НТТР, адресація в мережі 395.5 KB
  Для учнів які мають уявлення про мову HTML: розшукати історичні відомості про мову НТМL. Але для того щоб створити Webсторінку необхідно знати мову гіпертекстової розмітки тобто HTML. Отже тема уроку: âСтворення структури HTML документа. На попередньому уроці учням було завдання відшукати історичну довідку про створення мови HTML.
53349. Берегиня вроди – хустка 219 KB
  Впродовж століть хустка була на Україні найдорожчим подарунком який уособлював для кожної людини рідну Україну рідний дім рідну матір. Де ж вона сьогодні щира українська хустка що її серед тисячі інших вирізняє щось невимовно рідне Де весела та барвиста хустка щедро оспівана в народних піснях та іграх Хочеться щоб вона сьогодні стала не просто модною деталлю на деякий час а одним з національних символівоберегів. І учениця: Українська хустка з давніхдавен це основний і улюблений головний убір української молодиці.
53351. ХВИЛИНКИ КАЛІГРАФІЇ НА УРОКАХ УКРАЇНСЬКОЇ МОВИ 62 KB
  Поясніть правопис слова весна. Що означає слово купава Чи є тут слова вжиті в переносному значенні Опишіть образ весни яку ви побачили. Чи зрозуміли ви про що йдеться у вірші Знайдіть слова з ненаголошеними голосними. Назвіть слова правопис яких слід перевірити за словником.
53352. Різноманітність хвойних рослин. Значення в природі та житті людини 68.5 KB
  Мета: Продовжити формувати наукову картину живої природи на прикладі різноманітності хвойних. Ознайомити учнів із різноманітними представниками класу Хвойних особливостями їх поширення. Сприяти формуванню в учнів наукового світогляду на основі знань про різноманітність хвойних.
53353. Різноманітність та значення хвойних рослин 36 KB
  Тема уроку: Різноманітність та значення хвойних рослин. Тип уроку: комбінований Форма уроку: ділова гра Обладнання і матеріали: таблиці фотоілюстрації і малюнки що ілюструють різноманітність і значення голонасінних гербарій шишки і живі гілочки представників хвойних рослин динамічна схема Розмноження сосни картини викладені бурштином картки для опитування довідки учнів рекомендована література. Особливості будови і значення хвойних ми вивчимо сьогодні а зараз згадаємо Питання для бесіди: Які ознаки характерні для...
53354. Я ЛЮБЛЮ УКРАЇНУ! 317.5 KB
  Ми живемо в Україні, в краю, невимовно багатому на чарівні кольори і краєвиди, на дивовижні пісні, на чудову милозвучну мову, якою можна передати все на світі, описати красу і велич рідного краю. Рідною українською мовою можна висловити найпотаємніші почуття і думи, мрії кожної людини.