Б-стабло

Б-стабло је структура података у информатици. Карактеристике су му потпуна балансираност, сортирање података по вредности кључа и чување одређеног броја елемената у једном чвору стабла. Операције над подацима стабла се обављају у амортизовано логаритамском времену. Б-стабло налази примену у базама података и системима фајлова и директоријума на тврдим дисковима.

Дефиниција

Свако б-стабло је одређено једним параметром k, који може узимати вредности природних бројева. Услови које свако б-стабло треба да испуњава су следећи:

Сви листови дрвета се налазе на истој висини у односу на корен стабла.
Корен стабла може садржати 1 до 2k елемената. Сваки други чвор стабла садржи од k до 2k елемената.
Сви елементи у једном чвору су сортирани по вредности кључа
Чвор који није лист и садржи k' елемената показује на k'+1 деце. Показивачи ка деци су тако распоређени да показују на чворове са вредностима кључева између вредности кључева свака два суседна елемента чвора, као и на чворове са вредностима кључевима мањим и већим од вредности сваког његовог кључа.

Особине

За б-стабло висине h, са константом k и бројем чворова n важе следећи искази:

Висина стабла	$h\leq \log _{k}\left({n+1 \over 2}\right)$
Минималан број чворова (h > 0)	$n=1+2\sum _{i=0}^{h-1}{(k+1)^{i}}$
Минималан број елемената (h > 0)	$n=1+2k\sum _{i=0}^{h-1}{(k+1)^{i}}$
Максималан број чворова	$n=\sum _{i=0}^{h}{(2k+1)^{i}}$
Максималан број елемената	$n=2k\sum _{i=0}^{h}{(2k+1)^{i}}$

Операције

Структура б-стабла за исти скуп података у принципу није једнозначна. На пример за k=1 и вредности кључева 21,22,23,24 је за корен стабла могуће узети кључ 22 односно 23, при чему би у првом случају леви чвор преузео кључ 21 а десни 23 и 24. У другом случају би леви чвор преузео кључеве 21 и 22, а десни 24. Са порастом константе k и броја елемената расте и број могућности њиховог распоређивања.

Претраживање стабла

Претраживање, као и код других врста стабала, почиње од корена стабла и наставља се тако што се при сваком кораку претраге установљава да ли тражена вредност кључа постоји у тренутно претраживаном чвору, у неком од његове деце или не постоји у стаблу.

Додавање новог елемента

Случај прекорачења дозвољеног броја елемената приликом додавања новог.

Нови елемент се увек додаје на дно стабла, као нови елеменат у неком од листова. Уколико у неком тренутку број елемената у неком од чворова пређе дозвољену вредност од 2k, елеменат најближи средини низа елемената бива издвојен из низа и додат у родитеља чвора коме је припадао, истовремено постајући родитељ свих елемената са његове леве односно десне стране.

На датом примеру (слика десно) је број k=1. При другом кораку у постојеће стабло је додат елемент са кључем 80. Како је тиме прекорачен број (2k=2) дозвољених елемената по чвору, изабран је средишљи елеменат проблематичног чвора са кључем 50 и додат у свој родитељски чвор који у том тренутку садржи само вредност 42. Сви елементи са његове леве односно десне стране се деле у два нова чвора чији ће родитељ он постати.

Да је претходно описаним операцијама дозвољени број елемената у родитељском чвору био нарушен, процес би био поновљен и за њега. Уколико до овакве ситуације дође у корену стабла, неминовно је повећање висине стабла за један.

Брисање елемента из стабла

Операција Брисања елемента може резултовати губљењем особина б-стабла. Притом се искључиво ради о повреди правила о минималном броју елемената по чвору. Приступ проблему се састоји у томе да се у чвор који након брисања поседује k-1 елемената убаци елемент из родитељског чвора. Овај процес се може понављати рекурзивно, од дна стабла према врху.

Притом се издваја случај када стабло из кога се брише један елемент има минималан број елемената у сваком чвору. Ово значи да ће на крају процеса корен стабла кога чини само један елемент бити утопљен у једно од своје деце а притом ће свако од њих имати тачно по k елемената. У овом случају завршни корак је стапање то двоје деце у нови чвор који ће постати корен стабла. Једна од последица брисања у овом случају је смањење висине стабла h за један.

Извори

Скрипта за предмет „Информатика 2“ са Универзитета Карлсруе, Немачка

Види још

Спољашње везе

Јава-аплет који симулира унос података б-стабла