47317

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

Доклад

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

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

Русский

2014-03-31

49.19 KB

8 чел.

Особенности дерева Фибоначчи, удаление вершины из 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 - поворотов.

 


 

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

17962. Предмет, метод и система финансового права 115.5 KB
  ЛЕКЦИЯ 2 Предмет метод и система финансового права 1. Понятие финансового права. 2. Место финансового права в системе права. 3. Понятие и виды финансовоправовых норм. 4. Финансовоправовые отношения их особенности. 5. Система финансового права. 6. Исто...
17963. Правовые основы финансового контроля в Украине 132 KB
  ЛЕКЦИЯ 3 Правовые основы финансового контроля в Украине 1. Сущность и назначение финансового контроля. 2. Организация и органы финансового контроля. 3. Формы и методы финансового контроля. 1. Сущность и назначение финансового контроля Контроль за ра
17964. Государственный бюджет Украины и бюджетное право 175.5 KB
  ЛЕКЦИЯ 4 Государственный бюджет Украины и бюджетное право . 1. Понятие бюджета и его роль в обществе. 2. Понятие бюджетного права и его источники. 3. Бюджетноправовые отношения в обществе. 4. Бюджетная система. 5. Бюджетная классификация. 6. Государствен...
17965. Бюджетный процесс в Украине и его участники 447.5 KB
  ЛЕКЦИЯ 5 Бюджетный процесс в Украине и его участники 1. Понятие и содержание бюджетного процесса. 2. Распорядители бюджетных средств и бюджетные назначения. 3. Порядок составления проекта государственного бюджета Украины. 4. Порядок рассмотрения и принят...
17966. Основы правового регулирования государственных доходов 51 KB
  ЛЕКЦИЯ 6 Основы правового регулирования государственных доходов 1. Понятие и система государственных доходов Государственные доходы это совокупность денежных отношений по формированию финансов государства путем распределения и перераспределения валово...
17967. Налоговое право. Общегосударственные сборы 1.03 MB
  ЛЕКЦИЯ 7 Налоговое право 1. Понятие налогового права. 2. Государственные налоги. 3. Общегосударственные сборы обязательные платежи. 4. Правовая природа местных налогов и сборов. 5. Порядок осуществления расчетов плательщиков налогов перед бюджетом и го
17968. Правовые основы государственного кредита 201 KB
  ЛЕКЦИЯ 8 Правовые основы государственного кредита 1. Понятие и функции государственного кредита. 2. Виды государственного кредита. 3. Государственный кредит в Украине. 4. Правоотношения Украины с иностранными государствами и международными финансовокреди
17969. Правовые основы страхования 168 KB
  ЛЕКЦИЯ 9 Правовые основы страхования 1. Понятие и функции страхования. 2. Основные отрасли и виды страхования. 3. Отношения в сфере страхования регулирующие финансовым правом. 1. Понятие и функции страхования Экономика это хозяйственная система ко...
17970. Правовое регулирование государственных расходов в Украине 76 KB
  ЛЕКЦИЯ 10 Правовое регулирование государственных расходов в Украине 1. Понятие государственных расходов их особенности и принципы финансирования. 2. Правовые основы сметнобюджетного финансирования. 1. Понятие государственных расходов их особенности и прин