Prieš suprasdami Raudonai juodas medis ir AVL medis skirtumus, turėtume žinoti apie raudonai juodą medį ir AVL medį atskirai.

Kas yra raudonai juodas medis?

Raudonai juodas medis yra savaime subalansuotas dvejetainis paieškos medis kuriame kiekviename mazge yra vienas papildomas informacijos bitas, nurodantis mazgo spalvą. Mazgo spalva gali būti raudona arba juoda, atsižvelgiant į mazgo saugomą bitų informaciją.

java sveikasis skaičius į eilutę

Savybės

Toliau pateikiamos savybės, susijusios su raudonai juodu medžiu:

• Medžio šaknies mazgas turi būti juodas.
• Raudonas mazgas gali turėti tik juodus vaikus. Arba galime pasakyti, kad du gretimi mazgai negali būti raudonos spalvos.
• Jei mazgas neturi kairiojo ar dešiniojo vaiko, tada tas mazgas vadinamas lapo mazgu. Taigi, kairįjį ir dešinįjį vaikus dedame žemiau lapo mazgo, žinomo kaip nulis

Lapo mazgo juodos spalvos gylis arba juodos spalvos aukštis gali būti apibrėžtas kaip juodos spalvos skaičius, su kuriuo susiduriame, kai pereiname iš lapo mazgo į šaknies mazgą. Viena iš pagrindinių raudonai juodo medžio savybių yra ta, kad kiekvienas lapo mazgas turi turėti tokį patį juodos spalvos gylį.

Supraskime šią savybę per pavyzdį.

Aukščiau esančiame medyje yra penki mazgai, iš kurių vienas yra raudonas, o kiti keturi mazgai yra juodi. Aukščiau esančiame medyje yra trys lapų mazgai. Dabar apskaičiuojame kiekvieno lapo mazgo juodą gylį. Kaip galime pastebėti, kad visų trijų lapų mazgų juodasis gylis yra 2; todėl tai raudonai juodas medis.

Jei medis nepaklūsta nė vienai iš pirmiau minėtų trijų savybių, tai nėra raudonai juodas medis.

Raudonai juodo medžio aukštis

Laikykite h kaip medžio, turinčio n mazgų, aukštį. Kokia būtų mažiausia n reikšmė?. N reikšmė yra mažiausia, kai visi mazgai yra juodi. Jei medyje yra visi juodieji mazgai, medis būtų pilnas dvejetainis medis. Jei viso dvejetainio medžio aukštis yra h, tada medžio mazgų skaičius yra:

n = 2h -1

java vs c++

Kokia būtų didžiausia n reikšmė?

N reikšmė yra didžiausia, kai kiekvienas juodas mazgas turi du raudonus vaikus, bet raudonasis mazgas negali turėti raudonų vaikų, todėl jis turės juodus vaikus. Tokiu būdu yra pakaitiniai juodų ir raudonų vaikų sluoksniai. Taigi, jei juodų sluoksnių skaičius yra h, tai raudonųjų sluoksnių skaičius taip pat yra h; todėl bendras medžio aukštis tampa 2h. Bendras mazgų skaičius yra:

n = 2*2h-1

Kas yra AVL medis?

An AVL medis yra savaime balansuojantis dvejetainis paieškos medis, jei stebime toliau pateiktą atvejį, kuris yra dvejetainis paieškos medis ir subalansuotas medis.

Aukščiau pateiktame medyje blogiausias laiko sudėtingumas ieškant elemento yra O(h), t.y. medžio aukštis. Aukščiau pateiktu atveju palyginimų, atliktų ieškant 17 elemento, skaičius yra 4, o medžio aukštis taip pat yra 4.

Jei atsižvelgsime į iškreiptą dvejetainį medį, kaip parodyta žemiau:

javafx ant užtemimo

Aukščiau pateiktame dešiniajame iškreiptame medyje palyginimų, atliktų ieškant 17 elemento, skaičius yra 5, o medyje esančių elementų skaičius taip pat yra 5. Todėl galime sakyti, kad jei medis yra iškreiptas dvejetainis medis, tada laiko sudėtingumas. būtų O(n).

Dabar turime subalansuoti šiuos iškreiptus medžius, kad jų laiko sudėtingumas būtų O(h). Yra terminas, žinomas kaip a balanso faktorius , kuris naudojamas dvejetainės paieškos medžio savaiminiam balansavimui. Balanso koeficientą galima apskaičiuoti taip:

