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


 

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

16056. Русское уголовное право 2.57 MB
  ББК 67.9928 Т 12 Составитель и ответственный редактор доктор юридических наук профессор Н.И. Загородников Рецензенты: кандидат юридических наук Л О. Иванов доктор юридических наук профессор Ф.М. Решетников Таганцев Н.С. Т 12 Русское уголовное право. Лекции. Часть...
16057. Описание предметов одежды и обуви следов повреждений и наложений как вещественных доказательств 278 KB
  МВД Украины Университет внутренних дел Н.Н. Тагаев Н.И. Козаренко ОПИСАНИЕ ПРЕДМЕТОВ ОДЕЖДЫ И ОБУВИ СЛЕДОВ ПОВРЕЖДЕНИЙ И НАЛОЖЕНИЙ КАК ВЕЩЕСТВЕННЫХ ДОКАЗАТЕЛЬСТВ Учебное пособие Под редакцией профессора А.Н. Ярмыша ...
16058. Акционерное право США и России. Сравнительный анализ 947.5 KB
  ОГЛАВЛЕНИЕ ВВЕДЕНИЕ. ББК 67.99295 С79 Сыродоева О.Н. Акционерное право США и России сравнительный анализ. М.: Издательство Спарк 1996.112 с. Сыродоева О.Н. магистр права Университет штата Виржиния США Для юристовпрактиков студентов и преподавателей ю...
16059. Устная речь следователя при осуществлении допросов на предварительном следствии с применением звуко- и видеозаписи 149 KB
  Устная речь следователя при осуществлении допросов на предварительном следствии с применением звуко и видеозаписи учебнопрактическое пособие / Калинингр. унт; Ю.И. Сучков. Калининград 1998. Методические указания и примерные образцы процессуальных документов пред...
16060. Правовые системы стран мира 7.59 MB
  Правовые системы стран мира: Энциклопедический справочник. – 3е изд. перераб. и доп. / Отв. ред. докт. юрид. наук проф. А.Я. Сухарев. – М: Издательство НОРМА 2003. Коллектив авторов: Решетников Ф.М. – доктор юридических наук Батлер У.Э. – доктор права Лондонского универси
16061. Патентознавство. Підручник 2.06 MB
  МІНІСТЕРСТВО ОСВІТИ І НАУКИ У КРАЇ і. І УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ Л.М. Сусліков В.С. Дьордяй ПАТЕНТОЗНАВСТВО Рекомендовано Міністерством освіти і науки України як навчальнометодичний посібник для студентів КИЇВ 2005 вищих навчальних закладів ...
16062. Заведомо незаконное задержание, вопросы квалификации 446.5 KB
  МИНИСТЕРСТВО ВНУТРЕННИХ ДЕЛ РОССИИ СИБИРСКИЙ ЮРИДИЧЕСКИЙ ИНСТИТУТ П.Л. Сурихин ЗАВЕДОМО НЕЗАКОННОЕ ЗАДЕРЖАНИЕ: вопросы квалификации Учебное пособие КРАСНОЯРСК 2003 ББК 00.000 Сури
16064. Адвокатура в Российской Федерации 2.01 MB
  Происходящая в России демократизация политической и экономической системы, конституционное провозглашение правового социального государства вызывает необходимость коренной реорганизации форм и методов деятельности...