Pirms saprast Sarkanmelnais koks un AVL koks atšķirības, mums būtu jāzina par sarkanmelno koku un AVL koku atsevišķi.

Kas ir sarkanmelns koks?

Sarkanmelnais koks ir līdzsvarots binārā meklēšanas koks kurā katrs mezgls satur vienu papildu informācijas bitu, kas apzīmē mezgla krāsu. Mezgla krāsa var būt sarkana vai melna atkarībā no mezglā saglabātās bitu informācijas.

Īpašības

Tālāk ir norādītas īpašības, kas saistītas ar sarkanmelno koku:

• Koka saknes mezglam jābūt melnam.
• Sarkanajam mezglam var būt tikai melni bērni. Vai arī mēs varam teikt, ka divi blakus esošie mezgli nevar būt sarkanā krāsā.
• Ja mezglam nav kreisā vai labā bērna, tad tiek uzskatīts, ka šis mezgls ir lapas mezgls. Tātad, mēs ievietojam kreiso un labo bērnu zem lapas mezgla, kas pazīstams kā nulle

Lapas mezgla melno dziļumu vai melno augstumu var definēt kā melno krāsu skaitu, ar kuru mēs sastopamies, pārejot no lapas mezgla uz saknes mezglu. Viena no galvenajām sarkanmelnā koka īpašībām ir tāda, ka katram lapas mezglam jābūt vienādam melnajam dziļumam.

Izpratīsim šo īpašumu, izmantojot piemēru.

Iepriekš minētajā kokā ir pieci mezgli, no kuriem viens ir sarkans, bet pārējie četri mezgli ir melni. Iepriekš minētajā kokā ir trīs lapu mezgli. Tagad mēs aprēķinām katra lapas mezgla melno dziļumu. Kā mēs varam novērot, ka visu trīs lapu mezglu melnais dziļums ir 2; tāpēc tas ir sarkanmelns koks.

Ja koks nepakļaujas nevienai no trim iepriekšminētajām īpašībām, tad tas nav sarkanmelns koks.

Sarkanmelna koka augstums

Apsveriet h kā koka augstumu ar n mezgliem. Kāda būtu mazākā n vērtība?. N vērtība ir mazākā, ja visi mezgli ir melni. Ja koks satur visus melnos mezglus, tad koks būtu pilnīgs binārs koks. Ja pilna binārā koka augstums ir h, tad mezglu skaits kokā ir:

n = 2h -1

Kāda būtu n lielākā vērtība?

n vērtība ir vislielākā, ja katram melnajam mezglam ir divi sarkani bērni, bet sarkanajam mezglam nevar būt sarkani bērni, tāpēc tam būs melni bērni. Tādā veidā ir alternatīvi melnu un sarkanu bērnu slāņi. Tātad, ja melno slāņu skaits ir h, tad arī sarkano slāņu skaits ir h; līdz ar to koka kopējais augstums kļūst 2h. Kopējais mezglu skaits ir:

n = 2*2h-1

Kas ir AVL koks?

An AVL koks ir pašbalansējošs binārais meklēšanas koks, ja mēs novērojam tālāk norādīto gadījumu, kas ir binārais meklēšanas koks un līdzsvarots koks.

Iepriekš minētajā kokā vissliktākā laika sarežģītība elementa meklēšanai ir O(h), t.i., koka augstums. Iepriekš minētajā gadījumā salīdzinājumu skaits, kas veikts, lai meklētu 17 elementu, ir 4, un koka augstums arī ir 4.

Ja ņemam vērā šķību bināro koku, kā parādīts zemāk:

Iepriekš redzamajā labajā šķībajā kokā salīdzinājumu skaits, kas veikts, lai meklētu 17 elementu, ir 5, un kokā esošo elementu skaits arī ir 5. Tāpēc mēs varam teikt, ka, ja koks ir šķībs binārs koks, tad laika sarežģītība. būtu O(n).

Tagad mums ir jāsabalansē šie šķībie koki, lai tiem būtu laika sarežģītība O(h). Ir termins, kas pazīstams kā a līdzsvara faktors , ko izmanto, lai līdzsvarotu bināro meklēšanas koku. Līdzsvara koeficientu var aprēķināt šādi:

