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

 


 

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

45990. Проект по созданию и развитию интернет-подразделения в организации ООО “АСК-2” 236.29 KB
  Целью дипломной работы является изучение специфики и особенности интернет-бизнеса, основные проблемы в данной сфере, разработка интернет-подразделения в компании и оценка экономической целесообразности проекта.
45996. Сертифікація в зарубіжних країнах 196 KB
  У сертифікаті повинні бути вказані всі стандарти, дія яких поширюється на сертифіковану продукцію. Такий сертифікат повинен супроводжувати продукцію або бути переданим оптовому чи роздрібному продавцеві, до якого надійшла дана продукція.