Pusiausvyros koeficiento reikšmė gali būti 1, 0 arba -1. Jei kiekvienas dvejetainio medžio mazgas turi reikšmę 1, 0 arba -1, tada sakoma, kad tas medis yra subalansuotas dvejetainis medis arba AVL medis.

Medis žinomas kaip tobulai subalansuotas medis, jei kiekvieno mazgo balanso koeficientas yra 0. AVL medis yra beveik subalansuotas medis, nes kiekvienas medžio mazgas turi balanso koeficiento reikšmę 1, 0 arba -1.

Raudonai juodo medžio ir AVL medžio skirtumai.

Toliau pateikiami skirtumai tarp raudonai juodo medžio ir AVL medžio:

Dvejetainis paieškos medis

Raudonai juodas medis yra dvejetainis paieškos medis, o AVL medis taip pat yra dvejetainis paieškos medis.

Taisyklės

Raudonai juodam medžiui taikomos šios taisyklės:

kas yra dviguba java

1. Raudonai juodo medžio mazgas yra raudonos arba juodos spalvos.
2. Šaknies mazgo spalva turi būti juoda.
3. Gretimi mazgai neturėtų būti raudoni. Kitaip tariant, galime sakyti, kad raudonasis mazgas negali turėti raudonų vaikų, bet juodas mazgas gali turėti juodų vaikų.
4. Kiekviename kelyje turi būti tiek pat juodų mazgų; tada tik medis gali būti laikomas raudonai juodu medžiu.
5. Išoriniai mazgai yra nuliniai mazgai, kurie visada yra juodos spalvos.

AVL medžio taisyklė:

Kiekvieno mazgo balanso koeficientas turi būti -1, 0 arba 1.

Pavyzdys

Aukščiau pateiktame paveikslėlyje turime patikrinti, ar medis yra raudonai juodas medis, ar ne. Norėdami tai patikrinti, pirmiausia turime patikrinti, ar medis yra dvejetainis paieškos medis, ar ne. Kaip matome aukščiau esančiame paveikslėlyje, jis atitinka visas dvejetainio paieškos medžio savybes; todėl tai yra dvejetainis paieškos medis. Antra, turime patikrinti, ar jis atitinka pirmiau minėtas taisykles, ar ne. Aukščiau pateiktas medis atitinka visas pirmiau minėtas penkias taisykles; todėl daroma išvada, kad aukščiau minėtas medis yra raudonai juodas medis.

Aukščiau pateiktame paveikslėlyje turime patikrinti, ar medis yra AVL medis, ar ne. Kadangi kiekvieno mazgo balanso koeficiento reikšmė yra -1, 0 arba 1, tai yra AVL medis.

Kaip medį galima laikyti subalansuotu medžiu ar ne?

Raudonai juodo medžio atveju, jei tenkinamos visos aukščiau pateiktos taisyklės, su sąlyga, kad medis yra dvejetainis paieškos medis, tada medis laikomas raudonai juodu medžiu.

AVL medžio atveju, jei balanso koeficientas yra -1, 0 arba 1, aukščiau pateiktas medis laikomas AVL medžiu.

Balansavimui naudojami įrankiai

Jei medis nesubalansuotas, medžiui subalansuoti raudonai juodame medyje naudojami du įrankiai:

Perspalvinimas Rotacija

Jei medis nesubalansuotas, medžio balansavimui AVL medyje naudojamas vienas įrankis:

ketvirtį versle

Rotacija

Kuriai operacijai efektyvu

Raudonai juodo medžio atveju įterpimo ir ištrynimo operacijos yra veiksmingos. Jei pakeitus spalvą medis subalansuojamas, įterpimo ir ištrynimo operacijos raudonai juodame medyje yra veiksmingos.

AVL medžio atveju paieškos operacija yra efektyvi, nes norint subalansuoti medį reikia tik vieno įrankio.

Laiko sudėtingumas

Raudonojo-juodo medžio atveju visų operacijų, ty įterpimo, trynimo ir paieškos, sudėtingumo laikas yra O(logn).

AVL medžio atveju visų operacijų, ty įterpimo, trynimo ir paieškos, sudėtingumas yra O (logn).

Supraskime lentelės formos skirtumus.