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

 


 

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

70185. Экономико-математическое моделирование комплекса противоэрозионных мероприятий 186 KB
  Цель данной курсовой работы научиться строить экономико-математические модели по проектированию комплексов противоэрозионных мероприятий. Все элементы комплекса противоэрозионных мероприятий должны быть взаимно согласованы.
70186. Разработка нового туристского продукта – посещение иностранными гостями международной выставки вооружений и военной техники 152.5 KB
  Так называемые инсентив-туры давно практикуемые за рубежом и пользующиеся все большей популярностью в России предполагают не только корпоративный отдых как форму поощрения но и решение такой важной задачи внутрифирменного управления как сплочение членов трудового коллектива...
70187. ТЕХНОЛОГИЯ ПЕРЕВОЗКИ ГРУЗОВ И УПРАВЛЕНИЕ РАБОТОЙ ФЛОТА 838.5 KB
  В исходных данных для выполнения курсовой работы задаются: наименование судна направления перевозок два отдельных рейса род перевозимого груза дата начала рейсов. Предполагается что по окончании рейса судну предложено осуществить перевозку груза на одном из двух заданных направлений.
70189. Определение состава газовой фазы и окисляемости металлов при термообработке оксидного катода 594.94 KB
  В процессе откачки ЭВП наибольшее газовыделение происходит на этапе термообработки оксидного катода. Оксидное покрытие наносится на поверхность металлического керна катода (Mn) в виде суспензии карбонатов щелочноземельных металлов.
70190. ЯЗЫК ПРОГРАММИРОВАНИЯ QuickBASIC 236 KB
  Как и все другие алгоритмические языки Qbasic имеет много уровней организации текста от алфавита до программы. Прежде чем описывать синтаксические правила построения конструкций языка и приводить сведения по процедурам и функциям перечислим его структурные элементы от нижнего уровня к верхнему.
70191. ЯЗЫК ПРОГРАММИРОВАНИЯ QBASIC 618.5 KB
  Программа, написанная на языке Qbasic, может обрабатывать любые символы. Но это не значит, что каждый из них может использоваться в тексте программы для обеспечения действий или объектов программы. При вводе текста программы можно использовать как прописные, так и строчные буквы.
70193. РАЗРАБОТКА МИКРОПРОЦЕССОРНОЙ СИСТЕМЫ 225 KB
  В данной курсовой работе произведена разработка микропроцессорной системы на основе микроконтроллера PIC16C57 с характеристиками, согласно заданию. Произведена разработка функциональной и структурной схем. Приведена информация о выбранных элементах структурной схемы.