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  вид дерева будет следующим:


 

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

16242. ПРОЕКТИРОВАНИЕ И АНАЛИЗ ЭЛЕКТРИЧЕСКИХ СХЕМ 462.5 KB
  ПРОЕКТИРОВАНИЕ И АНАЛИЗ ЭЛЕКТРИЧЕСКИХ СХЕМ Методические указания для выполнения лабораторных работ по дисциплинам Автоматизация проектирования Основы автоматизированного проектирования Лабораторная работа № 1 Разработка графических моделей ...
16243. ВЕЛ про поліпшення питного водопостачання та охорони вод в Україні 122 KB
  ВЕЛ про поліпшення питного водопостачання та охорони вод в Україні. Вода найцінніший природний ресурс. Вода основа життя вона відіграє виняткову роль у процесах обміну речовин без яких життя не можливе. Загальні запаси води на земній кулі становлять близько 1390 м...
16245. Интерфейс Adobe Photoshop. Работа с документом 948.87 KB
  Лабораторная работа № 1 Интерфейс Adobe Photoshop. Работа с документом Открытие документов в Photoshop Запустите графический редактор Photoshop Пуск → Программы → Adobe Photoshop CS2. В меню File Файл выберите команду Open Открыть. В появившемся диалоговом окне Open Открыть
16246. Изучение выпрямителей и стабилизаторов напряжения 55.5 KB
  Лабораторная работа № 11 Изучение выпрямителей и стабилизаторов напряжения 11.1. Цель работы Изучение различных схем выпрямителей и линейных стабилизаторов напряжения. 11.2. Порядок выполнения работы 11.2.1. Для исследования двухполупериодного выпрямите
16247. Созданоие приложения визуализирующего работу cash-памяти в 3-х архитектурах 200.5 KB
  Содержание: Краткая информация о процессорах семейства х-86. Кэш-память Архитектура кэш-памяти Кэш-память с прямым отображением Полностью ассоциативная архитектура Наборно-ассоциативн...
16248. Эмуляция работы программы FDisk 471 KB
  Курсовой проект по по информатике Тема: Эмуляция работы программы FDisk Краткие теоретические сведения. Конструкция HDD Рис. 1 Диск представляет собой круглую металлическую пластину с очень ровной поверхностью покрытую тонким ферро...
16249. Конфигурация функции IGMP Snooping 724.66 KB
  Лабораторная работа №1 Конфигурация функции IGMP Snooping 1 Цель работы 1.1Научиться конфигурировать протокол управления групповой multicast рассылкой на коммутаторах Dlink. 2 Литература 2.1 Смирнова Е.В. Пролетарский А.В. Баскаков И.В. Федотов Р.А. Построение комму
16250. Создание профиля многоадресной рассылки 724.41 KB
  Лабораторная работа №2 Создание профиля многоадресной рассылки 1 Цель работы 1.1 Научиться управлять multicast трафиком. 2 Литература 2.1 Смирнова Е.В. Пролетарский А.В. Баскаков И.В. Федотов Р.А. Построение коммутируемых компьютерных сетей: учебное пособие. ...