Prieš sužinodami apie dvejetainio paieškos medžio ir AVL medžio skirtumus, turėtume žinoti apie dvejetainės paieškos medį ir AVL medį atskirai.

Kas yra dvejetainis paieškos medis?

The dvejetainis paieškos medis yra medis dvejetainis medis. Kaip žinome, tas medis gali turėti „n“ vaikų skaičių, tuo tarpu; dvejetainiame medyje gali būti daugiausiai du vaikai. Taigi, po dvejetainio medžio apribojimo taip pat seka dvejetainis paieškos medis. Kiekvienas dvejetainio paieškos medžio mazgas turi turėti daugiausiai du antrinius elementus; kitaip tariant, galime sakyti, kad dvejetainis paieškos medis yra dvejetainio medžio variantas.

Dvejetainės paieškos medis taip pat seka dvejetainės paieškos savybes. Dvejetainėje paieškoje visi masyvo elementai turi būti surūšiuoti. Dvejetainėje paieškoje apskaičiuojame vidurinį elementą, kurio kairiojoje vidurinio elemento dalyje yra mažesnė už vidurinę reikšmę, o dešiniojoje vidurinio elemento dalyje yra didesnės už vidurinę reikšmę.

Dvejetainėje paieškos medyje vidurinis elementas tampa šaknies mazgu, dešinioji dalis – dešiniuoju pomedžiu, o kairioji – kairiuoju pomedžiu. Todėl galime sakyti, kad dvejetainis paieškos medis yra a derinys dvejetainis medis ir dvejetainė paieška .

Pastaba: dvejetainis paieškos medis gali būti apibrėžtas kaip dvejetainis medis, kuriame visi kairiojo pomedžio elementai yra mažesni už šakninį mazgą, o visi dešiniojo pomedžio elementai yra didesni už šakninį mazgą.

Laiko sudėtingumas dvejetainėje paieškos medyje

Jei dvejetainis paieškos medis yra beveik subalansuotas medis, visos operacijos turės laiko sudėtingumą O (prisijungti) nes paieška skirstoma į kairę arba į dešinę pomedį.

galiojantys java identifikatoriai

Jei dvejetainis paieškos medis yra pakreiptas į kairę arba į dešinę, tada visos operacijos turės laiko sudėtingumą O(n) nes turime pereiti iki n elementų.

Kas yra AVL medis?

An AVL medis yra savaime balansuojantis dvejetainis paieškos medis, kuriame kairiojo ir dešiniojo pomedžio aukščių skirtumas negali būti didesnis nei vienas. Šis skirtumas žinomas kaip balanso veiksnys. AVL medyje balanso koeficiento reikšmės gali būti -1, 0 arba 1.

Kaip vyksta dvejetainio paieškos medžio savibalansas?

Kaip žinome, AVL medis yra savaime balansuojantis dvejetainis paieškos medis. Jei dvejetainis paieškos medis nėra subalansuotas, jį galima subalansuoti savaime su tam tikrais pertvarkymais. Šiuos pertvarkymus galima atlikti naudojant kai kuriuos pasukimus.

Supraskime savęs balansavimą per pavyzdį.

Tarkime, kad norime įterpti 10, 20, 30 AVL medyje.

Toliau pateikiami 10, 20, 30 įterpimo į AVL medį būdai:

Jei įterpimo tvarka yra 30, 20, 10.

1 žingsnis: Pirmiausia sukuriame dvejetainį paieškos medį, kaip parodyta toliau:

Java vietinė data

2 žingsnis: Aukščiau esančiame paveikslėlyje matome, kad medis yra nesubalansuotas, nes mazgo 30 balanso koeficientas yra 2. Kad jį paverstume AVL medžiu, turime atlikti kai kuriuos pasukimus. Jei atliksime teisingą 20 mazgo pasukimą, mazgas 30 judės žemyn, o mazgas 20 judės aukštyn, kaip parodyta toliau:

Kaip matome, galutinis medis seka dvejetainės paieškos medžio savybę ir subalansuotą medį; todėl tai AVL medis.

Tuo atveju medis buvo liko nesubalansuotas medis, todėl atliekame tinkamą mazgo sukimąsi.

Jei įterpimo tvarka yra 10, 20, 30.

1 žingsnis: Pirmiausia sukuriame dvejetainį paieškos medį, kaip parodyta žemiau:

2 žingsnis: Aukščiau pateiktame paveikslėlyje galime pastebėti, kad medis yra nesubalansuotas, nes 10 mazgo balanso koeficientas yra -2. Kad jį paverstume AVL medžiu, turime atlikti kai kuriuos pasukimus. Tai dešinysis nesubalansuotas medis, todėl atliksime sukimąsi į kairę. Jei atliksime 20 mazgo sukimąsi į kairę, 20 mazgas judės aukštyn, o 10 – žemyn, kaip parodyta toliau:

Kaip matome, galutinis medis seka savybę Dvejetainės paieškos medis ir a subalansuotas medis ; todėl tai AVL medis.

kaip nustatyti monitoriaus dydį

Jei įterpimo tvarka yra 30, 10, 20

1 žingsnis: Pirmiausia sukuriame dvejetainės paieškos medį, kaip parodyta žemiau:

2 žingsnis: Aukščiau esančiame paveikslėlyje galime pastebėti, kad medis yra nesubalansuotas, nes šaknies mazgo balanso koeficientas yra 2. Norėdami jį paversti AVL medžiu, turime atlikti kai kuriuos pasukimus. Aukščiau pateiktas scenarijus yra nesubalansuotas kairėje ir dešinėje, nes vienas mazgas yra pagrindinio mazgo kairėje, o kitas - dešinėje pagrindinio mazgo pusėje. Pirmiausia atliksime sukimąsi į kairę, o sukimas vyksta tarp 10 ir 20 mazgų. Po sukimo į kairę 20 judės aukštyn, o 10 – žemyn, kaip parodyta žemiau:

Visgi medis yra nesubalansuotas, todėl ant medžio atliekame tinkamą sukimąsi. Atlikus tinkamą medžio pasukimą, medis norėtų, kaip parodyta žemiau:

Kaip galime pastebėti aukščiau esančiame medyje, medis seka dvejetainės paieškos medžio savybę ir subalansuotą medį; todėl tai AVL medis.

Jei įterpimo tvarka yra 10, 30, 20

1 žingsnis: Pirmiausia sukuriame dvejetainės paieškos medį, kaip parodyta toliau:

2 žingsnis: Aukščiau esančiame paveikslėlyje galime pastebėti, kad medis yra nesubalansuotas, nes šaknies mazgo balanso koeficientas yra 2. Norėdami jį paversti AVL medžiu, turime atlikti kai kuriuos pasukimus. Aukščiau pateiktas scenarijus yra nesubalansuotas dešinėje ir kairėje, nes vienas mazgas yra dešinėje nuo pirminio mazgo, o kitas mazgas yra kairėje nuo pirminio mazgo. Pirmiausia atliksime teisingą sukimąsi tarp 30 ir 20 mazgų. Pasukus į dešinę, 20 judės aukštyn, o 30 – žemyn, kaip parodyta toliau:

Vis dėlto aukščiau pateiktas medis yra nesubalansuotas, todėl turime atlikti mazgo sukimąsi į kairę. Atlikus sukimąsi į kairę, mazgas 20 judės aukštyn, o mazgas 10 – žemyn, kaip parodyta toliau:

Kaip galime pastebėti aukščiau esančiame medyje, medis seka dvejetainės paieškos medžio savybę ir subalansuotą medį; todėl tai AVL medis.

Dvejetainės paieškos medžio ir AVL medžio skirtumai