Водич за почетнике у бинарном дрвећу

Ако сте похађали курс о структурама података на рачунару или сте самоуки програмер, велика је вероватноћа да сте наишли на израз „Бинарно дрвеће“. Иако могу звучати помало надмоћно и сложено, концепт бинарног стабла је прилично једноставан.

Читајте даље док сецирамо бинарна стабла и зашто су они неопходан основни концепт за програмере.

Шта су бинарна стабла?

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

Први чвор у бинарном стаблу назива се „корен“. Чворови последњег нивоа на дрвету називају се листови.

Сваки чвор садржи ставку података и два показивача чвора. Празно бинарно стабло представљено је нултим показивачем. Као што сте можда већ схватили, бинарна стабла могу имати само двоје деце (отуда и назив).

Врсте бинарних дрвених структура

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

Повезан: Најбољи начини да научите како бесплатно кодирати

Потпуно бинарно стабло има чворове испуњене на сваком нивоу, са изузетком последњег нивоа. У комплетним бинарним стаблима чворови су концентрисани на левој страни корена. Друга уобичајена структура је уравнотежено бинарно дрво; у овој структури висине десног и левог подстабла морају се разликовати највише за један. Такође је потребно да се лево и десно подстабло такође уравнотеже.

Важно је напоменути да је висина уравнотеженог бинарног стабла О (логн), где је н број чворова у стаблу.

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

Шта су бинарна стабла претраживања?

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

Својство БСТ мора бити тачно за сваки наредни родитељски чвор у стаблу.

Бинарна стабла претраживања нуде брзо уметање и претраживање. Уметање, брисање и операције претраживања имају сложеност О (н) у најгорем случају, што је слично повезаној листи.

Предности бинарног дрвећа

Бинарна стабла нуде многе предности, због чега остају веома корисна структура података. Могу се користити за приказивање структурних односа и хијерархија у скупу података. Још важније, бинарна стабла омогућавају ефикасно претраживање, брисање и уметање.

Такође је врло лако имплементирати и одржавати бинарно стабло. Бинарно дрво нуди програмерима предности уређеног низа и повезане листе; претраживање у бинарном стаблу је брзо као у сортираном низу, а операције уметања или брисања су ефикасне као и на повезаним листама.

Бинарна стабла су важна структура података

Бинарна стабла су веома важна структура података и кључно је да их програмери удобно примене у својим програмима. Често анкетари постављају једноставне проблеме са бинарним стаблом, попут преласка, максималне дубине, пресликавања итд.

Топло препоручујемо разумевање концепта бинарног стабла и упознавање са типичним проблемима интервјуа.

ТрееВиз: једноставан начин визуализације структура података

Прочитајте следеће

О аутору