Введение. На тему: «Фибоначчиева куча».

Реферат

На тему: «Фибоначчиева куча».

Студент: Самойленко Евгений Павлович

Преподаватель: Добрынин Владимир Юрьевич

Санкт-Петербург

Оглавние:

Введение

2. Что такое двоичное дерево?

3. Что такое куча?

4. Что такое асимптотический анализ?

Фибоначчиева куча.

Используемая литература.

Введение.

Итак, моя тема – Фибоначчиевы кучи. Тема эта не была изучена мною раньше, поэтому мне пришлось окунуться в изучение ее с самого начала. Для полного понимания происходящего мне сначала понадобилось узнать:

· Что такое двоичное дерево, как оно выглядит и где ее используют;

· Что такое куча, для чего её используют;

· Что такое Асимптотический анализ.

И уже потом Я узнал, что же такое Фибоначчиева куча.

Что такое Двоичное Дерево?

«Двои́ чное де́ рево — древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками». (с) Википедия

Применение:

· Двоичное дерево поиска

· Дерево Фибоначчи

· Двоичная куча

Для того чтобы лучше понять, что же такое Двоичное дерево, мне понадобилось рассмотреть пример реализации Д воичного Д ерева П оиска (ДДП).

Итак, реализация ДДП:

Суть ДДП заключается в разбиении полей на левую и правую часть таким образом, что с лева находятся все элементы меньше корня, а справа – больше (рис. 1).

Рис. 1

Следующий пример (рис. 2) Двоичным Деревом Поиска не является.

Рис. 2

Столь яркий пример, и информация позаимствованы с этого сайта.

. Что такое куча(heap)?

«В компьютерных науках ку́ ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B) => элемент с наибольшим ключом всегда является корневым узлом кучи.» (С) Википедия.

Применение:

· 2-3 куча

· Двуродительская куча

· Двоичная куча

· Биноминальная куча

· Очередь Бродала

· Спаренная куча

· Фибоначчиева куча.

Как же я сам понял, что такое куча? Ответ на этот вопрос легко и просто пришел в мою голову после примера «Биноминальная куча» - биноминальная куча отвечает двум простым правилам (рис. 3):

· Ребенок не должен превышать по значению своего родителя.

· Все биноминальные деревья имеют разный размер.

Рис. 3