Zbatimi i një peme kërkimi binar

2024 Autor: Angel Austin | [email protected]. E modifikuara e fundit: 2023-12-17 05:41

Pema e kërkimit binar - një bazë të dhënash e strukturuar që përmban nyje, dy lidhje me nyjet e tjera, djathtas dhe majtas. Nyjet janë një objekt i klasës që ka të dhëna, dhe NULL është shenja që shënon fundin e pemës.

I referohet shpesh si BST, i cili ka një veti të veçantë: nyjet më të mëdha se rrënja ndodhen në të djathtë të saj dhe ato më të vogla në të majtë.

Teori dhe terminologji e përgjithshme

Në një pemë kërkimi binar, çdo nyje, duke përjashtuar rrënjën, është e lidhur nga një skaj i drejtuar nga një nyje në tjetrën, e cila quhet prind. Secila prej tyre mund të lidhet me një numër arbitrar nyjesh, të quajtur fëmijë. Nyjet pa "fëmijë" quhen gjethe (nyje të jashtme). Elementet që nuk janë gjethe quhen të brendshëm. Nyjet me të njëjtin prind janë vëllezër e motra. Nyja më e lartë quhet rrënja. Në BST, cakto një element për secilën nyje dhe sigurohu që ata të kenë një grup të veçantë të vetive për to.

Terminologjia e pemës:

Thellësia e një nyje është numri i skajeve të përcaktuara nga rrënja në të.
Lartësia e një nyje është numri i skajeve të përcaktuara nga ajo në fletën më të thellë.
Lartësia e pemës përcaktohet nga lartësia e rrënjës.
Pema e kërkimit binar është një dizajn i veçantë, ai siguron raportin më të mirë të lartësisë dhe numrit të nyjeve.
Lartësia h me N nyje maksimumi O (log N).

Këtë mund ta vërtetoni lehtësisht duke numëruar nyjet në çdo nivel, duke filluar nga rrënja, duke supozuar se përmban numrin më të madh të tyre: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Zgjidhja e kësaj për h jep h=O (log n).

Përfitimet e drurit:

Paraqitni marrëdhëniet strukturore të të dhënave.
Përdoret për të përfaqësuar hierarkitë.
Siguroni instalim dhe kërkim efikas.
Pemët janë të dhëna shumë fleksibël, që ju lejojnë të lëvizni nënpemë me përpjekje minimale.

Mënyra e kërkimit

Në përgjithësi, për të përcaktuar nëse një vlerë është në BST, filloni një pemë kërkimi binar në rrënjën e saj dhe përcaktoni nëse i plotëson kërkesat:

je në rrënjë;
jenë në nënpemën e majtë të rrënjës;
në nënpemën e djathtë të rrënjës.

Nëse asnjë regjistër bazë nuk është i kënaqur, një kërkim rekurziv kryhet në nënpemën përkatëse. Në fakt ekzistojnë dy opsione themelore:

Pema është bosh - ktheje false.
Vlera është në nyjen rrënjë - ktheje true.

Duhet të theksohet se një pemë kërkimi binar me një skemë të zhvilluar gjithmonë fillon të kërkojë përgjatë shtegut nga rrënja në gjethe. Në rastin më të keq, ajo shkon deri në gjethe. Prandaj, koha më e keqe është në përpjesëtim me gjatësinë e shtegut më të gjatë nga rrënja në gjethe, që është lartësia e pemës. Në përgjithësi, kjo është kur ju duhet të dini se sa kohë duhet për të kërkuar në funksion të numrit të vlerave të ruajtura në pemë.

Me fjalë të tjera, ekziston një lidhje midis numrit të nyjeve në një BST dhe lartësisë së një peme, në varësi të "formës" së saj. Në rastin më të keq, nyjet kanë vetëm një fëmijë, dhe një pemë e ekuilibruar e kërkimit binar është në thelb një listë e lidhur. Për shembull:

