21.848
измена
м
нема описа измене
мНема описа измене |
|||
|
== Дефиниција ==
Свако б-стабло је одређено једним параметром ''-{k}-'', који може узимати вредности [[природан број|природних бројева]]. Услови које свако б-стабло треба да испуњава су следећи:
* Сви листови дрвета се налазе на истој висини у односу на корен стабла.▼
* Корен стабла може садржати ''1'' до ''-{2k}-'' елемената. Сваки други чвор стабла садржи од ''-{k}- ''до ''-{2k}-'' елемената.
* Сви елементи у једном чвору су сортирани по вредности кључа
* Чвор који није лист и садржи ''-{k'}-'' елемената показује на ''-{k'}-+1'' деце. Показивачи ка деци су тако распоређени да показују на чворове са вредностима кључева између вредности кључева свака два суседна елемента чвора, као и на чворове са вредностима кључевима мањим и већим од вредности сваког његовог кључа.
▲* Сви листови дрвета се налазе на истој висини.
== Операције над подацима ==
Структура б-стабла за исти скуп података у принципу није једнозначна. На пример за ''-{k=1}-'' и вредности кључева 21,22,23,24 је за корен стабла могуће узети кључ 22 односно 23, при чему би у првом случају леви чвор преузео кључ 21 а десни 23 и 24. У другом случају би леви чвор преузео кључеве 21 и 22, а десни 24. Са порастом константе ''-{k}-'' и броја елемената расте и број могућности њиховог распоређивања.
=== Додавање новог елемента ===
[[Слика:Bt.add.png|Случај прекорачења дозвољеног броја елемената приликом додавања новог.|десно|250п|мини]]
Нови елемент се увек '''додаје''' на дно стабла, као нови елеменат у неком од листова. Уколико у неком тренутку број елемената у неком од чворова пређе дозвољену вредност од ''-{2k}-'', елеменат најближи средини низа елемената бива издвојен из низа и додат у родитеља чвора коме је припадао, истовремено постајући родитељ свих елемената са његове леве односно десне стране.
На датом примеру (слика десно) је број ''-{k=1}-''. При другом кораку у постојеће стабло је додат елемент са кључем 80. Како је тиме прекорачен број (''-{2k=2}-'') дозвољених елемената по чвору, изабран је средишљи елеменат проблматичног чвора са кључем 50 и додат у свој родитељски чвор који у том тренутку садржи само вредност 42. Сви елементи са његове леве односно десне стране се деле у два нова чвора чији ће родитељ он постати.
Да је претходно описаним операцијама дозвољени број елемената у родитељском чвору био нарушен, процес би био поновљен и за њега. Уколико до овакве ситуације дође у корену стабла, неминовно је повећање висине стабла за један.
| |||