Б-стабло — разлика између измена
Нема описа измене |
|||
| Ред 12: | Ред 12: | ||
== Операције над подацима == |
== Операције над подацима == |
||
Структура б-стабла за исти скуп података у принципу није једнозначна. На пример за -{k=1}- и вредности кључева 21,22,23,24 је за корен стабла могуће узети кључ 22 односно 23, при чему би у првом |
Структура б-стабла за исти скуп података у принципу није једнозначна. На пример за -{k=1}- и вредности кључева 21,22,23,24 је за корен стабла могуће узети кључ 22 односно 23, при чему би у првом случају леви чвор преузео кључ 21 а десни 23 и 24. У другом случају би леви чвор преузео кључеве 21 и 22, а десни 24. Са порастом константе -{k}- и броја елемената расте и број могућности њиховог распоређивања. |
||
=== Додавање новог елемента === |
=== Додавање новог елемента === |
||
[[Слика:Bt.add.png|Случај прекорачења дозвољеног броја елемената приликом додавања новог.|десно|250п|мини]] |
|||
Нови елемент се увек '''додаје''' на дно стабла, као нови елеменат у неком од листова. Уколико у неком тренутку број елемената у неком од чворова пређе дозвољену вредност од -{2k}-, елеменат најближи средини низа елемената бива издвојен из низа и додат у родитеља чвора коме је припадао, истовремено постајући родитељ свих елемената са његове леве односно десне стране. |
Нови елемент се увек '''додаје''' на дно стабла, као нови елеменат у неком од листова. Уколико у неком тренутку број елемената у неком од чворова пређе дозвољену вредност од -{2k}-, елеменат најближи средини низа елемената бива издвојен из низа и додат у родитеља чвора коме је припадао, истовремено постајући родитељ свих елемената са његове леве односно десне стране. |
||
На датом примеру (слика десно) је број -{k=1}-. При другом кораку у постојеће стабло је додат елемент са кључем 80. Како је тиме прекорачен број (-{2k=2}-) дозвољених елемената по чвору, изабран је средишљи елеменат проблматичног чвора са кључем 50 и додат у свој родитељски чвор који у том тренутку садржи само вредност 42. Сви елементи са његове леве односно десне стране се деле у два нова чвора чији ће родитељ он постати. |
|||
Да је претходно описаним операцијама дозвољени број елемената у родитељском чвору био нарушен, процес би био поновљен и за њега. Уколико до овакве ситуације дође у корену стабла, неминовно је повећање висине стабла за један. |
|||
=== Брисање елемента из стабла === |
=== Брисање елемента из стабла === |
||
Верзија на датум 21. фебруар 2007. у 01:38
 | Један корисник управо ради на овом чланку. Молимо остале кориснике да му допусте да заврши са радом. Ако имате коментаре и питања у вези са чланком, користите страницу за разговор.
Хвала на стрпљењу. Када радови буду завршени, овај шаблон ће бити уклоњен. Напомене
|
Б-стабло је структура података у информатици. Карактеристике су му потпуна балансираност, сортирање података по вредности кључа и чување одређеног броја елемената у једном чвору стабла. Операције над подацима стабла се обављају у амортизовано логаритамском времену. Б-стабло налази примену у базама података и системима фајлова и директоријума на тврдим дисковима.
Дефиниција
Свако б-стабло је одређено једним параметром k, који може узимати вредности природних бројева. Услови које свако б-стабло треба да испуњава су следећи:
- Један чвор стабла може садржати од 1 до 2k елемената
- Сви елементи у једном чвору су сортирани по вредности кључа
- Сваки елеменат чвора који није лист показује на по тачно један чвор лево и десно од себе. Притом треба да буде задовољен услов сотрираности, а два суседна елемента показују на тачно један исти чвор.
- Сви листови дрвета се налазе на истој висини.
Операције над подацима
Структура б-стабла за исти скуп података у принципу није једнозначна. На пример за k=1 и вредности кључева 21,22,23,24 је за корен стабла могуће узети кључ 22 односно 23, при чему би у првом случају леви чвор преузео кључ 21 а десни 23 и 24. У другом случају би леви чвор преузео кључеве 21 и 22, а десни 24. Са порастом константе k и броја елемената расте и број могућности њиховог распоређивања.
Додавање новог елемента
Нови елемент се увек додаје на дно стабла, као нови елеменат у неком од листова. Уколико у неком тренутку број елемената у неком од чворова пређе дозвољену вредност од 2k, елеменат најближи средини низа елемената бива издвојен из низа и додат у родитеља чвора коме је припадао, истовремено постајући родитељ свих елемената са његове леве односно десне стране.
На датом примеру (слика десно) је број k=1. При другом кораку у постојеће стабло је додат елемент са кључем 80. Како је тиме прекорачен број (2k=2) дозвољених елемената по чвору, изабран је средишљи елеменат проблматичног чвора са кључем 50 и додат у свој родитељски чвор који у том тренутку садржи само вредност 42. Сви елементи са његове леве односно десне стране се деле у два нова чвора чији ће родитељ он постати.
Да је претходно описаним операцијама дозвољени број елемената у родитељском чвору био нарушен, процес би био поновљен и за њега. Уколико до овакве ситуације дође у корену стабла, неминовно је повећање висине стабла за један.
Брисање елемента из стабла
Приликом брисања елемента из чворова стабла који нису листово се дешава да брисање истог чворови на које је показивао остају без родитеља. У том случају се одабире или елемент на левом крају његовог десног детета, или елемент на десном крају његовог левог детета, и преузима његову улогу.