Још једна разлика између Б-стабла и бинарног стабла је да Б-стабло мора имати све своје дечје чворове на истом нивоу, док бинарно стабло нема такво ограничење. Бинарно стабло може имати максимално 2 подстабла или чворишта, док у Б-стаблу може имати М но подређених или чворова гдје је М ред Б-стабла.
Цомпарисон Цхарт
| Основа за поређење | Б-трее | Бинари трее |
|---|---|---|
| Основно ограничење | Чвор може имати максималан М број дјечјих чворова (гдје је М редослијед стабла). | Чвор може имати највише 2 подстабла. |
| Усед | Користи се када се подаци чувају на диску. | Користи се када се записи и подаци чувају у РАМ-у. |
| Висина дрвета | лог M Н (где је м ред дрвета М-пута) | лог 2 Н |
| Апликација | Структура података индексирања кодова у многим ДБМС-има. | Оптимизација кода, Хуффманово кодирање, итд. |
Дефиниција Б-стабла
Б-стабло је балансирано дрво М-пута и такође је познато као балансирано стабло сортирања. То је слично бинарном стаблу претраге где су чворови организовани на основу обилазнице. Просторна сложеност Б-стабла је О (н). Сложеност уношења и брисања је О (лог н).
Постоје одређени услови који морају бити истинити за Б-стабло:
- Висина стабла мора бити што је могуће мања.
- Изнад лишћа стабла не сме бити никаквих празних подстара.
- Лишће стабла мора доћи на истом нивоу.
- Сви чворови треба да имају најмањи број деце осим да напусте чворове.
Својства Б-стабла реда М
- Сваки чвор може имати максималан М број дјеце и минимални број дјеце М / 2 или било који број од 2 до максимума.
- Сваки чвор има један кључ мањи од дјеце са максималним М-1 кључевима.
- Распоред кључева је у неком специфичном реду унутар чворова. Сви кључеви у подстаблу присутном на левој страни кључа су претходници кључа, а они који се налазе на десној страни кључа називају се наследници.
- У тренутку уметања пуног чвора, стабло се дели на два дела, а кључ са средњом вредношћу се умеће у родитељски чвор.
- Операција спајања се дешава када су чворови избрисани.
Дефиниција бинарног стабла
Бинарно стабло је дрвна структура која може имати највише два показивача за своје дечије чворове. То значи да највиши степен који чвор може да има је 2 и да може бити нула или један степен.
Постоје одређене варијанте бинарног стабла као што су строго бинарно стабло, комплетно бинарно стабло, проширено бинарно стабло, итд.
- Строго бинарно стабло је стабло где сваки не-терминални чвор мора имати лево подстабло и десно подстабло.
- Дрво се назива Комплетно бинарно стабло када задовољава услов да има 2 и чворове на сваком нивоу где је и ниво.
- Навојни бинарни је бинарно стабло које се састоји од 0 нода или 2 броја чворова.
Траверсал Тецхникуес
Прелазак дрвећа је једна од најчешћих операција које се изводе на структури података о стаблу у којој је сваки чвор посећен тачно једном на систематски начин.
- Инордер - У овом прелазу стабла лево подстабло се рекурзивно посећује, а коријенски чвор се посећује и посећује се последње десно подстабло.
- Преорер - У овом прелазу стабла, коријенски чвор се прво посећује, затим лево подстабло и на крају последње десно подстабло.
- Постордер- Ова техника посећује лево подстабло, затим десно подстабло и последњи коренски чвор.
Кључне разлике између Б-стабла и бинарног стабла
- У Б-стаблу, максимални број дечјих чворова који може да има не-терминални чвор је М где је М ред Б-стабла. С друге стране, бинарно стабло може имати највише два подстабла или дечије чворове.
- Б-стабло се користи када се подаци чувају на диску, док се бинарно стабло користи када се подаци чувају у брзој меморији као што је РАМ.
- Друга област апликације за Б-трее је структура индексирања података код ДБМС-а, за разлику од тога, бинарно стабло се користи у оптимизацији кода, кодирању хуффман-а итд.
- Максимална висина Б-стабла је лог М Н (М је редослед дрвета). У односу на, максимална висина бинарног стабла је лог 2 Н (Н је број чворова и база је 2 јер је за бинарно).
Закључак
Б-стабло се користи преко бинарног и бинарног стабла претраживања, главни разлог за то је хијерархија меморије где је ЦПУ повезан са кешом са каналима високог пропусног опсега, док је ЦПУ повезан са диском преко канала слабог пропусног опсега. Бинарно стабло се користи када се записи чувају у РАМ-у (мала и брза), а Б-стабло се користи када се записи чувају на диску (велики и спори). Дакле, употреба Б-стабла уместо Бинарног стабла значајно смањује време приступа због високог фактора гранања и смањене висине стабла.
