Binaarne otsingupuu – struktureeritud andmebaas, mis sisaldab sõlme, kahte linki teistele sõlmedele, paremale ja vasakule. Sõlmed on klassi objekt, millel on andmed, ja NULL on märk, mis tähistab puu lõppu.
Seda nimetatakse sageli BST-ks, millel on eriline omadus: juurest suuremad sõlmed asuvad sellest paremal ja väiksemad vasakul.
Üldine teooria ja terminoloogia
Binaarses otsingupuus on iga sõlm, välja arvatud juur, ühendatud ühest sõlmest teise suunatud servaga, mida nimetatakse vanemaks. Igaüht neist saab ühendada suvalise arvu sõlmedega, mida nimetatakse lasteks. Sõlme ilma "lasteta" nimetatakse lehtedeks (välissõlmedeks). Elemente, mis ei ole lehed, nimetatakse sisemiseks. Sama vanemaga sõlmed on õed-vennad. Ülemist sõlme nimetatakse juureks. Määrake BST-s igale sõlmele element ja veenduge, et neile oleks määratud spetsiaalne atribuut.
Puu terminoloogia:
- Sõlme sügavus on juurest kuni selleni määratletud servade arv.
- Sõlmpunkti kõrgus on sellest kuni sügavaima leheni määratud servade arv.
- Puu kõrguse määrab juure kõrgus.
- Binaarne otsingupuu on erikujundus, see pakub parimat kõrguse ja sõlmede arvu suhet.
- Kõrgus h koos N sõlmega maksimaalselt O (log N).
Seda saate hõlps alt tõestada, loendades sõlmed igal tasemel, alustades juurest, eeldades, et see sisaldab neist suurimat arvu: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Lahendades selle h jaoks, annab h=O (log n).
Puidu eelised:
- Peegeldage andmete struktuurseid seoseid.
- Kasutatakse hierarhiate tähistamiseks.
- Tagage tõhus installimine ja otsing.
- Puud on väga paindlikud andmed, mis võimaldavad teil alampuid minimaalse pingutusega teisaldada.
Otsingumeetod
Üldiselt, et teha kindlaks, kas väärtus on BST-s, käivitage binaarne otsingupuu selle juurest ja määrake, kas see vastab nõuetele:
- olema juurtes;
- ole juure vasakpoolses alampuus;
- juure paremas alampuus.
Kui ükski põhiregister pole rahuldatud, tehakse vastavas alampuus rekursiivne otsing. Põhivalikuid on tegelikult kaks:
- Puu on tühi – tagasta vale.
- Väärtus asub juursõlmes – tagasta tõene.
Tuleb tähele panna, et väljatöötatud skeemiga binaarne otsingupuu alustab alati otsimist mööda teed juurest leheni. Halvimal juhul läheb see kuni leheni. Seetõttu on halvim aeg võrdeline juurest leheni viiva pikima tee pikkusega, mis on puu kõrgus. Üldiselt on see siis, kui peate teadma, kui kaua kulub otsimiseks puusse salvestatud väärtuste arvu funktsiooni.
Teisisõnu, BST sõlmede arvu ja puu kõrguse vahel on seos, olenev alt selle kujust. Halvimal juhul on sõlmedel ainult üks laps ja tasakaalustatud binaarne otsingupuu on sisuliselt lingitud loend. Näiteks:
50
/
10
15
30
/
20
Sellel puul on 5 sõlme ja kõrgus=5. Väärtuste leidmiseks vahemikus 16-19 ja 21-29 on vaja järgmist teed juurest leheni (väärtust 20 sisaldav sõlm), st., kulub aega võrdeliselt sõlmede arvuga. Parimal juhul on neil kõigil 2 last ja lehed asuvad samal sügavusel.
Sellel binaarsel otsingupuul on 7 sõlme ja kõrgus=3. Üldiselt on sellise puu (täispuu) kõrgus ligikaudu log 2 (N), kus N on puu sõlmede arv. Log 2 väärtus (N) on kordade arv (2), mil N saab jagada enne nulli jõudmist.
Kokkuvõte: halvim aeg BST-s otsimiseks on O (puu kõrgus). Halvimal juhul "lineaarne" puu on O(N), kus N on puu sõlmede arv. Parimal juhul on "täielik" puu O(log N).
BST binaarne sisestus
Mõtleb, kus peaks olemauus sõlm asub BST-s, peate loogikast aru saama, see tuleb paigutada kohta, kus kasutaja selle leiab. Lisaks peate meeles pidama reegleid:
- Duplikaadid pole lubatud, duplikaatväärtuse sisestamise katse loob erandi.
- Avalik sisestamise meetod kasutab tegelikuks sisestamiseks abistaja-rekursiivset abimeetodit.
- Uut väärtust sisaldav sõlm lisatakse BST-sse alati lehena.
- Avaliku sisestamise meetod tagastab tühisuse, abimeetod aga BST-sõlme. See toimib juhul, kui talle edastatud sõlm on null.
Üldiselt näitab abimees, et kui algne kahendotsingupuu on tühi, on tulemuseks ühe sõlmega puu. Vastasel juhul on tulemuseks kursor samale sõlmele, mis edastati argumendina.
Kustutamine binaaralgoritmis
Nagu arvata võis, hõlmab elemendi kustutamine eemaldatavat väärtust sisaldava sõlme leidmist. Selles koodis on mitu asja:
- BST kasutab abistavat, ülekoormatud kustutamismeetodit. Kui otsitavat elementi puus ei ole, kutsutakse lõpuks abimeetod välja n==null. Seda ei peeta veaks, sel juhul puu lihts alt ei muutu. Kustutamise abistaja meetod tagastab väärtuse – osuti värskendatud puule.
- Kui leht on eemaldatud, seab binaarsest otsingupuust eemaldamine selle vanema vastava alamkursori nulliks või juure nulliks, kui eemaldatav onsõlm on juur ja sellel pole lapsi.
- Pange tähele, et kustutamiskutse peab olema üks järgmistest: root=delete (juur, võti), n.setLeft (delete (n.getLeft (), klahv)), n.setRight (delete(n. getRight(), võti)). Seega on kõigil kolmel juhul õige, et kustutamismeetod tagastab lihts alt nulli.
- Kui kustutatavat väärtust sisaldava sõlme otsing õnnestub, on kolm võimalust: kustutatav sõlm on leht (pole lapsi), kustutataval sõlmel on üks alam, sellel on kaks lapsed.
- Kui eemaldataval sõlmel on üks laps, saate selle lihts alt asendada lapsega, tuues kursori lapsele.
- Kui kustutataval sõlmel on null või 1 last, siis kustutamismeetod "jälgib teed" juurest selle sõlmeni. Seega on halvim aeg võrdeline puu kõrgusega nii otsimisel kui ka sisestamisel.
Kui eemaldataval sõlmel on kaks last, tehakse järgmised toimingud:
- Leidke kustutatav sõlm, järgides teed juurest selleni.
- Leidke parempoolsest alampuust v väikseim väärtus, jätkates mööda teed lehe poole.
- Eemaldage rekursiivselt v väärtus, järgige sama teed nagu punktis 2.
- Seega tehakse halvimal juhul tee juurest leheni kaks korda.
Läikude järjekord
Traversal on protsess, mis külastab kõiki puusõlmi. Kuna C-binaarne otsingupuu on mittelineaarne andmestruktuur, pole ainulaadset läbimist. Näiteks mõnikord mitu läbimisalgoritmirühmitatud kahte järgmist tüüpi:
- ületussügavus;
- esimene läbimine.
On ainult üks laiusületus – tasemest möödasõit. See läbimine külastab sõlmede tasandil alla ja vasakule, üleval ja paremal.
Sügavusületusi on kolme erinevat tüüpi:
- Ettetellimuse edastamine – kõigepe alt külastage vanemat ja seejärel vasakut ja paremat last.
- Järele andmine – vasaku lapse, seejärel vanema ja parema lapse külastamine.
- Järeltellimusest möödas – külastage vasakut last, siis paremat last ja siis vanemat.
Binaarse otsingupuu nelja läbimise näide:
- Ettetellimine – 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- Järjekorras – 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- Järeltellimus – 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder – 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Joonis näitab sõlmede külastamise järjekorda. Number 1 on konkreetse läbimise esimene sõlm ja 7 on viimane sõlm.
Neid üldisi läbimisi saab esitada ühe algoritmina, eeldades, et iga sõlme külastatakse kolm korda. Euleri ringkäik on jalutuskäik ümber binaarse puu, kus iga serva käsitletakse seinana, mida kasutaja ei saa ületada. Sellel jalutuskäigul külastatakse iga sõlme kas vasakul, allpool või paremal. Euleri ringkäik, mis külastab vasakpoolseid sõlme, põhjustab eessõnast möödahiilimise. Allolevate sõlmede külastamisel läbitakse need järjekorras. Ja kui külastatakse paremal asuvaid sõlme - hankigesamm-sammult möödasõit.
Navigeerimine ja silumine
Puul navigeerimise hõlbustamiseks looge funktsioonid, mis kontrollivad esm alt, kas tegemist on vasaku või parema lapsega. Sõlme asukoha muutmiseks peab olema hõlbus juurdepääs ülemsõlme kursorile. Puu õigesti rakendamine on väga keeruline, seega peate teadma ja rakendama silumisprotsesse. Rakendusega binaarsel otsingupuul on sageli viiteid, mis tegelikult ei näita liikumissuunda.
Selle kõige välja selgitamiseks kasutatakse funktsiooni, mis kontrollib, kas puu võib olla õige, ja aitab leida palju vigu. Näiteks kontrollib see, kas vanemsõlm on alamsõlm. Funktsiooni assert(is_wellformed(root)) abil saab palju vigu enneaegselt tabada. Kasutades selles funktsioonis paari antud katkestuspunkti, saate ka täpselt määrata, milline osuti on vale.
Funktsioon Konsolenausgabe
See funktsioon viib kogu puu konsooli ja on seetõttu väga kasulik. Puu väljundi eesmärgi täitmise järjekord on:
- Selleks peate esm alt määrama, milline teave sõlme kaudu väljastatakse.
- Ja peate teadma ka seda, kui lai ja kõrge on puu, et arvestada, kui palju ruumi jätta.
- Järgmised funktsioonid arvutavad selle teabe puu ja iga alampuu kohta. Kuna konsooli saab kirjutada ainult ridade kaupa, peate ka puu ridade kaupa printima.
- Nüüd vajame teist võimalust taganemisekskogu puu, mitte ainult rida-re alt.
- Tühjendusfunktsiooni abil saate lugeda puud ja väljundalgoritmi kiiruse osas oluliselt parandada.
Kuid seda funktsiooni on suurte puude puhul raske kasutada.
Kopeeri konstruktor ja hävitaja
Kuna puu ei ole triviaalne andmestruktuur, on parem rakendada koopiakonstruktorit, destruktorit ja määramisoperaatorit. Destruktorit on lihtne rekursiivselt rakendada. Väga suurte puude puhul saab ta hakkama "kuhja ülevooluga". Sel juhul sõnastatakse see iteratiivselt. Idee on eemaldada leht, mis esindab kõigist lehtedest väikseimat väärtust, nii et see asub puu vasakul küljel. Esimeste lehtede mahalõikamisel tekivad uued ja puu kahaneb kuni lõpuks lakkab olemast.
Koopiakonstruktorit saab rakendada ka rekursiivselt, kuid olge ettevaatlik, kui tehakse erand. Vastasel juhul muutub puu kiiresti segaseks ja veaohtlikuks. Seetõttu eelistatakse iteratiivset versiooni. Idee on läbida vana puu ja uus puu, nagu teeksite destruktoris, kloonides kõik sõlmed, mis on vanas puus, kuid mitte uusi.
Selle meetodi korral on binaarne otsingupuu juurutus alati terves olekus ja hävitaja saab selle eemaldada isegi mittetäieliku olekus. Kui juhtub erand, pole vaja teha muud, kui anda hävitajale poolvalmis puu kustutamine. määramise operaatorsaab hõlpsasti rakendada, kasutades kopeerimist ja vahetamist.
Binaarse otsingupuu loomine
Optimaalsed binaarsed otsingupuud on õige haldamise korral uskumatult tõhusad. Mõned binaarsete otsingupuude reeglid:
- Emasõlmel on kuni 2 alamsõlme.
- Vasak alamsõlm on alati väiksem kui emasõlm.
- Kehtiv alamsõlm on alati suurem kui emasõlm või sellega võrdne.
Massiiv, mida kasutatakse binaarse otsingupuu koostamiseks:
- Seitsme väärtusega põhitäisarvu massiiv sortimata järjekorras.
- Esimene väärtus massiivis on 10, seega on puu loomise esimene samm luua 10 juursõlm, nagu siin näidatud.
- Juursõlmede komplekti korral on kõik muud väärtused selle sõlme alamväärtused. Reeglitele viidates on esimene samm puule 7 lisamiseks võrrelda seda juursõlmega.
- Kui väärtus 7 on väiksem kui 10, muutub see vasakpoolseks alamsõlmeks.
- Kui väärtus 7 on suurem kui 10 või sellega võrdne, liigub see paremale. Kuna 7 on teadaolev alt väiksem kui 10, määratakse see vasakpoolseks alamsõlmeks.
- Võrdlege iga elementi rekursiivselt.
- Järgides sama mustrit, tehke sama võrdlus massiivi 14. väärtusega.
- Väärtuse 14 võrdlemine juursõlmega 10, teades, et 14 on õige alam.
- Massiivi läbides,tule 20.
- Alustage massiivi võrdlemisega 10-ga, olenev alt sellest, kumb on suurem. Nii et liikuge paremale ja võrrelge seda 14-ga, ta on üle 14-aastane ja tal pole paremal pool lapsi.
- Nüüd on väärtus 1. Järgides sama mustrit, mis teiste väärtustega, võrrelge 1-ga 10, liikudes vasakule ja võrreldes 7-ga ja lõpuks 7. sõlme 1 vasakpoolse lapsega.
- Kui väärtus on 5, võrrelge seda 10-ga. Kuna 5 on väiksem kui 10, liikuge vasakule ja võrrelge seda väärtusega 7.
- Teades, et 5 on väiksem kui 7, jätkake mööda puud ja võrrelge 5 väärtust 1 väärtusega.
- Kui 1-l pole lapsi ja 5 on suurem kui 1, siis 5 on 1 sõlme kehtiv alam.
- Lõpuks sisestage puusse väärtus 8.
- Kui 8 on väiksem kui 10, liigutage seda vasakule ja võrrelge seda 7-ga, 8 on suurem kui 7, nii et liigutage seda paremale ja viige puu lõpule, tehes 8-st õige lapse 7.
Optimaalsete binaarsete otsingupuude lihtsa elegantsi hankimine ja hindamine. Nagu paljud programmeerimise teemad, tuleneb binaarsete otsingupuude võimsus nende võimest eraldada andmed väikesteks seotud komponentideks. Nüüdsest saate kogu andmestikuga organiseeritult töötada.
Võimalikud binaarse otsingu probleemid
Binaarsed otsingupuud on suurepärased, kuid tuleb meeles pidada mõnda hoiatust. Tavaliselt on need tõhusad ainult siis, kui need on tasakaalus. Tasakaalustatud puu on puu, millespuu mis tahes sõlme alampuude kõrguste vahe on maksimaalselt üks. Vaatame näidet, mis võib aidata reegleid selgitada. Kujutame ette, et massiiv algab sorteeritavana.
Kui proovite sellel puul käivitada binaarse otsingupuu algoritmi, toimib see täpselt nii, nagu itereeriks massiivi, kuni soovitud väärtus leitakse. Binaarse otsingu jõud seisneb võimaluses soovimatud väärtused kiiresti välja filtreerida. Kui puu ei ole tasakaalustatud, ei paku see tasakaalustatud puuga samu eeliseid.
Binaarse otsingupuu loomisel on väga oluline uurida andmeid, millega kasutaja töötab. Enne täisarvude binaarse otsingupuu rakendamist saate selle tasakaalustamiseks integreerida rutiine, nagu massiivi randomiseerimine.
Binaarse otsingu arvutusnäited
Peame kindlaks määrama, milline puu tekib, kui järgmisse binaarsesse otsingupuusse lisatakse 25:
10
/
/
5 15
/ /
/ /
2 12 20
Sisestades x-i puusse T, mis ei sisalda veel x-i, asetatakse võti x alati uuele lehele. Seoses sellega näeb uus puu välja selline:
10
/
/
5 15
/ /
/ /
2 12 20
25
Millise puu saaksite, kui sisestaksite järgmisse binaarsesse otsingupuusse 7?
10
/
/
5 15
/ /
/ /
2 12 20
Vastus:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Binaarset otsingupuud saab kasutada mis tahes objekti salvestamiseks. Lingitud loendi asemel binaarse otsingupuu kasutamise eeliseks on see, et kui puu on mõistlikult tasakaalustatud ja sarnaneb pigem "täispuule" kui "lineaarsele", saab sisestamise, otsingu ja kõik kustutamistoimingud käivitada O(log N) aeg.