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

 


 

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

74945. Умножение многозначного числа на однозначное число 447 KB
  Цели: продолжать знакомить учащихся с приёмом письменного умножения многозначного числа на однозначное число; совершенствовать устные и письменные вычислительные навыки; развивать умение решать задачи; закреплять умение рассуждать делать выводы.
74946. Правило обчислення площі прямокутника та його застосування. Знаходження значень виразів на сумісні дії 162 KB
  Мета: повторити поняття «площа» та «квадратний сантиметр»; навчити користуватись правилом обчислення площі; проводити роботу, спрямовану на запобігання змішувань понять «площа» і «периметр»; розвивати логічне мислення, пам’ять; виховувати організованість і дисципліну розумової праці дітей.
74947. Дроби. Вершки и корешки 138.5 KB
  Деление на команды Все вы знаете русскую народную сказку Вершки и корешки. Мы разделимся на команды Вершки и Корешки. Команды это I и II вариант. Сейчас проведем тендер конкурс на право выбора названия варианта-команды: команда числителя Вершки и команда знаменателя Корешки.
74949. Заміна одних одиниць вимірювання величин іншими. Розв’язування задач на дві дії та складання обернених задач 129.5 KB
  Заміна одних одиниць вимірювання величин іншими. Формувати вміння використовувати набуті знання для заміни одних одиниць вимірювання величин іншими. Познайомити учнів зі старовинними одиницями вимірювання довжини і маси.
74950. Розв’язування задач на знаходження швидкості, часу та відстані 92 KB
  Мета: Ознайомити учнів зі способами визначення відстані, швидкості та часу; за допомогою пилки» формувати вміння розв’язувати задачі на основі творчих видів роботи; розвивати обчислюванні навички.
74951. Повторення вивченого «Нумерація чисел від 21 до 100» 45 KB
  Кожен герой мультика приготував для вас своє завдання. Увага відгадайте герої якого мультфільму пропонують вам перше завдання звучить пісня Ю. Щоб нікого не образити ми виконаємо і те і те завдання. Фрагмент пісні з Бременських музикантів готові малюнки кожної тварини яка буде пропонувати завдання.
74952. Розв’язування задач на зведення до одиниці. Вправи на засвоєння таблиці множення числа 8. Розпізнання многокутників 32.5 KB
  Удосконалювати вміння учнів розвязувати задачі на зведення до одиниці; домогтися засвоєння таблиці множення числа 8 напамять; закріплювати знання правил порядку дій; розвивати обчислювальні навички та вміння розвязувати рівняння...
74953. Письменное вычитание трёхзначных чисел. Сложные задачи – цена, количество, стоимость. Геометрический материал 188.5 KB
  Цель: Учить детей письменному вычитанию трехзначных чисел столбиком; закрепить умение делать правильный мотивированный выбор действия в задаче; выбирать арифметическое действие для решения задачи; составлять равенства на умножение деление; классифицировать и обобщать.