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


 

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

15038. Жырау мен жыршылдық дәстүрдің Қазақ әдебиетіндегі қалыптасуы 52.5 KB
  ӘОЖ 378.147:8.0 ЖЫРАУ МЕН ЖЫРШЫЛЫҚ ДӘСТҮРДІҢ ҚАЗАҚ ӘДЕБИЕТІНДЕГІ ҚАЛЫПТАСУЫ А.Мұқашева Г.Мейірбекова Тараз мемлекеттік педагогикалық институты Тараз қ. Тарих қашан да өз перзенттерінің құнды мұраларымен қымбат әрі барлық кезеңдердің сарапшысы.Ерлігі м...
15039. Зар заман ақындарының (Дулат, Шортанбай, Мұрат) шығармаларындағы идеялық ерекшеліктер 42.5 KB
  ӘОЖ 323 001 574 ХІХ ҒАСЫРДЫҢ ІІ ЖАРТЫСЫНДАҒЫ ҚАЗАҚ ӘДЕБИЕТІНДЕГІ ЗАР ЗАМАН ӨКІЛДЕРІ Қ.С. Қожабекова Тараз мемлекеттік педагогикалық институты Тараз қ. Қазақ әдебиетіндегі байырлық рух ХVІІІ ғасырда жоңғарлар мен қарсы күресте ХІХ ұлт азаттық күресте Мах...
15040. Ілияс Есенберлиннің тарихи романдары 63 KB
  ІЛИЯС ЕСЕНБЕРЛИН 1915-1983 Ілияс Есенберлин 1915 жылы Ақмола облысындағы Атбасар қаласында туған. 1940 жылы Қазақ таукен институтын бітірген. Ұлы Отан соғысына қатысқан. Соғыстан кейінгі жылдарда филармонияны Жазушы баспасын басқарады т.б. жұмыстар атқарады. Жазушы ...
15041. Ілияс Жансүгіровтің Жетісу суреттері өлеңін оқытудағы ерекшеліктер 48.5 KB
  Ілияс Жансүгіровтің Жетісу суреттері өлеңін оқытудағы ерекшеліктер немесе қазақ поэзиясындағы ұлы жаңалық Б.О.Есімбекова Алматы қаласы Ілияс Жансүгіров Жетісу губерниясының Қапал уезі Ақсу болысы 4ауылында 1894 жылы 14 мамырда дүниеге келген. Анасынан 4
15042. Ілияс Жансүгіровтың Күйші поэмасы 48 KB
  Ілияс Жансүгіровтың Күйші поэмасы Қазақ поэзиясында бүгінге дейін өнер жайында көп жазған және көркемдіктің шыңына жеткізе жазған І.Жансүгіров пен теңдесер қаламгер жоқ. Сонау 20жылдардың бас кезінде өмірге келген Әнші өлеңінен басталған бұл тақырып тек қазақ әде
15043. Кел, жастар, біз бір түрлі жол табалық 113.02 KB
  Кел жастар біз бір түрлі жол табалық.... Шәкәрім Шаһкәрім Құдайбердіұлы өмірі мен шығармашылығын өз бетімен ізденіске бағыттап қосымша материалдарды пайдалану арқылы оқыту тәжірибесінен Көмекші оқуәдістемелік құрал Шаһкәрім Шәкәрім Құдайбердіұлы ө...
15044. Кітапханашылар байқауы 95 KB
  Шығыс Қазақстан облыстық балалар және жасөспірімдер кітапханасы ММ Ұымдастырушылық әдістемлік бөлім Өскемен қ. 2007 Оқысаң ұшасың Пауло Коэльо Құрметті оқырмандар Балаларға оқу бақытын сыйлайық байқауына ...
15045. Көне Грек әдебиетінің архаикалық кезеңі 67.5 KB
  Көне Грек әдебиетінің архаикалық дәуірі Антикалык әдебиет курсының пәні – көне грек және рим құлиеленушілік қоғамдарының әдебиеті. Антик антикалық деген термин antiquus деген латын сөзінен туған. Оның мағынасы ежелгі ертедегі көне болады. Антикалық әдебиет...
15046. Көне Рим әдебиеті 53 KB
  Көне Рим әдебиеті Б.д.д. ІІІ ғ. ортасында Жерорта теңізінің батыс жағалауында Италияда антикалық әдебиеттің екінші бөлігі – рим әдебиеті өркендей бастайды. Рим әдебиеті грек әдебиетімен байланысты болды. Рим әдебиеті грек әдебиетімен бірге дамыған бірақ о