Шта је бинарно стабло претраживања?
Бинарно стабло претраживања је напредни алгоритам који се користи за анализу чвора, његове леве и десне гране, који су моделирани у структури стабла и враћају вредност. БСТ је осмишљен на основу архитектуре основног алгоритма бинарног претраживања; стога омогућава брже претраживање, уметање и уклањање чворова. Ово чини програм заиста брзим и тачним.
У овом упутству за структуру података научићете:
- Шта је бинарно стабло претраживања?
- Атрибути бинарног стабла претраживања
- Зашто нам је потребно бинарно стабло претраживања?
- Врсте бинарних стабала
- Како функционише бинарно дрво претраживања?
- Важни услови
Атрибути бинарног стабла претраживања
БСТ се састоји од више чворова и састоји се од следећих атрибута:
- Чворови стабла су представљени у односу родитељ-дете
- Сваки родитељски чвор може имати нула подређених чворова или максимално два подвука или подстабла на левој и десној страни.
- Свако подстабло, познато и као бинарно стабло претраживања, има подгране десно и лево од себе.
- Сви чворови су повезани паровима кључ / вредност.
- Кључеви чворова присутних на левом подстаблу су мањи од кључева њиховог родитељског чвора
- Слично томе, кључеви левог подстабла имају мање вредности од кључева свог родитељског чвора.
- Постоји главни чвор или надређени ниво 11. Испод њега се налазе леви и десни чворови / гране са сопственим вредностима кључа
- Десно подстабло има вредности кључева веће од надређеног чвора
- Лево подстабло има вредности од надређеног чвора
Зашто нам је потребно бинарно стабло претраживања?
- Два главна фактора која чине бинарно стабло претраживања оптималним решењем за било који стварни проблем су брзина и тачност.
- Због чињенице да је бинарно претраживање у формату сличном грани са односима родитеља и детета, алгоритам зна на којој локацији стабла треба тражити елементе. Ово смањује број поређења кључ / вредност које програм мора да изврши да би лоцирао жељени елемент.
- Поред тога, у случају да је елемент који треба претраживати већи или мањи од надређеног чвора, чвор зна коју страну стабла треба тражити. Разлог је тај што је лево подстабло увек мање од надређеног чвора, а десно подстабло има вредности увек једнаке или веће од надређеног чвора.
- БСТ се обично користи за примену сложених претрага, робусне логике игара, активности аутоматског довршавања и графике.
- Алгоритам ефикасно подржава операције попут претраживања, уметања и брисања.
Врсте бинарних стабала
Три врсте бинарног стабла су:
- Комплетно бинарно стабло: Сви нивои у дрвећу су пуни могућих изузетака последњег нивоа. Слично томе, сви чворови су пуни, усмеравају крајње лево.
- Потпуно бинарно стабло: Сви чворови имају 2 подређена чвора, осим листа.
- Уравнотежено или савршено бинарно стабло: У стаблу сви чворови имају двоје деце. Поред тога, постоји исти ниво сваке подврсте.
Како функционише бинарно дрво претраживања?
Стабло увек има коријенски чвор и даље подређене чворове, било лево или десно. Алгоритам изводи све операције упоређивањем вредности са кореном и његовим даљим подређеним чворовима у левом или десном подстаблу.
Зависи од елемента који се убацује, претражује или брише, након поређења алгоритам може лако испустити лево или десно подстабло основног чвора.
БСТ првенствено нуди следеће три врсте операција за вашу употребу:
- Претрага: претражује елемент из бинарног стабла
- Уметни: додаје елемент у бинарно стабло
- Делете: избришите елемент из бинарног стабла
Свака операција има своју структуру и начин извршавања / анализе, али најсложенија од свих је операција Делете.
Операција претраживања
Увек покрените стабло за анализу на кореновом чвору, а затим се померите даље у десно или лево подстабло коренског чвора у зависности од тога да ли је елемент који се налази мањи или већи од корена.
- Елемент за претрагу је 10
- Упоредите елемент са коренским чвором 12, 10 <12, па се пребацујете у лево подстабло. Нема потребе за анализом десног подстабла
- Сада упоредите 10 са чвором 7, 10> 7, па пређите на десно подстабло
- Затим упоредите 10 са следећим чвором, који је 9, 10> 9, погледајте десно поддрево дете
- 10 подударања са вредношћу у чвору, 10 = 10, враћа вредност кориснику.
Инсерт Оператион
Ово је врло директна операција. Прво се убацује коријенски чвор, а затим се упоређује следећа вредност са коренским чвором. Ако је вредност већа од корена, додаје се у десно подстабло, а ако је мања од корена, додаје се у лево подстабло.
- Постоји листа од 6 елемената које треба уметнути у БСТ редом с лева на десно
- Уметните 12 као коренски чвор и упоредите следеће вредности 7 и 9 за уметање у складу с тим у десно и лево подстабло
- Упоредите преостале вредности 19, 5 и 10 са коренским чвором 12 и сходно томе их поставите. 19> 12 га ставите као десно дете од 12, 5 <12 и 5 <7, па га ставите као лево дете од 7 година.
- Сада упоредите 10, 10 је <12 & 10 је> 7 и 10 је> 9, ставите 10 као десно подстабло од 9.
Избриши операције
Делете је најнапреднија и најсложенија међу свим осталим операцијама. У БСТ-у се води више случајева за брисање.
- Случај 1- Чвор са нула деце: ово је најлакша ситуација, само треба да избришете чвор који нема даље деце ни десно ни лево.
- Случај 2 - Чвор са једним дететом: након што избришете чвор, једноставно повежите његов подређени чвор са родитељским чвором избрисане вредности.
- Случај 3 Чвор са двоје деце: ово је најтежа ситуација и функционише по следећа два правила
- 3а - У претходнику налога: треба да избришете чвор са двоје деце и замените га највећом вредношћу у левом подстаблу избрисаног чвора
- 3б - У редоследу наследника: треба да избришете чвор са двоје деце и замените га највећом вредношћу на десном подстаблу избрисаног чвора
- Ово је први случај брисања у којем бришете чвор који нема деце. Као што видите на дијаграму, 19, 10 и 5 немају деце. Али избрисаћемо 19.
- Избришите вредност 19 и уклоните везу са чвора.
- Погледајте нову структуру БСТ-а без 19
- Ово је други случај брисања у којем бришете чвор који има 1 дете, као што можете видети на дијаграму да 9 има једно дете.
- Избришите чвор 9 и замените га подређеним 10 и додајте везу од 7 до 10
- Погледајте нову структуру БСТ-а без 9
- Овде ћете избрисати чвор 12 који има двоје деце
- Брисање чвора ће се десити на основу правила претходника по редоследу, што значи да ће га заменити највећи елемент у левом подстаблу од 12.
- Избришите чвор 12 и замените га са 10 јер је то највећа вредност на левом подстаблу
- Погледајте нову структуру БСТ-а након брисања 12
- 1 Избришите чвор 12 који има двоје деце
- 2 Брисање чвора ће се догодити на основу правила Редослед наследника, што значи да ће га заменити највећи елемент у десном подстаблу од 12
- 3 Избришите чвор 12 и замените га са 19 јер је то највећа вредност на десном подстаблу
- 4 Погледајте нову структуру БСТ-а након брисања 12
Важни услови
- Уметни - убацује елемент у дрво / ствара дрво.
- Претрага - Претражује елемент у дрвету.
- Прелазак унапред - прелази дрво на начин унапред поручен.
- Унутарње прелажење - прелази дрво редом.
- Прелазак по редоследу - прелази дрво на начин по редоследу.
Резиме
- БСТ је алгоритам напредног нивоа који изводи разне операције на основу поређења вредности чвора са коренским чвором.
- Било која од тачака у хијерархији родитељ-дете представља чвор. Барем један родитељски или коренски чвор остаје присутан све време.
- Постоје лево и десно дрво. Лево подстабло садржи вредности које су мање од коренског чвора. Међутим, десно подстабло садржи вредност која је већа од коренског чвора.
- Сваки чвор може имати нула, једно или двоје деце.
- Бинарно стабло претраживања омогућава примарне операције попут претраживања, уметања и брисања.
- Брисање као најсложеније има више случајева, на пример, чвор без детета, чвор са једним дететом и чвор са двоје деце.
- Алгоритам се користи у стварним решењима попут игара, аутоматског довршавања података и графике.