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


 

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

74212. Қол машиналары. Жалпы мәліметтер, қол машиналарын атқаратын қызметіне, жұмыс жасау принципіне, жұмыс органының қозғалыс сипаттамасына, жұмыс режиміне, жетек түрі мен қорғаныс класына қарай жіктеу 1.34 MB
  Жалпы мәліметтер қол машиналарын атқаратын қызметіне жұмыс жасау принципіне жұмыс органының қозғалыс сипаттамасына жұмыс режиміне жетек түрі мен қорғаныс класына қарай жіктеу. Қол машиналарын атқаратын қызметіне жұмыс жасау принципіне жұмыс органының қозғалыс сипаттамасына жұмыс режиміне жетек түрі мен қорғаныс класына қарай жіктеу. Қол машиналары дегеніміз жұмыс органы қозғалысқа қозғалтқыш арқылы ал қосымша қозғалыстары жеткізу оператордың көмегімен қолдан қозғалысқа келтірілетін машиналар аталынады. Жеңіл түріне тескіш...
74213. Машинаны техникалық эксплуатациялау» түсінігі. Машинаны эксплуатацияға қабылдау және тапсыру 21.03 KB
  Машинаны техникалық жөндеу жүйесі. Жалпы еңбек қауіпсіздігі талаптары Жоспар: Машинаны техникалық эксплуатациялау түсінігі. Машинаны техникалық жөндеу жүйесі.
74214. Құрылыс машиналарының азаматтық және өндірістік құрылыс жұмыстарындағы технологиялық процестерді автоматтандыру және механикаландырудағы алатын орны 23.1 KB
  Құрылыс машиналарының азаматтық және өндірістік құрылыс жұмыстарындағы технологиялық процестерді автоматтандыру және механикаландырудағы алатын орны. Құрылыс машиналары мен құрылыс өндірісіндегі механикаландыру мен автоматтандырудың дамуы. Құрылыс машиналарының қазіргі техникалық деңгейінің сипаттамасы және ары қарай даму перспективалары Жоспар: Кіріспе. Құрылыс машиналары мен құрылыс өндірісіндегі механикаландыру мен автоматтандырудың дамуы.
74215. Құрылыс өндірісін механикаландыру және автоматтандыру жарағы ретінде құрылыс машиналарына қойылатын талаптар 23.21 KB
  Құрылыс машиналарының жіктелуі. Құрылыс машиналарын күштік жұмысшы және жүру құрылғыларынан трансмиссиялар мен басқару жүйелерінен құралған жүйе ретінде жалпы құрылымдық схемасы. Құрылыс машиналарының кинематикалық схемалары Жоспар: Құрылыс өндірісін механикаландыру және автоматтандыру жарағы ретінде құрылыс машиналарына қойылатын талаптар.
74216. Тасымалдау машиналары. Құрылыс жүктерінің сипаттамасы. Тасымалдау машиналарының негізгі параметрлері, эксплуатациялық сипаттамалары, қолданылуы, конструктивті схемалары, жұмыс процесі және технологиялық мүмкіндіктері 1.31 MB
  Тасымалдау машиналарының негізгі параметрлері эксплуатациялық сипаттамалары қолданылуы конструктивті схемалары жұмыс процесі және технологиялық мүмкіндіктері Жоспар: Құрылыс жүктерінің сипаттамасы. Тасымалдау машиналарының негізгі параметрлері. Тасымалдау машиналарының қолданылуы.
74217. Жүккөтеру машиналарының жіктелуі. Әр типті крандардың қызмет көрсету аймағы. Негізгі параметрлері мен индексация жүйесі 4.35 MB
  Бас параметрі – жүккөтергіштігі. Сондай-ақ жүккөтергіш машиналар жұмыс жасау аймағымен, асымен, қуатымен, тірек күштерімен, жүк моментімен сипатталады.
74218. Биполярные транзисторы. Типы, структура, режимы. Модель Эберса - Молла 2.11 MB
  Условные обозначения обоих типов транзисторов рабочие полярности напряжений и направления токов показаны на рисунке. Режим отсечки оба pn перехода закрыты при этом через транзистор обычно идет сравнительно небольшой ток. По характеру движения носителей тока в базе различают диффузионные и дрейфовые биполярные транзисторы.
74219. Дифференциальные параметры биполярных транзисторов в схеме с общей базой 2.3 MB
  Дифференциальные параметры биполярных транзисторов в схеме с общей базой Основными величинами характеризующими параметры биполярного транзистора являются коэффициент передачи тока эмиттера α сопротивление эмиттерного rэ и коллекторного rк переходов а также коэффициент обратной связи эмиттер коллектор μэк. Из полученного соотношения следует что для эффективной работы биполярного транзистора pnp типа ток эмиттера Jэ должен быть в основном дырочным Jэp. По этой причине эмиттер биполярного транзистора должен быть легирован...
74220. Тиристоры. Феноменологическое описание ВАХ динистора 1.78 MB
  Тиристор – это полупроводниковый прибор с тремя и более рn переходами, вольтамперная характеристика которого имеет участок с отрицательным дифференциальным сопротивлением и который используется для переключения.