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


 

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

15562. Реклама табака, табачных изделий и курительных принадлежностей 52.5 KB
  23. Реклама табака табачных изделий и курительных принадлежностей1. Реклама табака табачных изделий и курительных принадлежностей в том числе трубок кальянов сигаретной бумаги зажигалок и других подобных товаров не должна:1 содержать утверждение о том что курение им
15563. Реклама лекарственных средств, медицинской техники, изделий медицинского назначения и медицинских услуг, в том числе методов лечения 54.5 KB
  24. Реклама лекарственных средств медицинской техники изделий медицинского назначения и медицинских услуг в том числе методов лечения1. Реклама лекарственных средств не должна:1 обращаться к несовершеннолетним;2 содержать ссылки на конкретные случаи излечения от забол...
15564. Реклама биологически активных добавок и пищевых добавок, продуктов детского питания 25 KB
  25. Реклама биологически активных добавок и пищевых добавок продуктов детского питания1. Реклама биологически активных добавок и пищевых добавок не должна:1 создавать впечатление о том что они являются лекарственными средствами и или обладают лечебными свойствами;2 со
15565. Реклама продукции военного назначения и оружия 53.5 KB
  26. Реклама продукции военного назначения и оружия1. Не допускается реклама:1 продукции военного назначения за исключением рекламы такой продукции в целях осуществления военнотехнического сотрудничества Российской Федерации с иностранными государствами;2 оружия не ук...
15566. Реклама основанных на риске игр, пари 50 KB
  27. Реклама основанных на риске игр пари1. Реклама основанных на риске игр пари не должна:1 обращаться к несовершеннолетним;2 создавать впечатление что участие в основанных на риске играх пари является способом заработка или получения иного дохода либо иным способом пол
15567. Реклама финансовых услуг 138.5 KB
  28. Реклама финансовых услуг1. Реклама банковских страховых и иных финансовых услуг должна содержать наименование или имя лица оказывающего эти услуги для юридического лица наименование для индивидуального предпринимателя фамилию имя отчество.2. Реклама банковски...
15568. Реклама ценных бумаг 63 KB
  29. Реклама ценных бумаг1. Не допускается реклама ценных бумаг предложение которых неограниченному кругу лиц не предусмотрено федеральными законами и иными нормативными правовыми актами Российской Федерации.2. Не допускается реклама имущественных прав не удостоверенны
15569. Реклама услуг по заключению договоров ренты, в том числе договора пожизненного содержания с иждивением 19 KB
  30. Реклама услуг по заключению договоров ренты в том числе договора пожизненного содержания с иждивением1. Реклама услуг по заключению договоров ренты в том числе договора пожизненного содержания с иждивением не должна содержать:1 выражение благодарности физическими л...
15570. Реклама деятельности медиаторов по обеспечению проведения процедуры медиации 21 KB
  30.1. Реклама деятельности медиаторов по обеспечению проведения процедуры медиации1. Реклама деятельности медиаторов по обеспечению проведения процедуры медиации не прошедших соответствующего профессионального обучения и не имеющих подтверждающих такое обучение докум...