Dvejetainis paieškos medis – struktūrizuota duomenų bazė, kurioje yra mazgų, dvi nuorodos į kitus mazgus, dešinėje ir kairėje. Mazgai yra klasės objektas, kuriame yra duomenų, o NULL yra ženklas, žymintis medžio pabaigą.
Jis dažnai vadinamas BST, kuris turi ypatingą savybę: mazgai, didesni už šaknį, yra jo dešinėje, o mažesni – kairėje.
Bendroji teorija ir terminija
Dvejetainėje paieškos medyje kiekvienas mazgas, išskyrus šaknį, yra sujungtas nukreipta briauna iš vieno mazgo į kitą, kuri vadinama pirminiu. Kiekvienas iš jų gali būti prijungtas prie savavališko skaičiaus mazgų, vadinamų vaikais. Mazgai be „vaikų“vadinami lapais (išoriniais mazgais). Elementai, kurie nėra lapai, vadinami vidiniais. Mazgai, turintys tą patį tėvą, yra broliai ir seserys. Viršutinis mazgas vadinamas šaknimis. BST priskirkite elementą kiekvienam mazgui ir įsitikinkite, kad jiems nustatyta speciali ypatybė.
Medžio terminologija:
- Mazgo gylis yra briaunų, apibrėžtų nuo šaknies iki jo, skaičius.
- Mazgo aukštis yra briaunų, apibrėžtų nuo jo iki giliausio lapo, skaičius.
- Medžio aukštis nustatomas pagal šaknies aukštį.
- Dvejetainis paieškos medis yra specialus dizainas, jis užtikrina geriausią aukščio ir mazgų skaičiaus santykį.
- Aukštis h su N mazgų daugiausia O (log N).
Tai galite lengvai įrodyti skaičiuodami kiekvieno lygio mazgus, pradedant nuo šaknies, darant prielaidą, kad jame yra didžiausias jų skaičius: n=1 + 2 + 4 + … + 2 h-1 + 2 h.=2 h + 1 - 1 Išsprendus tai h gauname h=O (log n).
Medienos privalumai:
- Atspindėkite struktūrinius duomenų ryšius.
- Naudojama hierarchijoms pavaizduoti.
- Užtikrinkite veiksmingą diegimą ir paiešką.
- Medžiai yra labai lankstūs duomenys, leidžiantys perkelti pomedžius su minimaliomis pastangomis.
Paieškos metodas
Apskritai, norėdami nustatyti, ar reikšmė yra BST, paleiskite dvejetainį paieškos medį nuo jo šaknies ir nustatykite, ar jis atitinka reikalavimus:
- būti šaknyje;
- būti kairiajame šaknies pomedyje;
- dešiniajame šaknies pomedyje.
Jei nepatenkintas joks bazinis registras, atitinkamame submedyje atliekama rekursinė paieška. Iš tikrųjų yra dvi pagrindinės parinktys:
- Medis tuščias – grąžinkite klaidingą.
- Vertė yra šakniniame mazge – grąžinkite true.
Pažymėtina, kad dvejetainis paieškos medis su sukurta schema visada pradeda paiešką kelyje nuo šaknies iki lapo. Blogiausiu atveju eina iki pat lapo. Todėl blogiausias laikas yra proporcingas ilgiausio kelio nuo šaknies iki lapo ilgiui, kuris yra medžio aukštis. Apskritai, tai yra tada, kai reikia žinoti, kiek laiko užtrunka ieškoti kaip medyje saugomų reikšmių skaičiaus funkciją.
Kitaip tariant, yra ryšys tarp BST mazgų skaičiaus ir medžio aukščio, priklausomai nuo jo „formos“. Blogiausiu atveju mazgai turi tik vieną atžalą, o subalansuotas dvejetainis paieškos medis iš esmės yra susietas sąrašas. Pavyzdžiui:
50
/
10
15
30
/
20
Šis medis turi 5 mazgus, o aukštis=5. Norint rasti reikšmes diapazone 16-19 ir 21-29, reikės nueiti toliau nurodytą kelią nuo šaknies iki lapo (mazgo, kuriame yra reikšmė 20), t.y., tai užtruks proporcingai mazgų skaičiui. Geriausiu atveju jie visi turi 2 vaikus, o lapai yra viename gylyje.
Šiame dvejetainiame paieškos medyje yra 7 mazgai, o aukštis=3. Paprastai tokio medžio (viso medžio) aukštis bus maždaug log 2 (N), kur N yra mazgų skaičius medyje.. Log 2 (N) reikšmė yra skaičius, kiek kartų (2) N galima padalyti prieš pasiekiant nulį.
Apibendrinant: blogiausias laikas, reikalingas paieškai BST, yra O (medžio aukštis). Blogiausiu atveju „linijinis“medis yra O(N), kur N yra medžio mazgų skaičius. Geriausiu atveju „užbaigtas“medis yra O(log N).
BST dvejetainis įterpimas
Galvoju, kur turėtų būtinaujas mazgas yra BST, reikia suprasti logiką, jis turi būti dedamas ten, kur vartotojas jį randa. Be to, turite atsiminti taisykles:
- Dublikatai neleidžiami, bandant įterpti pasikartojančią reikšmę bus padaryta išimtis.
- Viešojo įterpimo metodas naudoja pagalbinį rekursyvų „pagalbininko“metodą, kad iš tikrųjų būtų įterptas.
- Magas su nauja verte visada įterpiamas kaip lapas BST.
- Viešojo įterpimo metodas grąžina galiojantį, bet pagalbinis metodas grąžina BSTmazgą. Tai daroma tam atvejui, kai jam perduotas mazgas yra nulinis.
Apskritai, pagalbinis metodas rodo, kad jei pradinis dvejetainis paieškos medis yra tuščias, rezultatas yra medis su vienu mazgu. Kitu atveju rezultatas bus rodyklė į tą patį mazgą, kuris buvo perduotas kaip argumentas.
Ištrynė dvejetainiame algoritme
Kaip ir galima tikėtis, ištrynus elementą reikia rasti mazgą, kuriame yra pašalintina reikšmė. Šiame kode yra keletas dalykų:
- BST naudoja pagalbinį, perkrauto trynimo metodą. Jei elemento, kurio ieškote, nėra medyje, pagalbinis metodas galiausiai bus iškviestas su n==null. Tai nelaikoma klaida, medis šiuo atveju tiesiog nesikeičia. Ištrynimo pagalbinės priemonės metodas grąžina reikšmę – žymeklį į atnaujintą medį.
- Pašalinus lapą, pašalinus iš dvejetainio paieškos medžio atitinkamas antrinis pirminio elemento žymeklis nustatomas į nulį arba šaknies rodyklė į nulį, jei pašalinamasmazgas yra šaknis ir neturi vaikų.
- Atkreipkite dėmesį, kad trynimo iškvietimas turi būti vienas iš šių: root=delete (root, key), n.setLeft (delete (n.getLeft (), klavišas)), n.setRight (delete(n. getRight(), raktas)). Taigi visais trim atvejais teisinga, kad trynimo metodas tiesiog grąžina nulį.
- Kai pavyksta ieškoti mazgo, kuriame yra trintina reikšmė, yra trys parinktys: norimas ištrinti mazgas yra lapas (neturi vaikų), naikinamasis mazgas turi vieną antrį, jis turi du vaikai.
- Kai pašalinamame mazge yra vienas vaikas, galite tiesiog pakeisti jį vaiku, grąžindami žymeklį į vaiką.
- Jei norimas ištrinti mazgas turi nulį arba 1 antrinį, tada ištrynimo metodas „suks keliu“nuo šaknies iki to mazgo. Taigi blogiausias laikas yra proporcingas medžio aukščiui tiek ieškant, tiek įterpiant.
Jei mazgas, kurį reikia pašalinti, turi du vaikus, atliekami šie veiksmai:
- Raskite mazgą, kurį norite ištrinti, vadovaudamiesi keliu nuo šaknies iki jo.
- Raskite mažiausią v reikšmę dešiniajame pomedyje, tęsdami kelią iki lapo.
- Rekursyviai pašalinkite v reikšmę, eikite tuo pačiu keliu, kaip ir 2 veiksme.
- Taigi, blogiausiu atveju kelias nuo šaknies iki lapo atliekamas du kartus.
Kelionių tvarka
Perėjimas yra procesas, kuris aplanko visus medžio mazgus. Kadangi C dvejetainis paieškos medis yra nelinijinė duomenų struktūra, nėra unikalaus perėjimo. Pavyzdžiui, kartais keli važiavimo algoritmaisugrupuoti į šiuos du tipus:
- kirtimo gylis;
- pirmas leidimas.
Yra tik viena pločio kirtimo rūšis – lygio apėjimas. Šis važiavimas aplanko mazgus lygiu žemyn ir kairėje, viršuje ir dešinėje.
Yra trys skirtingi gylio kirtimų tipai:
- Išankstinis užsakymas – pirmiausia aplankykite tėvą, o tada kairįjį ir dešinįjį vaiką.
- Passing InOrder – kairiojo vaiko, tada tėvo ir dešiniojo vaiko lankymas.
- Pastovėjęs užsakymas – aplankykite kairįjį vaiką, tada dešinį vaiką, tada tėvą.
Keturių dvejetainio paieškos medžio perėjimų pavyzdys:
- Išankstinis užsakymas – 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- Užsakymas – 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- PostOrder – 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder – 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Paveikslėlyje parodyta mazgų lankymosi tvarka. Skaičius 1 yra pirmas mazgas tam tikro važiavimo metu, o 7 yra paskutinis mazgas.
Šios bendros kelionės gali būti pavaizduotos kaip vienas algoritmas, darant prielaidą, kad kiekvienas mazgas aplankomas tris kartus. Eulerio turas yra pasivaikščiojimas aplink dvejetainį medį, kurio kiekvienas kraštas traktuojamas kaip siena, kurios vartotojas negali kirsti. Šiame žingsnyje kiekvienas mazgas bus aplankytas arba kairėje, arba apačioje, arba dešinėje. Eulerio turas, aplankantis kairėje esančius mazgus, leidžia apeiti prielinksnį. Kai aplankomi žemiau esantys mazgai, jie perkeliami eilės tvarka. O kai aplankomi mazgai dešinėje – gaukitežingsnis po žingsnio apėjimas.
Navigacija ir derinimas
Kad būtų lengviau naršyti medyje, sukurkite funkcijas, kurios pirmiausia patikrintų, ar tai kairysis, ar dešinysis vaikas. Norint pakeisti mazgo padėtį, pirminiame mazge turi būti lengva prieiga prie žymeklio. Teisingai įdiegti medį yra labai sunku, todėl reikia žinoti ir taikyti derinimo procesus. Dvejetainis paieškos medis su įgyvendinimu dažnai turi rodyklių, kurios iš tikrųjų nenurodo važiavimo krypties.
Norint tai išsiaiškinti, naudojama funkcija, kuri patikrina, ar medis gali būti teisingas, ir padeda rasti daug klaidų. Pavyzdžiui, patikrinama, ar pirminis mazgas yra antrinis mazgas. Naudojant assert(is_wellformed(root)) daug klaidų galima pastebėti per anksti. Naudodami keletą šioje funkcijoje nurodytų lūžio taškų, taip pat galite tiksliai nustatyti, kuris žymeklis neteisingas.
Funkcija Konsolenausgabe
Ši funkcija perkelia visą medį į konsolę, todėl yra labai naudinga. Medžio išvesties tikslo vykdymo tvarka yra tokia:
- Norėdami tai padaryti, pirmiausia turite nustatyti, kokia informacija bus išvesta per mazgą.
- Ir jūs taip pat turite žinoti, koks platus ir aukštas yra medis, kad atsiskaitytumėte, kiek vietos palikti.
- Toliau pateiktos funkcijos apskaičiuoja šią medžio ir kiekvieno pomedžio informaciją. Kadangi į konsolę galite rašyti tik eilutę po eilutės, taip pat turėsite spausdinti medžio eilutę po eilutės.
- Dabar mums reikia kito būdo pasitrauktivisas medis, o ne tik eilutė po eilutės.
- Naudodami iškelties funkciją, galite nuskaityti medį ir žymiai pagerinti išvesties algoritmą, kiek tai susiję su greičiu.
Tačiau šią funkciją bus sunku naudoti dideliems medžiams.
Kopijuoti konstruktorių ir naikintuvą
Kadangi medis nėra triviali duomenų struktūra, geriau įdiegti kopijavimo konstruktorių, naikintuvą ir priskyrimo operatorių. Destruktorius lengva įdiegti rekursyviai. Labai dideliems medžiams jis gali susidoroti su „krūvos perpildymu“. Šiuo atveju jis formuluojamas iteratyviai. Idėja yra pašalinti lapą, kuris reiškia mažiausią visų lapų vertę, todėl jis yra kairėje medžio pusėje. Nupjovus pirmuosius lapus atsiranda naujų, o medis traukiasi, kol galiausiai nustoja egzistuoti.
Kopijavimo konstruktorius taip pat gali būti įdiegtas rekursyviai, tačiau būkite atsargūs, jei bus padaryta išimtis. Priešingu atveju medis greitai pasidaro painus ir linkęs į klaidas. Štai kodėl pirmenybė teikiama kartotinei versijai. Idėja yra pereiti per seną medį ir per naują medį, kaip tai darytumėte destruktoriumi, klonuojant visus mazgus, esančius sename medyje, bet ne naujus.
Šiuo metodu dvejetainio paieškos medžio diegimas visada yra sveikos būsenos ir naikintojas gali jį pašalinti net esant neužbaigtai. Jei įvyksta išimtis, tereikia nurodyti naikintojui ištrinti pusgaminį medį. priskyrimo operatoriusgalima lengvai įdiegti naudojant Kopijuoti ir pakeisti.
Dvejetainės paieškos medžio kūrimas
Optimalūs dvejetainiai paieškos medžiai yra neįtikėtinai veiksmingi, jei jie tinkamai tvarkomi. Kai kurios dvejetainių paieškos medžių taisyklės:
- Pirminis mazgas turi daugiausia 2 antrinius mazgus.
- Kairysis antrinis mazgas visada yra mažesnis už pirminį mazgą.
- Tinkamas antrinis mazgas visada yra didesnis už pirminį mazgą arba jam lygus.
Masyvas, kuris bus naudojamas dvejetainiam paieškos medžiui kurti:
- Pagrindinis sveikųjų skaičių masyvas iš septynių reikšmių nerūšiuota tvarka.
- Pirmoji reikšmė masyve yra 10, todėl pirmasis žingsnis kuriant medį yra sukurti 10 šaknies mazgą, kaip parodyta čia.
- Su šakninių mazgų rinkiniu visos kitos reikšmės bus šio mazgo antrinės reikšmės. Remiantis taisyklėmis, pirmas žingsnis, kurį reikia atlikti norint pridėti 7 prie medžio, yra palyginti jį su šaknies mazgu.
- Jei reikšmė 7 yra mažesnė nei 10, ji taps kairiuoju antriniu mazgu.
- Jei reikšmė 7 yra didesnė arba lygi 10, ji pasislinks į dešinę. Kadangi žinoma, kad 7 yra mažesnis nei 10, jis nurodomas kaip kairysis antrinis mazgas.
- Rekursyviai palyginkite kiekvieną elementą.
- Vykdydami tą patį modelį, atlikite tą patį palyginimą su 14-a masyvo reikšme.
- Palyginus reikšmę 14 su šakniniu mazgu 10, žinant, kad 14 yra tinkamas vaikas.
- Einant per masyvą,atvykti į 20.
- Pradėkite palygindami masyvą su 10, atsižvelgiant į tai, kuris yra didesnis. Taigi pereikite į dešinę ir palyginkite su 14 metų, jam daugiau nei 14 metų, o dešinėje neturi vaikų.
- Dabar yra 1 reikšmė. Vadovaudamiesi tuo pačiu modeliu kaip ir kitos vertės, palyginkite 1 su 10, pereidami į kairę ir palygindami su 7 ir galiausiai su 1 kairiuoju 7-ojo mazgo antruoju.
- Jei reikšmė yra 5, palyginkite ją su 10. Kadangi 5 yra mažesnė nei 10, pereikite į kairę ir palyginkite su 7.
- Žinodami, kad 5 yra mažesnis nei 7, eikite žemyn medžiu ir palyginkite 5 su 1 reikšme.
- Jei 1 neturi vaikų, o 5 yra didesnis nei 1, tada 5 yra tinkamas 1 mazgo antrinis skaičius.
- Pagaliau į medį įterpkite reikšmę 8.
- Kai 8 yra mažesnis nei 10, perkelkite jį į kairę ir palyginkite su 7, o 8 yra didesnis nei 7, todėl perkelkite jį į dešinę ir užpildykite medį, kad 8 būtų tinkamas 7 vaikas.
Paprastos optimalių dvejetainių paieškos medžių elegancijos gavimas ir įvertinimas. Kaip ir daugelis programavimo temų, dvejetainių paieškos medžių galia atsiranda dėl jų gebėjimo padalyti duomenis į mažus, susijusius komponentus. Nuo šiol su visu duomenų rinkiniu galėsite dirbti organizuotai.
Galimos dvejetainės paieškos problemos
Dvejetainės paieškos medžiai yra puikūs, tačiau reikia atsiminti keletą įspėjimų. Paprastai jie yra veiksmingi tik tada, kai yra subalansuoti. Subalansuotas medis yra medis, kuriameskirtumas tarp bet kurio medžio mazgo pomedžių aukščių yra daugiausia vienas. Pažvelkime į pavyzdį, kuris gali padėti paaiškinti taisykles. Įsivaizduokime, kad masyvas prasideda kaip rūšiuojamas.
Jei bandysite paleisti dvejetainį paieškos medžio algoritmą šiame medyje, jis veiks tiksliai taip, lyg tiesiog kartotųsi masyve, kol bus rasta norima reikšmė. Dvejetainės paieškos galia slypi gebėjime greitai išfiltruoti nepageidaujamas reikšmes. Kai medis nesubalansuotas, jis neduos tokios pat naudos kaip subalansuotas medis.
Kurdamas dvejetainį paieškos medį, labai svarbu ištirti duomenis, su kuriais vartotojas dirba. Prieš įdiegdami dvejetainį sveikųjų skaičių paieškos medį, galite integruoti įprastas procedūras, pvz., masyvo atsitiktinių imčių nustatymą, kad jį subalansuotumėte.
Dvejetainės paieškos skaičiavimo pavyzdžiai
Turime nustatyti, koks medis atsiras, jei 25 bus įterptas į šį dvejetainį paieškos medį:
10
/
/
5 15
/ /
/ /
2 12 20
Įterpiant x į medį T, kuriame dar nėra x, raktas x visada įdedamas į naują lapą. Atsižvelgiant į tai, naujasis medis atrodys taip:
10
/
/
5 15
/ /
/ /
2 12 20
25
Kokį medį gautumėte, jei į šį dvejetainį paieškos medį įterptumėte 7?
10
/
/
5 15
/ /
/ /
2 12 20
Atsakymas:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Dvejetainis paieškos medis gali būti naudojamas bet kuriam objektui saugoti. Dvejetainio paieškos medžio, o ne susieto sąrašo, naudojimo pranašumas yra tas, kad jei medis yra pakankamai subalansuotas ir labiau panašus į „pilną“medį, o ne į „linijinį“, įterpimo, paieškos ir visos trynimo operacijos gali būti įgyvendintos. O(log N) laikas.
