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:
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.
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į
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.
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
| Dvejetainės paieškos medis | AVL medis |
|---|---|
| Kiekvienas dvejetainis paieškos medis yra dvejetainis medis, nes abiejuose medžiuose yra didžiausi du vaikai. | Kiekvienas AVL medis taip pat yra dvejetainis, nes AVL medis taip pat turi daugiausiai du vaikus. |
| BST nėra termino, pvz., balanso faktoriaus. | AVL medyje kiekviename mazge yra balanso koeficientas, o balanso koeficiento reikšmė turi būti -1, 0 arba 1. |
| Kiekvienas dvejetainės paieškos medis nėra AVL medis, nes BST gali būti subalansuotas arba nesubalansuotas medis. | Kiekvienas AVL medis yra dvejetainis paieškos medis, nes AVL medis seka BST savybę. |
| Kiekvienas dvejetainės paieškos medžio mazgas susideda iš trijų laukų, ty kairiojo pomedžio, mazgo reikšmės ir dešiniojo pomedžio. | Kiekvienas AVL medžio mazgas susideda iš keturių laukų, ty kairiojo pomedžio, mazgo vertės, dešiniojo pomedžio ir balanso koeficiento. |
| Dvejetainės paieškos medžio atveju, jei norime į medį įterpti bet kurį mazgą, lyginame mazgo reikšmę su šaknies reikšme; jei mazgo reikšmė yra didesnė už šakninio mazgo reikšmę, mazgas įterpiamas į dešinįjį pomedį, priešingu atveju mazgas įterpiamas į kairįjį pomedį. Įdėjus mazgą, nereikia tikrinti aukščio balanso koeficiento, kad įterpimas būtų baigtas. | AVL medžio atveju pirmiausia rasime tinkamą vietą mazgui įterpti. Kai mazgas bus įdėtas, apskaičiuosime kiekvieno mazgo balanso koeficientą. Jei kiekvieno mazgo balanso koeficientas yra patenkintas, įterpimas baigtas. Jei balanso koeficientas yra didesnis nei 1, turime atlikti kai kuriuos pasukimus, kad subalansuotume medį. |
| Dvejetainės paieškos medyje medžio aukštis arba gylis yra O(n), kur n yra mazgų skaičius dvejetainės paieškos medyje. | AVL medyje medžio aukštis arba gylis yra O (logn). |
| Tai paprasta įgyvendinti, nes turime vadovautis dvejetainės paieškos ypatybėmis, kad įterptume mazgą. | Tai sudėtinga įgyvendinti, nes AVL medyje pirmiausia turime sukurti AVL medį, o tada turime patikrinti aukščio balansą. Jei aukštis yra nesubalansuotas, turime atlikti keletą pasukimų, kad subalansuotume medį. |
| BST nėra subalansuotas medis, nes jis neatitinka balanso faktoriaus koncepcijos. | AVL medis yra aukščio subalansuotas medis, nes jis atitinka pusiausvyros koeficiento koncepciją. |
| BST paieška yra neefektyvi, kai medyje yra daug mazgų, nes aukštis nesubalansuotas. | Paieška AVL medyje yra efektyvi net tada, kai medyje yra daug mazgų, nes aukštis yra subalansuotas. |