Algajate juhend kahendpuude jaoks

Kui olete läbinud arvutiteaduse kraadi andmestruktuuride kursuse või olete iseõppinud programmeerija, olete tõenäoliselt kohanud mõistet „binaarpuud”. Kuigi need võivad tunduda pisut üle jõu käivad ja keerulised, on kahendpuu mõiste üsna lihtne.

Loe edasi, kui me lahkame binaarpuid ja miks nad on programmeerijate jaoks vajalik põhikontseptsioon.

Mis on kahendpuud?

Binaarpuud on üks esimesi andmestruktuure, mida õpilastele andmestruktuuride kursusel õpetatakse. Binaarpuu koosneb paljudest sõlmedest ja iga binaarpuu sõlm sisaldab kahte kursorit, mis näitavad vasakut ja paremat alamandmesõlme.

Kahendpuu esimest sõlme nimetatakse juureks. Puu viimase taseme sõlmi nimetatakse lehtedeks.

Iga sõlm sisaldab andmeüksust ja kahte sõlme viit. Tühja binaarpuud tähistab null -osuti. Nagu olete juba aru saanud, võib binaarpuudel olla ainult kaks last (sellest ka nimi).

Kahendpuude struktuuride tüübid

Sõltuvalt sõlmede paigutusviisist on mitu erinevat kahendpuu struktuuri. Binaarpuud nimetatakse täisbinaarpuuks, kui puu igal sõlmel on kas null või kaks last. Täiuslikus binaarpuus on kõigil sõlmedel kaks last ja lehed kõik samal sügavusel.

Seotud: Parimad viisid tasuta koodide õppimiseks

Täielikul kahendpuul on sõlmed täidetud igal tasandil, välja arvatud viimane tase. Täielikes kahendpuudes on sõlmed koondunud juure vasakule küljele. Teine levinud struktuur on tasakaalustatud binaarpuu; selles struktuuris peavad parema ja vasaku alampuu kõrgused erinema maksimaalselt ühe võrra. Samuti on nõutav, et vasak ja parem alampuu peavad olema tasakaalus.

Oluline on märkida, et tasakaalustatud kahendpuu kõrgus on O (logn), kus n on puu sõlmede arv.

Mõnel juhul, kui igal sõlmel on ainult üks vasak või parem laps, võib binaarpuust saada viltu binaarpuu. Seejärel käitub see nagu lingitud loend, selliseid puid nimetatakse ka mandunud puuks.

Mis on binaarsed otsimispuud?

Binaarne otsingupuu (BST) on sisuliselt tellitud binaarpuu, millel on spetsiaalne omadus, mida tuntakse kui "binaarse otsingupuu" omadust. BST atribuut tähendab, et sõlmed, mille võtmeväärtus on väiksem kui juur, paigutatakse vasakusse alampuusse ja sõlmed, mille võtmeväärtus on suurem kui juur, on osa paremast alampuust.

BST atribuut peab olema tõene iga järgneva puus oleva vanemasõlme jaoks.

Binaarotsingu puud pakuvad kiiret sisestamist ja otsimist. Sisestamis-, kustutamis- ja otsingutoimingute halvima aja keerukus on O (n), mis sarnaneb lingitud loendiga.

Binaarpuude eelised

Binaarpuud pakuvad palju eeliseid, mistõttu on need endiselt väga kasulik andmestruktuur. Neid saab kasutada andmestiku struktuuriliste seoste ja hierarhiate näitamiseks. Veelgi olulisem on see, et kahendpuud võimaldavad tõhusat otsimist, kustutamist ja sisestamist.

Samuti on binaarpuu rakendamine ja hooldamine väga lihtne. Kahendpuu pakub programmeerijatele tellitud massiivi ja lingitud loendi eeliseid; binaarpuus otsimine on sama kiire kui sorteeritud massiivis ning sisestus- või kustutamistoimingud on sama tõhusad kui lingitud loendites.

Kahendpuud on olulised andmestruktuurid

Binaarpuud on väga oluline andmestruktuur ja on ülioluline, et programmeerijad saaksid neid oma programmides mugavalt rakendada. Sageli küsivad intervjueerijad lihtsaid binaarpuuprobleeme, nagu läbimine, maksimaalne sügavus, peegeldamine jne.

Soovitame tungivalt mõista binaarpuu kontseptsiooni ja tutvuda tüüpiliste intervjuuprobleemidega.

TreeViz: lihtne viis andmestruktuuride visualiseerimiseks

Loe edasi

Autori kohta