47317

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

Доклад

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

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

Русский

2014-03-31

49.19 KB

4 чел.

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

 


 

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

19521. Амплитудно фазовый критерий Найквиста 3.26 MB
  Амплитудно фазовый критерий Найквиста. АФ критерий Найквиста позволяет оценить устойчивость системы с отрицательной обратной связью то есть замкнутый по найденной экспериментальной или из передаточной функции АФХ разомкнутой системы. Рассмотрим замкнутый контур....
19522. Показатели качества переходных процессов 1.78 MB
  Показатели качества переходных процессов. Процессам управления представляют следующие основные требования по точности установившихся режимов по устойчивости и по качеству переходных процессов. Устойчивость САУ то есть затухание протекающих в ней процессов явля
19523. Интегральные критерии качества 1.75 MB
  Интегральные критерии качества. Интегральный критерий дает обобщенную оценку качество переходного процесса одну из достоинств интегральных критериев в том что для их определения не обязательно строить график переходного процесса что иногда является затруднительны...
19524. Расширенные частотные характеристики 1.3 MB
  Расширенные частотные характеристики. При разработки САУ критерия качества применяют не только для оценки готовых систем но их используют на стадии разработки вводя в расчеты и тогда параметры системы получают с учетом определенных требований. Наиболее удобным пока...
19525. Пропорциональный закон регулирования 341 KB
  Пропорциональный закон регулирования описывается следующим уравнением . Здесь: параметр настройки регулятора. заданное значение регулируемой координаты. Знак €œ€ означает что регулятор включен в систему по принципу отрицательной обратной. Уравнение регулятора
19526. Интегральный закон регулирования 454.5 KB
  Интегральный закон регулирования описывается уравнением. Как видно из уравнения интегральным регулятором является интегрирующие звено с постоянной интегрирования которая является параметром настройки регулятора. Динамические характеристики: ; АФХ ; АЧХ ; ФЧХ ...
19527. Пропорционально-дифференцируемый (ПД - регулятор) 1014 KB
  Пропорционально-дифференцируемый ПД регулятор Представляет собой параллельное соединение пропорционально и дифференциальной составляющей. Динамические характеристики: С точки зрения качества переходных процессов ПД – регулятора обладае...
19528. Пропорционально – интегральный регулятор (ПИ) 798 KB
  Пропорционально – интегральный регулятор ПИ Динамические характеристики: Система с ПИ – регулятором не дает статической ошибки. ПИ регулятор сочетает в себе достоинство обеих простейших составляющих. П составляющая обеспеч...
19529. Пропорционально – интегрально дифференцируемый регулятор (ПИД) 1.11 MB
  Пропорционально – интегрально дифференцируемый регулятор ПИД АФХ АЧХ: ФЧХ ПИД регулятор сочетает в себе достоинства всех 3х составляющих. Высокое быстродействие П составляющей малая динамическая ошибка за счет воздействия по скорости и отсутст...