Kjo pemë ka 5 nyje dhe lartësi=5. Gjetja e vlerave në rangun 16-19 dhe 21-29 do të kërkojë shtegun e mëposhtëm nga rrënja në gjethe (nyja që përmban vlerën 20), d.m.th., do të duhet kohë proporcionale me numrin e nyjeve. Në rastin më të mirë, të gjithë kanë 2 fëmijë dhe gjethet janë të vendosura në të njëjtën thellësi.

Kjo pemë kërkimi binar ka 7 nyje dhe lartësi=3. Në përgjithësi, një pemë si kjo (pema e plotë) do të ketë një lartësi prej përafërsisht log 2 (N), ku N është numri i nyjeve në pemë. Vlera e log 2 (N) është numri i herëve (2) që N mund të ndahet para se të arrihet zero.

Përmbledhje: koha më e keqe që nevojitet për të kërkuar në BST është O (lartësia e pemës). Pema "lineare" e rastit më të keq është O(N), ku N është numri i nyjeve në pemë. Në rastin më të mirë, një pemë "e plotë" është O(log N).

Insert binare BST

Po pyes veten se ku duhet të jetënyja e re ndodhet në BST, ju duhet të kuptoni logjikën, ajo duhet të vendoset aty ku përdoruesi e gjen. Përveç kësaj, duhet të mbani mend rregullat:

Dublikimet nuk lejohen, përpjekja për të futur një vlerë të kopjuar do të sjellë një përjashtim.
Metoda e futjes publike përdor një metodë "ndihmëse" rekursive ndihmëse për të futur në të vërtetë.
Një nyje që përmban një vlerë të re futet gjithmonë si fletë në BST.
Metoda e insertit publik kthen void, por metoda ndihmëse kthen një BSTnode. E bën këtë për të trajtuar rastin kur nyja e kaluar tek ajo është e pavlefshme.

Në përgjithësi, metoda ndihmëse tregon se nëse pema origjinale e kërkimit binar është bosh, rezultati është një pemë me një nyje. Përndryshe, rezultati do të jetë një tregues për të njëjtën nyje që u kalua si argument.

Fshirje në algoritmin binar

Siç mund të prisni, fshirja e një elementi përfshin gjetjen e një nyje që përmban vlerën që duhet hequr. Ka disa gjëra në këtë kod:

BST përdor një metodë fshirjeje ndihmëse, të mbingarkuar. Nëse elementi që kërkoni nuk është në pemë, atëherë metoda ndihmëse do të thirret përfundimisht me n==null. Kjo nuk konsiderohet një gabim, pema thjesht nuk ndryshon në këtë rast. Metoda e ndihmës së fshirjes kthen një vlerë - një tregues në pemën e përditësuar.
Kur hiqet një fletë, heqja nga pema e kërkimit binar e vendos treguesin përkatës të fëmijës së prindit të tij në null ose rrënjën në null nëse ai që hiqet ështënyja është një rrënjë dhe nuk ka fëmijë.
Vini re se thirrja e fshirjes duhet të jetë një nga sa vijon: rrënjë=fshij (rrënja, çelësi), n.setLeft (fshij (n.getLeft (), tasti)), n.setRight (fshij(n. getRight (), çelësi)). Kështu, në të tre rastet është e saktë që metoda e fshirjes thjesht kthen null.
Kur kërkimi për nyjen që përmban vlerën që do të fshihet ka sukses, ekzistojnë tre opsione: nyja që do të fshihet është një fletë (nuk ka fëmijë), nyja që do të fshihet ka një fëmijë, ajo ka dy fëmijë.
Kur nyja që hiqet ka një fëmijë, thjesht mund ta zëvendësoni me një fëmijë, duke i kthyer një tregues fëmijës.
Nëse nyja që do të fshihet ka zero ose 1 fëmijë, atëherë metoda e fshirjes do të "ndjejë rrugën" nga rrënja në atë nyje. Pra, koha më e keqe është proporcionale me lartësinë e pemës, si për kërkimin ashtu edhe për futjen.

Nëse nyja që do të hiqet ka dy fëmijë, ndërmerren hapat e mëposhtëm:

