Б-стабло — разлика између измена
Садржај обрисан Садржај додат
биће још дорада, но могу да ослободим чланак и за измене других |
|||
Ред 1:
'''Б-стабло''' је [[структура података]] у [[информатика|информатици]]. Карактеристике су му потпуна балансираност, [[сортирање]] података по вредности кључа и чување одређеног броја елемената у једном чвору стабла. Операције над подацима стабла се обављају у амортизовано логаритамском времену. Б-стабло налази примену у [[база података|базама података]] и системима фајлова и директоријума на [[Тврди диск|тврдим дисковима]].
Линија 19 ⟶ 17:
|-
|Минималан број чворова (''-{h > 0}-'')
|<math>n = 1 + 2\sum_{i=0}^{h-1}{(k+1)^i}</math>
|-
|Минималан број елемената (''-{h > 0}-'')
|<math>n = 1 + 2k\sum_{i=0}^{h-1}{(k+1)^i}</math>
|-
|Максималан број чворова
|<math>n = \sum_{i=0}^{h}{(2k+1)^i}</math>
|-
|Максималан број елемената
|<math>n = 2k\sum_{i=0}^{h}{(2k+1)^i}</math>
|-
|}
Линија 49 ⟶ 47:
Операција '''Брисања''' елемента може резултирати губљењем особина б-стабла. Притом се искључиво ради о повреди правила о минималном броју елемената по чвору. Приступ проблему се састоји у томе да се у чвор који након брисања поседује ''-{k-1}-'' елемената убаци елемент из родитељског чвора. Овај процес се може понављати рекурзивно, од дна стабла према врху.
Притом се издваја случај када стабло из кога се брише један елемент има минималан број елемената у сваком чвору. Ово значи да ће на крају процеса корен стабла
== Види још ==
Линија 59 ⟶ 57:
== Извори ==
* ''Скрипта за предмет „Информатика 2“ са Универзитета Карлсруе, Немачка.''
* ''Белешке са предавања Др. Проф. Рудолфа Бајера, ТУ-Минхен
[[cs:B-strom]]
| |||