Б-стабло — разлика између измена

биће још дорада, но могу да ослободим чланак и за измене других
(биће још дорада, но могу да ослободим чланак и за измене других)
{{радови у току}}
 
'''Б-стабло''' је [[структура података]] у [[информатика|информатици]]. Карактеристике су му потпуна балансираност, [[сортирање]] података по вредности кључа и чување одређеног броја елемената у једном чвору стабла. Операције над подацима стабла се обављају у амортизовано логаритамском времену. Б-стабло налази примену у [[база података|базама података]] и системима фајлова и директоријума на [[Тврди диск|тврдим дисковима]].
 
|-
|Минималан број чворова (''-{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>
|-
|}
Операција '''Брисања''' елемента може резултирати губљењем особина б-стабла. Притом се искључиво ради о повреди правила о минималном броју елемената по чвору. Приступ проблему се састоји у томе да се у чвор који након брисања поседује ''-{k-1}-'' елемената убаци елемент из родитељског чвора. Овај процес се може понављати рекурзивно, од дна стабла према врху.
 
Притом се издваја случај када стабло из кога се брише један елемент има минималан број елемената у сваком чвору. Ово значи да ће на крају процеса корен стабла, кога чини само један елемент бити утопљен у једно од своје деце а притом ће свако од њих имати тачно по ''-{k}-'' елемената. У овом случају завршни корак је спајањестапање то двоје деце иу нови чвор који ће постати корен стабла. Једна од последица брисања у овом случају је смањење висине стабла ''-{h}-'' за један.
 
== Види још ==
== Извори ==
* ''Скрипта за предмет „Информатика 2“ са Универзитета Карлсруе, Немачка.''
* ''Белешке са предавања Др. Проф. Рудолфа Бајера, ТУ-Минхен'', Немачка''
 
[[cs:B-strom]]