Gjeni nyjen që do të fshihet, duke ndjekur rrugën nga rrënja drejt saj.
Gjeni vlerën më të vogël të v në nënpemën e djathtë, duke vazhduar përgjatë rrugës drejt gjethes.
Hiq rekurzivisht vlerën e v, ndiqni të njëjtën rrugë si në hapin 2.
Kështu, në rastin më të keq, rruga nga rrënja në gjethe kryhet dy herë.

Rendi i traversave

Traversal është një proces që viziton të gjitha nyjet në një pemë. Për shkak se një pemë kërkimi binar C është një strukturë jolineare e të dhënave, nuk ka asnjë kalim unik. Për shembull, ndonjëherë disa algoritme kalimigrupuar në dy llojet e mëposhtme:

thellësi kalimi;
kalimi i parë.

Ekziston vetëm një lloj kalimi i gjerësisë - anashkalimi i nivelit. Ky kalim viziton nyjet në nivele poshtë dhe majtas, lart dhe djathtas.

Ekzistojnë tre lloje të ndryshme kryqëzimesh në thellësi:

Kalimi i porosisë paraprake - fillimisht vizitoni prindin dhe më pas fëmijën e majtë dhe të djathtë.
Kalimi në Rendi - vizita e fëmijës së majtë, më pas prindit dhe fëmijës së djathtë.
Pas porosisë së postimit - vizitoni fëmijën e majtë, më pas fëmijën e djathtë, pastaj prindin.

Shembull për katër kalime të një peme kërkimi binar:

Porporosi paraprake - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
Me rend - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
Post Porosi - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Figura tregon rendin në të cilin vizitohen nyjet. Numri 1 është nyja e parë në një kalim të caktuar dhe 7 është nyja e fundit.

Këto kalime të përgjithshme mund të përfaqësohen si një algoritëm i vetëm, duke supozuar se çdo nyje vizitohet tre herë. Turneu i Euler është një shëtitje rreth një peme binare ku çdo skaj trajtohet si një mur që përdoruesi nuk mund ta kalojë. Në këtë shëtitje, çdo nyje do të vizitohet ose në të majtë, ose poshtë, ose në të djathtë. Turneu i Euler-it, i cili viziton nyjet në të majtë, bën që parafjala të anashkalohet. Kur vizitohen nyjet më poshtë, ato përshkohen me rend. Dhe kur vizitohen nyjet në të djathtë - merrnianashkalim hap pas hapi.

Navigimi dhe korrigjimi

Për ta bërë më të lehtë navigimin te pema, krijoni funksione që së pari kontrollojnë nëse janë fëmija i majtë apo i djathtë. Për të ndryshuar pozicionin e një nyje, duhet të ketë qasje të lehtë në treguesin në nyjen mëmë. Zbatimi i saktë i një peme është shumë i vështirë, kështu që ju duhet të dini dhe të aplikoni proceset e korrigjimit. Një pemë kërkimi binar me një zbatim shpesh ka tregues që në fakt nuk tregojnë drejtimin e udhëtimit.

Për ta kuptuar këtë, përdoret një funksion që kontrollon nëse pema mund të jetë e saktë dhe ndihmon për të gjetur shumë gabime. Për shembull, kontrollon nëse nyja prind është një nyje fëmijë. Me assert(is_wellformed(root)) shumë gabime mund të kapen para kohe. Duke përdorur disa pika ndërprerjesh të dhëna brenda këtij funksioni, mund të përcaktoni gjithashtu saktësisht se cili tregues është i gabuar.

Funksioni Konsolenausgabe

Ky funksion shpërndan të gjithë pemën në tastierë dhe për këtë arsye është shumë i dobishëm. Rendi në të cilin ekzekutohet qëllimi i prodhimit të pemës është:

