Шта је стабло бинарног претраживања?

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

У овом чланку ћемо детаљније погледати како функционише — заједно са његовим својствима и применама.

Шта је стабло бинарног претраживања?

Бинарно стабло претраге је структура података састављена од чворова—слично повезаним листама. Могу постојати две врсте чворова: родитељ и дете. Коренски чвор је почетна тачка структуре која се грана на два подређена чвора, која се називају леви чвор и десни чвор.

Сваки чвор може да референцира само његов родитељ, а ми можемо прећи чворове стабла у зависности од правца. Стабло бинарног претраживања има три главна својства:

1. Леви чвор је мањи од свог родитеља.
2. Десни чвор је већи од свог родитеља.
3. Лево и десно подстабло морају бити бинарно стабло претраге.

Савршено стабло бинарне претраге се постиже када су сви нивои попуњени, а сваки чвор има леви и десни подређени чвор.

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

Основне операције бинарног стабла претраге

Сада имате бољу представу о томе шта је стабло бинарног претраживања, можемо погледати његове основне операције у наставку.

1. Операција претраге

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

С друге стране, претрага у дубину прелази стабло вертикално — почевши од коренског чвора и иде низ једну грану. Ако је циљ пронађен, операција се завршава. Али ако не, претражује друге чворове.

2. Операција уметања

Операција уметања користи операцију претраге да би одредила локацију на коју треба уметнути нови чвор. Процес почиње од основног чвора, а претрага почиње док се не стигне до одредишта. Постоје три случаја која треба размотрити са уметањем.

• Случај 1: Када чвор не постоји. Чвор који ће бити уметнут ће постати основни чвор.

• Случај 2: Нема деце. У овом случају, чвор ће се упоредити са коренским чвором. Ако је веће, постаће право дете; иначе ће постати лево дете.

• Случај 3: Када су присутни корен и његова деца. Нови чвор ће се упоредити са сваким чвором на својој путањи да би се утврдило који чвор следећи посећује. Ако је чвор већи од коренског чвора, он ће прећи низ десно подстабло или лево. Слично, на сваком нивоу се праве поређења како би се утврдило да ли ће ићи десно или лево док не стигне на одредиште.

3. Операција брисања

Операција брисања се користи за уклањање одређеног чвора унутар стабла. Брисање се сматра незгодним јер након уклањања чвора, дрво мора бити реорганизовано у складу са тим. Постоје три главна случаја за разматрање:

• Случај 1: Брисање лисног чвора. Листни чвор је чвор без деце. Ово је најлакше уклонити јер не утиче ни на један други чвор; једноставно прелазимо преко дрвета док не стигнемо до њега и избришемо га.

• Случај 2: Брисање чвора са једним дететом. Брисање родитеља са једним чвором ће довести до тога да дете заузме своју позицију, а сви наредни чворови ће се померити за један ниво. Неће бити промена у структури подстабала.

• Случај 3: Брисање чвора са двоје деце. Када морамо да уклонимо чвор са два детета, прво морамо пронаћи следећи чвор који може да заузме његову позицију. Два чвора могу заменити уклоњени чвор, наследника или претходника нереда. Наследник нереда је крајње лево дете десног подстабла, а претходник нереда је крајње десно дете левог подстабла. Копирамо садржај наследника/претходника у чвор и бришемо нередовног наследника/претходника.

Повезан: Како изградити структуре података помоћу ЈаваСцрипт ЕС6 класа

Како прећи кроз стабло бинарног претраживања

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

• Прелазак по поруџбини: Прелазак у редоследу ће произвести мапу у растућем редоследу. Овом методом почињемо од левог подстабла и настављамо до корена и десног подстабла.

• Прелазак поруџбине унапред: У овој методи, прво се посећује коренски чвор, а затим лево подстабло и десно подстабло.

• Прелазак након поруџбине: Ово обилажење подразумева посету коренском чвору последње. Почињемо од левог подстабла, затим од десног подстабла, а затим од коренског чвора.

Реал-Ворлд Апплицатионс

Дакле, како да користимо алгоритме бинарног стабла претраге? Као што се може претпоставити, изузетно су ефикасни у претраживању и сортирању. Највећа снага бинарних стабала је њихова организована структура. Омогућава да се претраживање обави изузетним брзинама тако што се количина података које требамо анализирати преполови по пролазу.

Стабла бинарног претраживања нам омогућавају да ефикасно одржавамо динамички променљив скуп података у организованом облику. За апликације које често убацују и уклањају податке, оне су од велике помоћи. Мотори за видео игре користе алгоритам заснован на стаблима познатим као бинарна партиција простора како би помогли у уређењу објеката. Мицрософт Екцел и већина софтвера за прорачунске табеле користе бинарна стабла као основну структуру података.

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

Стабла бинарне претраге: Савршена почетна тачка

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

15 метода ЈаваСцрипт низа које би требало да савладате данас

Желите да разумете ЈаваСцрипт низове, али не можете да се ухватите у коштац са њима? Погледајте наше примере ЈаваСцрипт низова за смернице.

Реад Нект

О аутору