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


 

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

15616. ФИЛОСОФИЯ БЕЗОПАСНОСТИ СИБИРИ И ДАЛЬНЕГО ВОСТОКА РОССИИ В СВЕТЕ БОРЬБЫ ЦИВИЛИЗАЦИЙ 66 KB
  Философия безопасности Сибири и Дальнего Востока России в свете борьбы цивилизаций Переход к легальной рыночной экономике ускорил центробежные силы разрывающие Россию. Если на юге страны использовались военные и идеологические орудия развала государства то на Дал
15617. НОВАЯ ТЕОСОФИЯ КАК ФИЛОСОФИЯ ГЛОБАЛЬНОЙ БЕЗОПАСНОСТИ РОССИИ 133 KB
  НОВАЯ ТЕОСОФИЯ КАК Философия ГЛОБАЛЬНОЙ безопасности России Землетрясения и цунами вызвавшие радиоактивную катастрофу на Японских островах в марте 2011 г. свидетельствуют о начале глобальной природнотехногенной катастрофы. Кризис индустриальной цивилизации прояв...
15618. Принципы нравственной экономики 53 KB
  Принципы нравственной экономики Потребность в новой экономике обусловлена усиливающимся цивилизационным кризисом [1]. Методологической основой для создания концепции нравственной экономики может служить нравственнорелигиозный неоинституционализм разработанны
15619. КИТАЙСКИЙ, ИНДИЙСКИЙ И ЯПОНСКИЙ ПРОЕКТЫ ДЛЯ ГЕОПОЛИТИКИ И ГЕОЭКОНОМИКИ РОССИИ 218.5 KB
  КИТАЙСКИЙ ИНДИЙСКИЙ И ЯПОНСКИЙ ПРОЕКТЫ ДЛЯ ГЕОПОЛИТИКИ И ГЕОЭКОНОМИКИ РОССИИ Переход к легальной рыночной экономике ускорил центробежные силы разрывающие Россию. Если на юге страны использовались военные и идеологические орудия развала государства то на Дальнем
15620. Культура, кризис, этика и эстетика 38 KB
  Культура кризис этика и эстетика Темы для обсуждения предложены две: насчёт того переживает ли нынешняя культура кризис и вторая об этическом и эстетическом в современной культуре. Ничего существенного я не могу сказать ни на первую тему ни на вторую. Потому что ч...
15621. Das Prinzip verum factum: seine theologische Pramisse bei Nikolaus von Kues 41.5 KB
  Das Prinzip verumfactum: seine theologische Pramisse bei Nikolaus von Kues Das Tatsachlichkeit der Wahrheit heutzutage ist etwas dass versteht sich von selbst. Dass die Wahrheit gewissermassen erzeugt ist davon man sagt seitdem am Morgen der Philosophie war klargestellt dass obgleich die Wahrheit von sich selbst existiert denn seine Stellung in die Sprache in dem Urteil von Wahrheit ist. Das bei uns aus Latein angekommende Faktum hat vor langer Zeit derUntersch...
15622. Николай Кузанский и философия эпохи культуры 58 KB
  Николай Кузанский и философия эпохи культуры слишком обширная тема если считать что эпоха культуры это всё Новое время. Я попытаюсь эскизно очертить только один сюжет из этой большой темы правда он один из главных. Речь пойдёт об истоках новоевропейского г
15623. Бог был для мира не сим одним 109.5 KB
  Бог был для мира не сим одним Бог был для мира не сим одним не причиною только бытия но сотворил как благий полезное как премудрый прекраснейшее как могущественный величайшее Василий Великий. Беседы на Шестоднев.1 Всё дальнейшее будет попыткой комментария...
15624. Время событий и событие времени 43.5 KB
  Время событий и событие времени На последней странице Онтологии времени значится учебное издание. Я бы даже сказал учебное пособие. Для меня это учебное пособие по истории философии настоящее и одно из лучших и немногих при наличии кучи учебников плохих и хор...