45527

В-дерево. Добавление и удаление элементо

Доклад

Информатика, кибернетика и программирование

Вдерево это сбалансированное дерево. Основной недостаток индексов в том что трудно вносить изменения а дерево упрощает внесение изменений а сбалансированность позволяет ускорить поиск. В основе Вдерева лежат следующие аксиомы: Вдерево порядка n содержит 2n ключей 2n1 ссылку; В дерево растет от листьев к корню; Путь от корня к листу содержит одно и тоже количество шагов; Каждый узел заполняется не менее чем на половину кроме корня.

Русский

2013-11-17

27.5 KB

0 чел.

В-дерево. Добавление и удаление элементов.

В-дерево – это сбалансированное дерево.

Основной недостаток индексов в том, что трудно вносить изменения, а дерево упрощает внесение изменений, а сбалансированность позволяет ускорить поиск.

В основе В-дерева лежат следующие аксиомы:

  •  В-дерево порядка n содержит 2n ключей 2n+1 ссылку;
  •  В –дерево растет от листьев к корню;
  •  Путь от корня к листу содержит одно и тоже количество шагов;
  •  Каждый узел заполняется не менее чем на половину, кроме корня.

Пример.

Пусть у нас есть дерево третьего порядка,  с ключами 12, 8, 4, 9, 6, 13, 14, 16,100, 10.

Приходит ключ 12, его заносим в корень

Приходит 8, 8 меньше 12

Приходит 4, места в корне нет, разбиваем на 2

Приходит 9, она больше 8, но меньше 12, 12 сдвигаем, перед ней записываем 9, приходит 6 она меньше 8, но больше 4, записываем ее после 4:

После того как придет 13, 14, 16, 100, 10  вид дерева будет следующим:


 

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

19525. Пропорциональный закон регулирования 341 KB
  Пропорциональный закон регулирования описывается следующим уравнением . Здесь: параметр настройки регулятора. заданное значение регулируемой координаты. Знак означает что регулятор включен в систему по принципу отрицательной обратной. Уравнение регулятора
19526. Интегральный закон регулирования 454.5 KB
  Интегральный закон регулирования описывается уравнением. Как видно из уравнения интегральным регулятором является интегрирующие звено с постоянной интегрирования которая является параметром настройки регулятора. Динамические характеристики: ; АФХ ; АЧХ ; ФЧХ ...
19527. Пропорционально-дифференцируемый (ПД - регулятор) 1014 KB
  Пропорционально-дифференцируемый ПД регулятор Представляет собой параллельное соединение пропорционально и дифференциальной составляющей. Динамические характеристики: С точки зрения качества переходных процессов ПД регулятора обладае...
19528. Пропорционально – интегральный регулятор (ПИ) 798 KB
  Пропорционально интегральный регулятор ПИ Динамические характеристики: Система с ПИ регулятором не дает статической ошибки. ПИ регулятор сочетает в себе достоинство обеих простейших составляющих. П составляющая обеспеч...
19529. Пропорционально – интегрально дифференцируемый регулятор (ПИД) 1.11 MB
  Пропорционально интегрально дифференцируемый регулятор ПИД АФХ АЧХ: ФЧХ ПИД регулятор сочетает в себе достоинства всех 3х составляющих. Высокое быстродействие П составляющей малая динамическая ошибка за счет воздействия по скорости и отсутст...
19530. Определение настроек регулятора методом расширенных частотных характеристик 1.15 MB
  Определение настроек регулятора методом расширенных частотных характеристик. При изучении условий устойчивости замкнутой системы по критерию Найквиста было отмечено что если разомкнутая система разомкнута и ее АФХ проходит через точку то замкнутая система будет...
19531. Определение настроек регулятора методом незатухающих колебаний 36.5 KB
  Определение настроек регулятора методом незатухающих колебаний. Суть метода заключается в нахождении критической настройками П регулятора при которой в замкнутой системе устанавливаются не затухающие колебания то есть система находится на границе устойчивости. На ...
19532. Цифровая обработка сигналов. Основные понятия 608.07 KB
  Лекция 1.Цифровая обработка сигналов. Основные понятия Введение В настоящее время методы цифровой обработки сигналов digital signal processing DSP находят все более широкое применение вытесняя постепенно методы основанные на аналоговой обработке. В данном курсе рассматрива...
19533. Преобразование Фурье и обобщенные функции 641.26 KB
  2 Лекция 2. Преобразование Фурье и обобщенные функции Вспомогательные утверждения Лемма. Справедлива формула 1 Доказательство. Хотя формула 1 хорошо известна мы приведем ее доказательство поскольку она является основой многих дальнейших выкл...