Për ta bërë këtë, së pari duhet të përcaktoni se çfarë informacioni do të dalë nga nyja.
Dhe gjithashtu duhet të dini se sa e gjerë dhe e gjatë është pema për të llogaritur se sa hapësirë duhet të lini.
Funksionet e mëposhtme llogaritin këtë informacion për pemën dhe secilën nënpemë. Meqenëse mund të shkruani në konsolë vetëm rresht pas rreshti, do t'ju duhet gjithashtu të printoni pemën rresht pas rreshti.
Tani na duhet një mënyrë tjetër për t'u tërhequre gjithë pema, jo vetëm rresht pas rreshti.
Me ndihmën e funksionit dump, ju mund të lexoni pemën dhe të përmirësoni ndjeshëm algoritmin e daljes, për sa i përket shpejtësisë.

Megjithatë, ky funksion do të jetë i vështirë për t'u përdorur në pemë të mëdha.

Kopjo konstruktorin dhe destruktorin

Për shkak se një pemë nuk është një strukturë e parëndësishme e të dhënave, është më mirë të zbatohet një konstruktor kopjimi, një destruktor dhe një operator caktimi. Destruktori është i lehtë për t'u zbatuar në mënyrë rekursive. Për pemët shumë të mëdha, mund të përballojë "mbushjen e grumbullit". Në këtë rast, ai formulohet në mënyrë të përsëritur. Ideja është të hiqni gjethen që përfaqëson vlerën më të vogël të të gjitha gjetheve, pra të jetë në anën e majtë të pemës. Prerja e gjetheve të para krijon gjethe të reja dhe pema tkurret derisa përfundimisht të pushojë së ekzistuari.

Konstruktori i kopjes mund të zbatohet gjithashtu në mënyrë rekursive, por kini kujdes nëse hidhet një përjashtim. Përndryshe, pema shpejt bëhet konfuze dhe e prirur ndaj gabimeve. Kjo është arsyeja pse versioni përsëritës është i preferuar. Ideja është të kalojmë nëpër pemën e vjetër dhe pemën e re, siç do të bëni në destruktorin, duke klonuar të gjitha nyjet që janë në pemën e vjetër, por jo ato të reja.

Me këtë metodë, zbatimi i pemës binar të kërkimit është gjithmonë në gjendje të shëndetshme dhe mund të hiqet nga destruktori edhe në një gjendje jo të plotë. Nëse ndodh një përjashtim, gjithçka që duhet të bëni është të udhëzoni destruktorin të fshijë pemën gjysmë të gatshme. operatori i caktimitmund të zbatohet lehtësisht duke përdorur Copy & Swap.

Krijimi i një peme kërkimi binar

Pemët e kërkimit binar optimal janë tepër efikasë nëse menaxhohen siç duhet. Disa rregulla për pemët e kërkimit binar:

Një nyje prind ka më së shumti 2 nyje fëmijë.
Nyja e fëmijës së majtë është gjithmonë më e vogël se nyja prind.
Një nyje e vlefshme fëmijë është gjithmonë më e madhe ose e barabartë me nyjen prind.

Rreth që do të përdoret për të ndërtuar pemën e kërkimit binar:

Një grup bazë me numra të plotë me shtatë vlera në rend të pa renditur.
Vlera e parë në grup është 10, kështu që hapi i parë në ndërtimin e pemës është krijimi i një nyje me 10 rrënjë, siç tregohet këtu.
Me një grup nyjesh rrënjësore, të gjitha vlerat e tjera do të jenë fëmijë të kësaj nyje. Duke iu referuar rregullave, hapi i parë që duhet bërë për të shtuar 7 në pemë është ta krahasoni atë me nyjen rrënjë.
Nëse vlera 7 është më e vogël se 10, ajo do të bëhet nyja e fëmijës së majtë.
Nëse vlera 7 është më e madhe ose e barabartë me 10, ajo do të lëvizë djathtas. Meqenëse dihet se 7 është më pak se 10, ajo është caktuar si nyja e majtë e fëmijës.
Kryej krahasime në mënyrë rekursive për secilin element.
Duke ndjekur të njëjtin model, kryeni të njëjtin krahasim me vlerën e 14-të në grup.
Krahasimi i vlerës 14 me nyjen rrënjësore 10, duke ditur që 14 është fëmija i duhur.
Duke ecur nëpër grup,eja në 20.
Filloni duke krahasuar grupin me 10, cilado që të jetë më e madhe. Pra, lëvizni djathtas dhe krahasojeni me 14, ai është mbi 14 vjeç dhe nuk ka fëmijë në të djathtë.
Tani ka një vlerë prej 1. Duke ndjekur të njëjtin model si vlerat e tjera, krahasoni 1 me 10, duke lëvizur majtas dhe duke krahasuar me 7 dhe në fund me 1 fëmijën e majtë të nyjës së 7-të.
Nëse vlera është 5, krahasojeni me 10. Meqenëse 5 është më pak se 10, kaloni majtas dhe krahasojeni me 7.
Duke ditur që 5 është më pak se 7, vazhdoni poshtë pemës dhe krahasoni 5 me 1 vlerë.
Nëse 1 nuk ka fëmijë dhe 5 është më i madh se 1, atëherë 5 është një fëmijë i vlefshëm i 1 nyje.
Më në fund fut vlerën 8 në pemë.
Kur 8 është më pak se 10, zhvendoseni në të majtë dhe krahasojeni me 7, 8 është më i madh se 7, kështu që zhvendoseni në të djathtë dhe plotësoni pemën, duke e bërë 8 një fëmijë të duhur prej 7.

