Pirma, mes suprasime dvejetainis medis ir dvejetainis paieškos medis atskirai, tada pažvelgsime į dvejetainio medžio ir dvejetainio paieškos medžio skirtumus.

Kas yra dvejetainis medis?

A Dvejetainis medis yraRodyklė į kairįjį vaiką:Jame saugoma kairiojo antrinio mazgo nuoroda.Rodyklė į tinkamą vaiką:Jame saugoma dešiniojo antrinio mazgo nuoroda.Duomenų elementas:Duomenų elementas yra duomenų, kuriuos saugo mazgas, reikšmė.

Dvejetainis medis gali būti pavaizduotas taip:

Aukščiau pateiktame paveikslėlyje galime pastebėti, kad kiekviename mazge yra daugiausia 2 vaikai. Jei kuriame nors mazge nėra kairiojo ar dešiniojo antrinio atvejo, rodyklės reikšmė to vaiko atžvilgiu būtų NULL.

Pagrindinės dvejetainio medžio terminijos yra šios:

Šakninis mazgas:Šakninis mazgas yra pirmasis arba aukščiausias dvejetainio medžio mazgas.Pirminis mazgas:Kai mazgas yra prijungtas prie kito mazgo per kraštus, tada tas mazgas yra žinomas kaip pirminis mazgas. Dvejetainiame medyje pirminis mazgas gali turėti daugiausia 2 antrinius elementus.Antrinis mazgas:Jei mazgas turi savo pirmtaką, tada tas mazgas yra žinomas kaip a vaiko mazgas .Lapo mazgas:Mazgas, kuriame nėra jokio vaiko, žinomo kaip a lapo mazgas .Vidinis mazgas:Mazgas, kuriame yra bent 2 vaikai, žinomas kaip an vidinis mazgas .Mazgo gylis:Atstumas nuo šakninio mazgo iki nurodyto mazgo yra žinomas kaip a mazgo gylis . Mes suteikiame etiketes visiems mazgams, pavyzdžiui, šakninis mazgas yra pažymėtas 0, nes neturi gylio, šakninio mazgo vaikai žymimi 1, šakninio vaiko vaikai žymimi 2.Aukštis:Ilgiausias atstumas nuo šaknies mazgo iki lapo mazgo yra mazgo aukštis .

Dvejetainiame medyje yra vienas medis, žinomas kaip a tobulas dvejetainis medis . Tai yra medis, kuriame visuose vidiniuose mazguose turi būti du mazgai, o visi lapų mazgai turi būti tame pačiame gylyje. Tobulo dvejetainio medžio atveju bendras dvejetainiame medyje esančių mazgų skaičius gali būti apskaičiuojamas naudojant šią lygtį:

n = 2^m+1-1

kur n yra mazgų skaičius, m yra mazgo gylis.

Kas yra dvejetainės paieškos medis?

A Dvejetainis paieškos medis yra medis, kuris pagal tam tikrą elementų išdėstymo tvarką, o dvejetainis medis nesilaiko jokios tvarkos. Dvejetainėje paieškos medyje kairiojo mazgo reikšmė turi būti mažesnė nei pirminio mazgo, o dešiniojo mazgo reikšmė turi būti didesnė už pirminio mazgo.

Supraskime dvejetainio paieškos medžio sąvoką per pavyzdžius.

Aukščiau pateiktame paveikslėlyje galime pastebėti, kad šakninio mazgo reikšmė yra 15, o tai yra didesnė už visų kairiojo pomedžio mazgų vertę. Šakninio mazgo reikšmė yra mažesnė už visų dešiniojo pomedžio mazgų reikšmes. Dabar pereiname prie šakninio mazgo kairiojo antrinio. 10 yra didesnis nei 8 ir mažesnis nei 12; ji taip pat atitinka dvejetainio paieškos medžio savybę. Dabar pereiname prie šakninio mazgo dešiniojo antrosios pusės; reikšmė 20 yra didesnė nei 17 ir mažesnė nei 25; ji taip pat atitinka dvejetainio paieškos medžio savybę. Todėl galime sakyti, kad aukščiau parodytas medis yra dvejetainis paieškos medis.

Dabar, jei pakeisime 12 reikšmę į 16 aukščiau esančiame dvejetainiame medyje, turime išsiaiškinti, ar tai vis dar dvejetainis paieškos medis, ar ne.

java eilutė į int

Šakninio mazgo reikšmė yra 15, kuri yra didesnė nei 10, bet mažesnė nei 16, todėl ji neatitinka dvejetainio paieškos medžio savybių. Todėl tai nėra dvejetainis paieškos medis.

Operacijos dvejetainėje paieškos medyje

Dvejetainiame paieškos medyje galime atlikti įterpimo, trynimo ir paieškos operacijas. Supraskime, kaip paieška atliekama dvejetainėje paieškoje. Žemiau parodytas dvejetainis medis, kuriame turime atlikti paieškos operaciją:

Tarkime, kad turime ieškoti 10 aukščiau esančiame dvejetainiame medyje. Norėdami atlikti dvejetainę paiešką, apsvarstysime visus sveikuosius skaičius surūšiuotame masyve. Pirmiausia paieškos erdvėje sukuriame visą sąrašą, o visi skaičiai bus paieškos erdvėje. Paieškos vieta pažymėta dviem rodyklėmis, ty pradžia ir pabaiga. Aukščiau pateikto dvejetainio medžio masyvas gali būti pavaizduotas kaip

Pirmiausia apskaičiuosime vidurinį elementą ir palyginsime vidurinį elementą su elementu, kurio reikia ieškoti. Vidurinis elementas apskaičiuojamas naudojant n/2. n reikšmė yra 7; todėl vidurinis elementas yra 15. Vidurinis elementas nėra lygus ieškomam elementui, t.y., 10.

Pastaba: jei ieškomas elementas yra mažesnis už vidurinį elementą, tada paieška bus atliekama kairėje pusėje; kitu atveju paieška bus atliekama dešinėje pusėje. Lygybės atveju elementas randamas.

Kadangi elementas, kurio reikia ieškoti, yra mažesnis už vidurinį elementą, paieška bus atliekama kairiajame masyve. Dabar paieška sumažinta iki pusės, kaip parodyta žemiau:

Vidurinis elementas kairiajame masyve yra 10, kuris yra lygus ieškomam elementui.

Laiko sudėtingumas

Dvejetainėje paieškoje yra n elementų. Jei vidurinis elementas nėra lygus ieškomam elementui, tada paieškos erdvė sumažinama iki n/2, ir mes toliau mažinsime paieškos erdvę n/2, kol elementą rasime. Visoje redukcijoje, jei pereisime nuo n iki n/2 į n/4 ir t. t., tai užtruks log₂n žingsnių.

Dvejetainio medžio ir dvejetainio paieškos medžio skirtumai