Б-стабло — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
Нема описа измене |
||
Ред 11:
* Чвор који није лист и садржи ''-{k'}-'' елемената показује на ''-{k'}-+1'' деце. Показивачи ка деци су тако распоређени да показују на чворове са вредностима кључева између вредности кључева свака два суседна елемента чвора, као и на чворове са вредностима кључевима мањим и већим од вредности сваког његовог кључа.
== Особине ==
== Операције над подацима == ▼
За б-стабло висине ''-{h}-'', са константом ''-{k}-'' и бројем чворова ''-{n}-'' важи:
: <math>h \leq \log_k \left({n+1 \over 2} \right)</math>
Структура б-стабла за исти скуп података у принципу није једнозначна. На пример за ''-{k=1}-'' и вредности кључева 21,22,23,24 је за корен стабла могуће узети кључ 22 односно 23, при чему би у првом случају леви чвор преузео кључ 21 а десни 23 и 24. У другом случају би леви чвор преузео кључеве 21 и 22, а десни 24. Са порастом константе ''-{k}-'' и броја елемената расте и број могућности њиховог распоређивања.
=== Претраживање стабла ===
Претраживање, као и код других врста стабала, почиње од корена стабла и наставља се тако што се при сваком кораку претраге установљава да ли тражена вредност кључа постоји у трненутно претраживаном чвору, у неком од његове деце или не постоји у стаблу.
=== Додавање новог елемента ===
Линија 23 ⟶ 31:
=== Брисање елемента из стабла ===
Операција '''Брисања''' елемента може резултирати губљењем особина б-стабла. Притом се искључиво ради о повреди правила о минималном броју елемената по чвору. Приступ проблему се састоји у томе да се у чвор који након брисања поседује ''-{k-1}-'' елемената убаци елемент из родитељског чвора. Овај процес се може понављати рекурзивно, од дна стабла према врху.
Притом се издваја случај када стабло из кога се брише један елемент има минималан број елемената у сваком чвору. Ово значи да ће на крају процеса корен стабла, кога чини само један елемент бити утопљен у једно од своје деце а притом ће свако од њих имати тачно по ''-{k}-'' елемената. У овом случају завршни корак је спајање то двоје деце и нови корен стабла. Једна од последица брисања у овом случају је смањење висине стабла за један.
== Види још ==
* [[Црвено-црно стабло]]
== Спољашње везе ==
* [http://slady.net/java/bt/view.php?w=600&h=450 Јава-аплет који симулира унос података б-стабла]
== Извори ==
* ''Скрипта за предмет „Информатика 2“ са Универзитета Карлсруе, Немачка.''
* ''Белешке са предавања Др. Проф. Рудолфа Бајера, ТУ-Минхен'', Немачка
[[cs:B-strom]]
| |||