Садржај

• Упоредни графикон
• Дефиниција Б-стабла
• Својства Б-стабла реда М
• Дефиниција Бинарног стабла
• Технике обиласка
• Закључак

Б-стабло и Бинарно дрво су врсте нелинеарне структуре података. Иако су појмови слични, али су различити у свим аспектима. Бинарно стабло користи се када су записи или подаци похрањени у РАМ-у умјесто на диску јер је брзина приступа РАМ-у много већа од диска. С друге стране, Б-стабло се користи када се подаци похрањују на диск, смањује време приступа смањујући висину стабла и повећавајући гране у чвору.

Још једна разлика између Б-стабла и бинарног стабла је та што Б-стабло мора имати све своје подређене чворове на истом нивоу док бинарно дрво нема тако ограничење. Бинарно стабло може имати највише 2 поткрепљења или чворова док у Б-дрвету може бити М без подтврда или чворова где је М редослед Б стабла.

1. Упоредни графикон
2. Дефиниција
3. Кључне разлике
4. Закључак

Упоредни графикон

Основе за поређење	Б-стабло	Бинарно дрво
Суштинско ограничење	Чвор може имати највише М броја дечијих чворова (где је М редослед стабла).	Чвор може имати највише 2 броја потврда.
Користи се	Користи се када се подаци чувају на диску.	Користи се када се записи и подаци похрањују у РАМ-у.
Висина стабла	ПријаваМ Н (где је м редослед стабла М-пута)	Пријава2 Н
Апликација	Структура података индексирања кода у многим ДБМС-има.	Оптимизација кода, Хуффманово кодирање итд.

Дефиниција Б-стабла

Стабло Б је избалансирано М-стабло и познато је и као стабло избалансиране сорте. Слично је с бинарним стаблом претраживања гдје су чворови организирани на основи интерверзног пресјека. Сложеност простора Б-стабла је О (н). Временска сложеност уметања и брисања је О (лог н).

Постоје одређени услови који морају бити тачни за Б стабло:

• Висина стабла мора бити што је могуће мања.
• Изнад лишћа стабла не би требало бити празних поткољеница.
• Листови дрвета морају да буду на истом нивоу.
• Сви чворови требају имати најмање дјеце, осим чворова који остављају.

Својства Б-стабла реда М

• Сваки чвор може имати максимални М број деце и минимални М / 2 број деце или било који број од 2 до максимума.
• Сваки чвор има један тастер мање од деце са максималним М-1 тастерима.
• Распоред типки је по одређеном редослиједу унутар чворова. Сви тастери у поддрвету који се налазе на левој страни тастера су претходници, а они који се налазе у десној страни тастера називају се наследници.
• У тренутку уметања пуног чвора, стабло се дели на два дела, а кључ са средњом вредношћу се убацује у родитељски чвор.
• Операција спајања се дешава када чворови буду избрисани.

Дефиниција Бинарног стабла

Бинарно дрво је структура дрвећа која може имати највише два показивача за своје подређене чворове. То значи да највиши степен чвора може бити 2, а може постојати и нула или чвор једног степена.

Постоје одређене варијанте бинарног стабла попут строго бинарног стабла, комплетног бинарног стабла, проширеног бинарног стабла итд.

• Строго бинарно дрво је дрво на којем сваки не-терминални чвор мора имати лијево подређење и десно поддрево.
• Дрво се назива Комплетно бинарно дрво када оно испуњава услов да има 2 ^ја чворови на сваком нивоу гдје је и ниво.
• Навојни бинарни запис је бинарно стабло које се састоји од 0 без чворова или 2 броја чворова.

Технике обиласка

Прелазак дрвећа је једна од најчешћих операција изведених на структури података о дрвећу, у којој је сваки чвор тачно једном посетио систематски.

• Инордер - У овом се дрвету пролази лево поткресивност рекурзивно, затим се посећује роот чвор и у последњем се налази десна поддрва.
• Преорер - У овом дрвету се налази коријенски чвор испрва, а затим лијево подређење и коначно десно поддрево.
• Постордер - Ова техника обилази лево субтрее, затим десно субтрее и последњи роот чвор.

1. У Б-дрвету је највећи број дечјих чворова који може имати не-терминални чвор М где је М редослед Б-стабла. С друге стране, бинарно дрво може имати највише два поткрата или подређених чворова.
2. Б-стабло се користи када се подаци похрањују на диск, док се бинарно дрво користи када се подаци похрањују у брзој меморији попут РАМ-а.
3. Друга област примене за Б-стабло је структура података индексирања кода у ДБМС-у, насупрот томе, Бинарно дрво се користи у оптимизацији кода, Хуффман-овом шифрирању итд.
4. Максимална висина Б стабла је трупац_МН (М је ред дрвета). За разлику од максималне висине бинарног стабла је записник₂Н (Н је број чворова, а база је 2 јер је за бинарне).

Закључак

Б-стабло се користи преко бинарног и бинарног стабла претраживања. Главни разлог за то је меморијска хијерархија где је ЦПУ повезан са кеш меморијом каналима велике пропусности док је ЦПУ повезан с диском преко канала ниске пропусности. Бинарно стабло се користи када су записи похрањени у РАМ-у (мали и брзи), а Б-стабло се користи када се записи похрањују на диск (велики и спори). Дакле, употреба Б-стабла уместо Бинарног стабла значајно смањује време приступа због високог фактора гранања и смањене висине стабла.