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

 


 

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

25610. Кровяные пластинки 47 KB
  Количество их в крови от 20 109 л до 40 109 л. При окраске мазков крови азур 2эозином в кровяных пластинках выявляются более светлая периферическая часть гиаломер и более темная зернистая часть грануломер структура и окраска которых могут варьировать в зависимости от стадии развития кровяных пластинок. Гликопротеин PIb является рецептором для находящегося в плазме фактора фон Виллебранда vWF одного из ключевых механизмов свертывания крови. Гликопротеин PIIbIIIa рецептор фибриногена; участвует в аггрегации кровяных...
25611. Мембраны клеток 32 KB
  состав: липиды 40 и белки 60 ; кроме того во многих мембранах обнаружены углеводы 5 10 . Многие мембранные белки состоят из двух частей участков с полярными аминокислотами и участков с неполярными: глицином аланином валином лейцином. Такие белки в липидных слоях мембран располагаются так что их неполярные участки как бы погружены в жирную часть мембраны где находятся гидрофобные участки липидов. Эти белки как бы пронизывают мембрану их называют интегральными белками мембран.
25612. Цитоплазма. Органеллы 29.5 KB
  Гиалоплазма матрикс цитоплазмы представляет собой истинную внутреннюю среду клетки. В ней при участии рибосом и полисом происходит синтез белков необходимых для собственно клеточных нужд для поддержания и обеспечения жизни данной клетки. Осмотические и буферные свойства клетки в значительной степени определяются составом и структурой гиалоплазмы. Например: клетки панкреатической железы.