Marrja dhe vlerësimi i elegancës së thjeshtë të pemëve optimale të kërkimit binar. Ashtu si shumë tema në programim, fuqia e pemëve të kërkimit binar vjen nga aftësia e tyre për të zgjidhur të dhënat në komponentë të vegjël të lidhur. Që tani e tutje, ju mund të punoni me të dhënat e plota në mënyrë të organizuar.

Çështje të mundshme të kërkimit binar

Pemët e kërkimit binar janë të shkëlqyera, por ka disa paralajmërime që duhen mbajtur parasysh. Zakonisht ato janë efektive vetëm nëse janë të balancuara. Një pemë e ekuilibruar është një pemë në të cilëndiferenca midis lartësive të nënpemëve të çdo nyjeje në pemë është më së shumti një. Le të shohim një shembull që mund të ndihmojë në sqarimin e rregullave. Le të imagjinojmë që grupi fillon si i renditshëm.

Nëse provoni të ekzekutoni një algoritëm binar të pemës së kërkimit në këtë pemë, ai do të funksionojë tamam sikur të ishte duke u përsëritur nëpër grup derisa të gjendet vlera e dëshiruar. Fuqia e kërkimit binar qëndron në aftësinë për të filtruar shpejt vlerat e padëshiruara. Kur një pemë nuk është e ekuilibruar, ajo nuk do të japë të njëjtat përfitime si një pemë e ekuilibruar.

Është shumë e rëndësishme të shqyrtohen të dhënat me të cilat po punon përdoruesi kur krijon një pemë kërkimi binar. Ju mund të integroni rutina të tilla si randomizimi i grupeve përpara se të zbatoni një pemë kërkimi binar për numra të plotë për ta balancuar atë.

Shembuj të llogaritjes së kërkimit binar

Ne duhet të përcaktojmë se çfarë lloj peme do të rezultojë nëse 25 futet në pemën e mëposhtme të kërkimit binar:

5 15

/ /

2 12 20

Kur futet x në një pemë T që nuk përmban ende x, çelësi x vendoset gjithmonë në një fletë të re. Në lidhje me këtë, pema e re do të duket si:

5 15

/ /

2 12 20

Çfarë lloj peme do të merrnit nëse do të futnit 7 në pemën e mëposhtme të kërkimit binar?

5 15

/ /

2 12 20

Përgjigje:

5 15

/ / /

2 7 12 20

Një pemë kërkimi binar mund të përdoret për të ruajtur çdo objekt. Avantazhi i përdorimit të një peme kërkimi binar në vend të një liste të lidhur është se nëse pema është e balancuar në mënyrë të arsyeshme dhe më shumë si një pemë "e plotë" sesa një "lineare", futja, kërkimi dhe të gjitha operacionet e fshirjes mund të zbatohen për t'u ekzekutuar në Koha O(log N).