У следећем туторијалу научићемо о структури података Б стабла и размотрити њено визуелизовање.
Дакле, хајде да почнемо.
Шта је Б дрво?
Тхе Б Дрво је посебан тип вишесмерног стабла претраге , опште познат као М-пут дрво, које се балансира. Због своје уравнотежене структуре, ова стабла се обично користе за рад и управљање огромним базама података и поједностављење претраживања. У Б стаблу, сваки чвор може имати највише н подређених чворова. Б стабло је пример вишестепеног индексирања у систему за управљање базом података (ДБМС). Лист и унутрашњи чворови ће имати референце записа. Б стабло је познато као балансирано ускладиштено дрво јер су сви чворови листа на истом нивоу.
Следећи дијаграм је пример Б дрвета:
Слика 1. А Б Дрво са редоследом 3
Разумевање правила Б дрвета
Следеће су важне особине Б дрвета:
- Сви чворови листа су на истом нивоу.
- Структура података Б стабла је дефинисана термином минимални степен 'д'. Вредност 'д' зависи од величине блока диска.
- Сваки чвор, осим корена, мора да се састоји од најмање д-1 кључева. Основни чвор може се састојати од најмање 1 кључа.
- Сви чворови (укључујући основни чвор) могу се састојати од највише (2д-1) кључеви.
- Број деце чвора је једнак сабирање броја кључева присутних у њему и .
- Сви кључеви чвора су сортирани у растућем редоследу. Дете између два кључа, к1 и к2, састоји се од свих кључева у распону између к1 и к2, респективно.
- За разлику од бинарног стабла претраге, структура података Б стабла расте и смањује се из корена. Док стабло бинарног претраживања расте наниже и смањује се надоле.
- Слично другим самоуравнотеженим бинарним стаблима претраге, временска сложеност структуре података Б стабла за операције као што су претраживање, уметање и брисање је О(лог?н) .
- Убацивање чвора у Б стабло се дешава само у чвору листа.
Размотримо следећи пример Б стабла минималног реда 5.
Слика 2. А Б Дрво реда 5
Напомена: Вредност минималне поруџбине је много већа од 5 у практичним Б стаблима.
У горњем дијаграму можемо приметити да су сви чворови листа на истом нивоу, а сви нелисни чворови немају празно подстабло и да се састоје од кључева за један мањи од броја њихових деце.
Формулација скупа правила Б стабла:
Свако Б дрво зависи од позитивног константног целог броја познатог као МИНИМУМ , који се користи за одређивање броја елемената података који се могу држати у једном чвору.
Правило 1: Корен може имати само један елемент података (или чак ни један елемент података ако такође није подређен); сваки други чвор има најмање МИНИМУМ елементи података.
Правило 2: Максималан број елемената података ускладиштених у чвору је двоструко већи од вредности МИНИМУМ .
Правило 3: Елементи података сваког чвора Б стабла се чувају у делимично попуњеном низу, сортираном од најмањег елемента података (на индексу 0 ) до највећег елемента података (на коначној искоришћеној позицији низа).
Правило 4: Укупан број подстабала испод чвора без листа је увек један већи од броја елемената података у том чвору.
јава инт у стрингу
- подстабло 0, подстабло 1,...
Правило 5: У вези са било којим чвором који није лист:
- Елемент података у индексу је већи од свих елемената података у броју подстабла и чвора, и
- Елемент података у индексу је мањи од свих елемената података у броју подстабла и+1 чвора.
Правило 6: Сваки лист у дрвету Б има исту дубину. Дакле, осигурава да Б стабло спречава проблем неуравнотеженог стабла.
Операције на структури података Б стабла
Да би се осигурало да ниједно од својстава структуре података Б стабла није нарушено током операција, Б стабло се може поделити или спојити. Следе неке операције које можемо да изведемо на Б стаблу:
- Претраживање елемента података у Б стаблу
- Уметање елемента података у Б стабло
- Брисање елемента података у Б стаблу
Операција претраживања на Б стаблу
Претраживање елемента у Б стаблу је слично оном у бинарном стаблу претраге. Али уместо да доноси двосмерну одлуку (лево или десно) као стабло бинарног претраживања, Б стабло доноси м-смерну одлуку у сваком чвору где је м број деце чвора.
Кораци за претрагу елемента података у Б стаблу:
Корак 1: Претрага почиње од коренског чвора. Упоредите елемент за претрагу, к, са кореном.
Корак 1.1: Ако се основни чвор састоји од елемента к, претрага ће бити завршена.
Корак 1.2: Ако је елемент к мањи од прве вредности у корену, прећи ћемо на крајње лево дете и претражити дете рекурзивно.
Корак 1.3.1: Ако корен има само два детета, прећи ћемо на крајње десно дете и рекурзивно претраживати подређене чворове.
Корак 1.3.2: Ако корен има више од два кључа, претражићемо остатак.
Корак 2: Ако елемент к није пронађен након преласка целог стабла, онда елемент за претрагу није присутан у Б стаблу.
Хајде да визуелизујемо горе наведене кораке уз помоћ примера. Претпоставимо да желимо да тражимо кључ к=34 у следећем Б стаблу:
Слика 3.1. Дато Б дрво
- Прво ћемо проверити да ли је кључ к = 34 налази се у коренском чвору. Пошто кључ није у корену, прећи ћемо на његове подређене чворове. Такође можемо приметити да коренски чвор има два детета; стога ћемо упоредити потребну вредност између два кључа.
Слика 3.2. Кључ к није присутан у корену - Сада када можемо да приметимо да је кључ к већи од коренског чвора, тј. 30, наставићемо са десним дететом корена.
Слика 3.3. Тастер к > 30, померите десно дете - Сада ћемо упоредити кључ к са вредностима присутним на чвору, тј. 40 и 50, респективно. Пошто је кључ к мањи од левог кључа, тј. 40, прећи ћемо на лево дете чвора.
Слика 3.4. Кључ к<40, move to left child< li> - Пошто је вредност у левом детету од 40 34, што је тражена вредност, можемо закључити да је кључ пронађен, а операција претраживања је завршена.
Слика 3.4. Кључ к = 34, лево дете од 40
Упоредили смо кључ са четири различите вредности у горњем примеру док га нисмо пронашли. Дакле, временска сложеност потребна за операцију претраживања у Б стаблу је О(лог?н) .
Уметање операције на Б дрво
Док убацујемо елемент података у Б стабло, прво морамо проверити да ли је тај елемент већ присутан у стаблу или не. Ако се елемент података пронађе унутар Б стабла, тада се операција уметања не дешава. Међутим, ако то није случај, наставићемо даље са уметањем. Постоје два сценарија о којима треба водити рачуна приликом уметања елемента у лисни чвор:
Кораци за уметање елемента података у Б стабло:
Корак 1: Почећемо тако што ћемо израчунати максималан број кључева у чвору на основу редоследа Б стабла.
Корак 2: Ако је стабло празно, додељује се коренски чвор, а ми ћемо убацити кључ који делује као коренски чвор.
Корак 3: Сада ћемо претражити одговарајући чвор за уметање.
4. корак: Ако је чвор пун:
Корак 4.1: Убацићемо елементе података у растућем редоследу.
Корак 4.2: Ако су елементи података већи од максималног броја кључева, цео чвор ћемо поделити на медијани.
Корак 4.3: Погураћемо средњи тастер нагоре и поделићемо леви и десни тастер као лево и десно дете.
5. корак: Ако чвор није пун, убацићемо чвор у растућем редоследу.
Хајде да визуелизујемо горе наведене кораке уз помоћ примера. Претпоставимо да се од нас тражи да креирамо Б стабло реда 4. Елементи података који треба да се убаце у Б стабло су 5,3,21,11,1,16,8,13,4 и 9 .
замените
- Пошто је м једнако 3, максималан број кључева за чвор = м-1 = 3-1 = 2 .
- Почећемо са уметањем 5 у празном дрвету.
Слика 4.1. Уметање 5 - Сада ћемо уметнути 3 у дрво. Пошто је 3 мање од 5, убацићемо 3 лево од 5 у исти чвор.
Слика 4.2. Уметање 3 - Сада ћемо уметнути 21 у стабло, а пошто је 21 веће од 5, биће уметнуто десно од 5 у истом чвору. Међутим, пошто знамо да је максималан број кључева у чвору 2, један од ових кључева ће бити премештен у чвор изнад како би се поделио. Тако ће се 5, средњи елемент података, померити нагоре, а 3 и 21 ће постати његов леви и десни чвор, респективно.
Слика 4.3. Убацивање 21 - Сада је време да се убаци следећи елемент података, тј. 11, који је већи од 5, али мањи од 21. Стога ће 11 бити уметнут као кључ са леве стране чвора који се састоји од 21 као кључ.
Слика 4.4. Уметање 11 - Слично, уметнућемо следећи елемент података 1 у стабло, и као што можемо приметити, 1 је мање од 3; стога ће бити уметнут као кључ са леве стране чвора који се састоји од 3 као кључ.
Слика 4.5. Уметање 1 - Сада ћемо у стабло убацити елемент података 16, који је већи од 11, али мањи од 21. Међутим, број кључева у том чвору премашује максималан број кључева. Стога ће се чвор поделити, померајући средњи кључ у корен. Дакле, 16 ће бити уметнуто десно од 5, раздвајајући 11 и 21 у два одвојена чвора.
Слика 4.6. Уметање 16 - Елемент података 8 биће уметнут као кључ лево од 11.
Слика 4.7. Уметање 8 - У стабло ћемо убацити 13, што је мање од 16 и веће од 11. Дакле, елемент података 13 треба уметнути десно од чвора који се састоји од 8 и 11. Међутим, пошто максималан број кључева у стаблу може само 2, доћи ће до поделе, померајући средњи елемент података 11 у горњи чвор и 8 и 13 у два одвојена чвора. Сада ће се горњи чвор састојати од 5, 11 и 16, што опет премашује максималан број кључева. Због тога ће доћи до још једног поделе, чинећи елемент података 11 основним чвором са 5 и 16 као потомцима.
Слика 4.8. Уметање 13 - Пошто је елемент података 4 мањи од 5, али већи од 3, биће уметнут десно од чвора који се састоји од 1 и 3, што ће поново премашити максималан број кључева у чвору. Због тога ће поново доћи до изливања, померајући 3 у горњи чвор поред 5.
Слика 4.9. Уметање 4 - Најзад, елемент података 9, који је већи од 8, али мањи од 11, биће уметнут десно од чвора који се састоји од 8 као кључ.
Слика 4.10. Уметање 9
У горњем примеру, извршили смо различита поређења. Прва вредност је директно уметнута у стабло; након тога, свака вредност је морала да се упореди са чворовима доступним у том стаблу. Временска сложеност за операцију уметања у Б стабло зависи од броја чворова и .
Брисање операције на Б стаблу
Брисање елемента података на Б стаблу садржи три примарна догађаја:
- Претраживање чвора у којем постоји кључ који треба обрисати,
- Брисање кључа и
- Балансирање дрвета, ако је потребно.
Приликом брисања елемента из стабла може доћи до стања познатог као Ундерфлов. Недостатак се јавља када се чвор састоји од мањег броја кључева; требало би да издржи.
Следе неки термини које треба разумети пре визуелизације операције брисања/уклањања:
У наставку су три истакнута случаја операције брисања у Б стаблу:
Случај 1: Брисање/уклањање кључа лежи у Леаф чвору - Овај случај је даље подељен на два различита случаја:
1. Брисање/уклањање кључа не нарушава својство минималног броја кључева који чвор треба да има.
Хајде да визуализујемо овај случај користећи пример где ћемо избрисати кључ 32 из следећег Б стабла.
Слика 4.1: Брисање кључа листног чвора (32) из Б стабла
Као што можемо приметити, брисање 32 из овог стабла не крши горњу особину.
2. Брисање/уклањање кључа крши својство минималног броја кључева које чвор треба да држи. У овом случају, морамо да позајмимо кључ од његовог најближег братског чвора по редоследу са лева на десно.
Прво ћемо посетити најближег левог брата. Ако леви братски чвор има више од минималног броја кључева, он ће позајмити кључ од овог чвора.
У супротном, проверићемо да ли позајмимо од најближег десног братског чвора.
Хајде да сада визуелизујемо овај случај уз помоћ примера где ћемо избрисати 31 из горњег Б стабла. У овом случају ћемо позајмити кључ од левог братског чвора.
Слика 4.2: Брисање кључа листног чвора (31) из Б стабла
Ако се оба приближна братска и сестра чвора већ састоје од минималног броја кључева, онда ћемо спојити чвор са левим братским или десним чвором. Овај процес спајања се врши преко родитељског чвора.
Хајде да поново визуализујемо брисањем кључа 30 са горњег Б стабла.
Слика 4.3: Брисање кључа листног чвора (30) из Б стабла
класа јава скенера
Случај 2: Брисање/уклањање кључа лежи у чвору који није лист - Овај случај је даље подељен на различите случајеве:
1. Не-Леаф/Интерни чвор, који је уклоњен, замењује се претходником у редоследу ако леви подређени чвор има више од минималног броја кључева.
Хајде да визуелизујемо овај случај користећи пример где ћемо избрисати кључ 33 из Б стабла.
Слика 4.4: Брисање кључа лисног чвора (33) из Б стабла
2. Не-Леаф/Интерни чвор, који је уклоњен, замењује се наследником по реду ако десни подређени чвор има више од минималног броја кључева.
Ако било које дете има минималан број кључева, онда ћемо спојити леви и десни дечји чвор.
Хајде да визуализујемо овај случај брисањем кључа 30 из Б стабла.
Слика 4.5: Брисање кључа листног чвора (30) из Б стабла
Након спајања, ако родитељски чвор има мање од минималног броја кључева, може се тражити браћу и сестре, као у Случај 1 .
Случај 3: У следећем случају, висина дрвета се смањује. Ако циљни кључ лежи у унутрашњем чвору, а уклањање кључа доводи до мањег броја кључева у чвору (што је мање од потребног минимума), онда потражите претходника у редоследу и наследника у редоследу. Ако оба детета имају минималан број кључева, онда не може доћи до позајмљивања. То доводи до Случај 2(3) , тј. спајање подређених чворова.
Поново ћемо потражити брата и сестру да позајмимо кључ. Међутим, ако се брат или сестра такође састоји од минималног броја кључева, онда ћемо спојити чвор са братом и сестром заједно са родитељским чвором и уредити подређене чворове према захтевима (узлазни редослед).
Хајде да визуелизујемо овај случај уз помоћ примера где ћемо избрисати елемент података 10 из датог Б стабла.
Слика 4.6: Брисање кључа лисног чвора (10) из Б стабла
Временска сложеност у горњим примерима варира у зависности од локације са које кључ треба да се обрише. Дакле, временска сложеност за операцију брисања у Б стаблу је О(лог?н) .
Закључак
У овом туторијалу смо научили о Б стаблу и визуелизовали његове различите операције на различитим примерима. Такође смо разумели нека основна својства и правила Б дрвета.