Līdzsvara koeficienta vērtība var būt 1, 0 vai -1. Ja katram binārā koka mezglam ir vērtība 1, 0 vai -1, tad tiek uzskatīts, ka šis koks ir līdzsvarots. binārais koks vai AVL koks.

Koks ir pazīstams kā perfekti līdzsvarots koks, ja katra mezgla līdzsvara koeficients ir 0. AVL koks ir gandrīz līdzsvarots koks, jo katram koka mezglam līdzsvara koeficienta vērtība ir 1, 0 vai -1.

Atšķirības starp sarkanmelno koku un AVL koku.

Tālāk ir norādītas atšķirības starp sarkanmelno koku un AVL koku:

Binārais meklēšanas koks

Sarkanais-melnais koks ir binārs meklēšanas koks, un AVL koks ir arī binārs meklēšanas koks.

Noteikumi

Sarkanmelnajā kokā tiek piemēroti šādi noteikumi:

1. Sarkanmelnā koka mezgls ir sarkanā vai melnā krāsā.
2. Saknes mezgla krāsai jābūt melnai.
3. Blakus esošie mezgli nedrīkst būt sarkani. Citiem vārdiem sakot, mēs varam teikt, ka sarkanajam mezglam nevar būt sarkani bērni, bet melnajam mezglam var būt melni bērni.
4. Katrā ceļā jābūt vienādam melno mezglu skaitam; tad tikai koku var uzskatīt par sarkanmelnu koku.
5. Ārējie mezgli ir nulles mezgli, kas vienmēr ir melnā krāsā.

AVL koka noteikums:

Katra mezgla līdzsvara koeficientam jābūt -1, 0 vai 1.

Piemērs

Iepriekš redzamajā attēlā mums ir jāpārbauda, ​​vai koks ir sarkanmelns koks. Lai to pārbaudītu, vispirms mums ir jāpārbauda, ​​vai koks ir binārs meklēšanas koks. Iepriekš redzamajā attēlā redzams, ka tas atbilst visām binārā meklēšanas koka īpašībām; tāpēc tas ir binārs meklēšanas koks. Otrkārt, mums ir jāpārbauda, ​​vai tas atbilst iepriekš minētajiem noteikumiem vai nē. Iepriekš minētais koks atbilst visiem iepriekšminētajiem pieciem noteikumiem; tāpēc tiek secināts, ka iepriekš minētais koks ir sarkanmelns koks.

Iepriekš redzamajā attēlā mums ir jāpārbauda, ​​vai koks ir AVL koks. Tā kā katram mezglam līdzsvara koeficienta vērtība ir -1, 0 vai 1, tas ir AVL koks.

Kā koku var uzskatīt par līdzsvarotu koku vai nē?

Sarkanmelna koka gadījumā, ja ir izpildīti visi iepriekš minētie noteikumi, ar nosacījumu, ka koks ir binārs meklēšanas koks, tad tiek uzskatīts, ka koks ir sarkanmelns koks.

AVL koka gadījumā, ja līdzsvara koeficients ir -1, 0 vai 1, tad tiek uzskatīts, ka iepriekš minētais koks ir AVL koks.

Līdzsvarošanai izmantotie instrumenti

Ja koks nav līdzsvarots, tad koka līdzsvarošanai sarkanmelnā kokā tiek izmantoti divi instrumenti:

Pārkrāsošana Rotācija

Ja koks nav līdzsvarots, tad koka balansēšanai AVL kokā izmanto vienu instrumentu:

Rotācija

Kurai darbībai efektīvs

Sarkanmelnā koka gadījumā ievietošanas un dzēšanas darbības ir efektīvas. Ja koks tiek līdzsvarots, mainot krāsu, ievietošanas un dzēšanas darbības ir efektīvas sarkanmelnajā kokā.

AVL koka gadījumā meklēšanas darbība ir efektīva, jo koka līdzsvarošanai ir nepieciešams tikai viens rīks.

xd xd nozīme

Laika sarežģītība

Sarkanā un melnā koka gadījumā visu operāciju, t.i., ievietošanas, dzēšanas un meklēšanas, laika sarežģītība ir O(logn).

AVL koka gadījumā visu operāciju, t.i., ievietošanas, dzēšanas un meklēšanas, laika sarežģītība ir O(logn).

Sapratīsim atšķirības tabulas formā.