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

 


 

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

2051. Основні прибиральні роботи в літній період 16.41 KB
  На початку літа клумби очищають від відцвілих рослин та прикрашають літніми сортами. Декоративні кущі періодично розчищають, підтримуючи задану форму.
2052. Основні прибиральні роботи в осінній період 16.45 KB
  Восени, крім щоденних прибиральних робіт, проводять підготовку до зимового періоду, прибирають осіннє листя, перекопують клумби, вдобрюють ґрунт.
2053. Прибиральні роботи 23.14 KB
  Висококваліфікований професійно підготовлений персонал, повноцінний інвентар, сучасні прибиральні матеріали, сучасні види прибиральних машин і механізмів. Важливим є правильний розподіл часу, що витрачається на прибиральні роботи.
2054. Поведінка обслуговуючого персоналу в підприємствах готельного типу 21.77 KB
  Для здійснення прибиральних робіт у приміщеннях житлових груп на підприємствах функціонують служби експлуатації номерного фонду. Найважливішою функцією цього підрозділу є підтримка необхідного рівня комфорту і санітарно-гігієнічного стану готельних номерів, а також приміщень загального користування
2055. Основы виброзащиты машин 316.5 KB
  Виброзащита - это совокупность методов и средств, уменьшающих вредное влияние вибраций. Создание виброзащитных устройств, позволяющих эффективно решать поставленные перед ними задачи при ограниченных массовых и геометрических характеристиках
2056. Изготовление колонн с помощью сварочных работ на заводе 597.86 KB
  Выбор и обоснование металла сварной конструкции. Выбор способа сварки и методов контроля качества сварных соединений. Расчет сварных швов, прикрепляющих планки к ветвям колонны. Энергосберегающие мероприятия при проектировании колонны.
2057. Создание автоматизированной системы для оптимизации процесса создания надежного программного обеспечения на языке JAVA 373.85 KB
  Разработать программное обеспечение, реализующее возможность комплексного тестирования программ на языке Java. Программная система должна быть представлена в виде десктопного приложения и обладать интуитивно понятным графическим интерфейсом пользователя(ГИП).
2058. Арифметические действия над многозначными числами 350.5 KB
  Сложение и вычитание многозначных чисел. Виды работ по формированию вычислительных навыков. Типичные ошибки при выполнении арифметических действий над многозначными числами, пути их предупреждения и исправления.
2059. Классификация и обозначение турбокомпрессоров 181.5 KB
  Цель работы: ознакомиться с классификацией и обозначением турбокомпрессоров, изучить принцип работы и основные части турбины и компрессора.