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

 


 

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

71718. ОПРЕДЕЛЕНИЕ ПЛОТНОСТИ ГРУНТА ЕСТЕСТВЕННОЙ (НЕНАРУШЕННОЙ) СТРУКТУРЫ И ЕГО ВЕСОВОЙ ВЛАЖНОСТИ 60.5 KB
  Эта характеристика используется при проектировании фундаментов для определения расчетного давления на основание напряжений от собственного веса грунта давления на ограждающие конструкции при расчете устойчивости откосов и т.
71719. ОПРЕДЕЛЕНИЕ ПОКАЗАТЕЛЕЙ ПЛАСТИЧНОСТИ 179 KB
  В качестве показателей пластичности используется два предела: нижний влажность грунта на границе раскатывания WP когда в грунте такое количество воды что он находится на границе перехода из пластичного состояния в твердого; верхний влажность грунта на границе текучести WL на границе...
71720. ОПРЕДЕЛЕНИЯ ПЛОТНОСТИ СЛОЖЕНИЯ И ВОДОПРОНИЦАЕМОСТИ ПЕСЧАНЫХ ГРУНТОВ 150.5 KB
  От плотности сложения песка зависят его строительные свойства, в том числе статическая и динамическая устойчивость, деформативность, водопроницаемость и т.д. Так, например, если песок в рыхлом состоянии, то он может быть использован в качестве основания только после его уплотнения или скрепления.
71721. Физические основы низкочастотной электротерапии 203 KB
  Раздражение электрическим током определенного характера и силы у большей части органов и тканей вызывает такую же реакцию, как и естественное возбуждение. Кроме того, это воздействие можно строго дозировать как по силе, так и по времени. Это широко используется в физиологии и медицине.
71722. Физические основы высокочастотных электрических методов, применяемых в медицине 320.5 KB
  На опыте убедиться в эффективности действия электрического поля ультравысокой частоты и высокочастотного магнитного поля на хорошо проводящие электролит и плохо проводящие дистиллированная вода структуры. Действие магнитного поля на движущийся заряд.
71723. Физические свойства ЭКГ 430.5 KB
  Задача электрокардиографии заключается в том чтобы оценить работу сердца электрические процессы в сердце по биопотенциалам регистрируемым с поверхности тела человека. Эти импульсы возникают в проводящей системе сердца которая состоит из синусного узла атриовентрикулярного узла и пучка Гиса.
71724. Физические основы электропроводности биологических тканей при постоянном токе. Лечебный электрофорез и гальванизация 239 KB
  Изучить физические основы применения постоянного электрического тока с лечебной целью. Чем объясняется нарушение закона Ома при прохождении постоянного тока через биологическую ткань С чем связывают первичное действие постоянного тока Почему у анода и катода возбудимость клетки разная.
71725. Изучение импеданса живой биологической ткани 201 KB
  Изучить зависимость импеданса биологической ткани от частоты переменного тока. Определить сдвиг фаз между силой тока и напряжением при прохождении переменного тока через живую ткань. Вопросы входного контроля Что такое электрический ток Что является носителями тока в проводниках...
71726. Определение динамического коэффициента вязкости. Определение коэффициента поверхностного натяжения 465 KB
  Какие режимы течения жидкости существуют Объясните возникновение силы внутреннего трения. Напишите уравнение Ньютона для течения вязкой жидкости. Как зависит вязкость жидкости от температуры Что такое ньютоновские и неньютоновские жидкости Запишите формулу Пуазейля проанализируйте ее.