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 yra
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:
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 = 2m+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 log2n žingsnių.
Dvejetainio medžio ir dvejetainio paieškos medžio skirtumai
| Palyginimo pagrindas | Dvejetainis medis | Dvejetainis paieškos medis |
|---|---|---|
| Apibrėžimas | Dvejetainis medis yra nelinijinė duomenų struktūra, kurioje mazgas gali turėti daugiausiai du vaikus, t. y. mazgas gali turėti 0, 1 arba daugiausiai du vaikus. Dvejetainis paieškos medis yra sutvarkytas dvejetainis medis, kuriame vadovaujamasi tam tikra tvarka organizuojant mazgus medyje. | |
| Struktūra | Dvejetainio medžio struktūra yra tokia, kad pirmasis mazgas arba aukščiausias mazgas yra žinomas kaip šakninis mazgas. Kiekviename dvejetainio medžio mazge yra kairysis ir dešinysis žymeklis. Kairiajame žymeklyje yra kairiojo pomedžio adresas, o dešinėje – dešiniojo pomedžio adresas. | Dvejetainis paieškos medis yra vienas iš dvejetainio medžio tipų, kurio visų kairiojo pomedžio mazgų vertė yra mažesnė arba lygi šakniniam mazgui, o visų dešiniojo pomedžio mazgų vertė yra didesnė arba lygi šakninio mazgo vertė. |
| Operacijos | Veiksmai, kuriuos galima įgyvendinti dvejetainiame medyje, yra įterpimas, trynimas ir perėjimas. | Dvejetainiai paieškos medžiai yra surūšiuoti dvejetainiai medžiai, kurie leidžia greitai įterpti, ištrinti ir ieškoti. Peržvalgos dažniausiai įgyvendina dvejetainę paiešką, nes visi raktai yra išdėstyti rūšiuota tvarka. |
| tipai | Keturių tipų dvejetainiai medžiai yra pilnas dvejetainis medis, pilnas dvejetainis medis, tobulas dvejetainis medis ir išplėstinis dvejetainis medis. | Yra įvairių tipų dvejetainių paieškos medžių, tokių kaip AVL medžiai, Splay medis, Tango medžiai ir kt. |