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


 

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

36033. Предмет изучения стилистики 33.5 KB
  Существуют стилистика языка и стилистика речи лингвостилистика и литературоведческая стилистика стилистика от автора и стилистика восприятия стилистика декодирования и др. Стилистика языка исследует с одной стороны специфику языковых подсистем называемых функциональными стилями и подъязыками и характеризующихся своеобразием словаря фразеологии и синтаксиса и с другой стороны экспрессивные эмоциональные и оценочные свойства различных языковых средств. Стилистика речи изучает отдельные реальные тексты рассматривая каким образом...
36034. Глобальные экологические проблемы современности. Пути их преодоления. Концепция устойчивого развития 33 KB
  Концепция устойчивого развития 1 Утилизация радиоактивных отходов Решение:Новые ядерные технологии сконструированны таким системным научным методом согласованного взаимодействия единства противоположностей процессов синтезараспада становятся управляемыми и безотходными. Концепция устойчивого развития основывается на пяти основных принципах. Триединая концепция устойчивого развития объединение 3х основных точек зрения экономическая социальная экологическая. развития у недоминирующих культур.
36036. Политическая мысль эпохи Возрождения. Н. Макиавелли 31.5 KB
  Идеал 2х направлений: национально независимое суверенное госво в форме республики. В борьбе двух зарождавшихся идеологий либерализма и коммунизма победил либерализм и стал господствующей идеологией в 20 в. Он вводит понятие для определения госва stto госво это пол оргя обва а политика умение управлять. Определил предмет п науки учреждение государств сохранение и управление им создание армии ведение войны.
36037. ассортименту. Под номенклатурой понимается укрупненный перечень изделий предусмотренный планом к выполнен. 33.5 KB
  В начале строится таблица где весь V продукции структурирован по группам видам изделий. Шапка: вид продукции изделие А Б Объем продукции в оптимальных стабильных ценах в к плану единицы измерения оптимальной цены за ед. выпуск продукции в натуральном выражении план и факт выпуск продукции в стоим. 1 Кср =  объемов продукции которая пошла в зачет по номенклатуре  продукции по плану.
36038. Строение и функции клеточного ядра. Деление клеток эукариот. Митоз и мейоз 33 KB
  ДНК спирализуется передделением клетки для более точного распределения генетического материала при делении. Хранение генетической информации и передача ее дочернимклеткам в процессе деления. Митоз тип клеточного деления в результате которого дочерние клетки получают генетический материал идентичный тому который содержался в материнской клетке. Хромосомы спирализуются центриоли у животных клеток расходятся к полюсам клетки распадается ядерная оболочка исчезают ядрышки и начинает формироваться веретено деления.
36039. Формы изменчивости живых организмов. Рекомбинации и мутации 33 KB
  Хромосомные мутации возникают на основе хромосомных перестроек аберраций. Различают внутрихромосомные нехватки дупликации инверсии и межхромосомные транслокации обмен участками негомологичных хромосом иди фрагментов; геномные изменения чисел хромосомгаплоидия полиплоидия анеуплоидия; плазмовые изменения цитоплазматических наследственных структур. Комбинативная; причинами служат все виды скрещивания и гибридизации а также кроссинговер обмен генетическим материалом между гомологичными хромосомами родителей во время...
36040. Необходимость международного сотрудничества в области ООС 33 KB
  Поэтому в настоящее время государства под эгидой ООН или на двухсторонней основе организуют взаимодействие с целью охраны среды обитания человека растительного и животного мира. является специализированным учреждением ООН и занимается вопросами продовольственных ресурсов и раз вития сельского хозяйства в целях улучшения условий жизни народов мира. В соответствии с своей компетенцией она обращает внимание на охрану и рациональное использование земель водных ресурсов лесов и иной растительности животного мира суши биологических ресурсов...
36041. Иван Александрович Гончаров 33 KB
  Роман интересен тем что образ Ильи Ильича Обломова мы можем отождествлять с определенным типом людей живших в России в то время. Любовь их продолжается до тех пор пока Илье не приходится столкнуться с реальной жизнью пока от него не требуется решительных действий пока Ольга не понимает что она любит будущего Обломова. Ни дружба ни даже такая чистая искренняя любовь не смогли заставить Обломова отказаться от своих идеалов: мирной покойной беззаботной жизни плотной еды и безмятежного сна. Родители Обломова понимали важность и...