TechCodeview

Innan du förstår Röd-svart träd och AVL-träd skillnader bör vi känna till det röd-svarta trädet och AVL-trädet separat.

Vad är ett röd-svart träd?

Det rödsvarta trädet är ett självbalanserat binärt sökträd där varje nod innehåller en extra bit information som anger färgen på noden. Färgen på noden kan vara antingen röd eller svart, beroende på den bitinformation som lagras av noden.

Egenskaper

struktur i datastruktur

Följande egenskaper är associerade med ett röd-svart träd:

• Trädets rotnod ska vara svart.
• En röd nod kan bara ha svarta barn. Eller så kan vi säga att två intilliggande noder inte kan vara röda.
• Om noden inte har ett vänster eller höger barn, sägs den noden vara en lövnod. Så vi placerar vänster och höger barn under lövnoden som kallas noll

Det svarta djupet eller svarta höjden för en lövnod kan definieras som antalet svarta som vi möter när vi flyttar från lövnoden till rotnoden. En av nyckelegenskaperna hos det röd-svarta trädet är att varje lövnod ska ha samma svarta djup.

Låt oss förstå denna egenskap genom ett exempel.

I ovanstående träd finns det fem noder, där en är en röd och de andra fyra noderna är svarta. Det finns tre lövnoder i ovanstående träd. Nu beräknar vi det svarta djupet för varje lövnod. Som vi kan observera att det svarta djupet för alla tre bladnoderna är 2; därför är det ett röd-svart träd.

Om trädet inte följer någon av ovanstående tre egenskaper är det inte ett röd-svart träd.

Höjd på ett röd-svart träd

Betrakta h som höjden på trädet som har n noder. Vilket skulle vara det minsta värdet på n?. Värdet på n är det minsta när alla noder är svarta. Om trädet innehåller alla svarta noder, skulle trädet vara ett komplett binärt träd. Om höjden på ett komplett binärt träd är h, då är antalet noder i ett träd:

n = 2h-1

Vilket skulle vara det största värdet på n?

Värdet på n är störst när varje svart nod har två röda barn, men den röda noden kan inte ha röda barn, så att den kommer att ha svarta barn. På så sätt finns det omväxlande lager av svarta och röda barn. Så, om antalet svarta lager är h, så är antalet röda lager också h; därför blir trädets totala höjd 2h. Det totala antalet noder är:

n = 2*2h-1

java sömn

Vad är AVL-trädet?

En AVL-träd är ett självbalanserande binärt sökträd om vi observerar fallet nedan, som är ett binärt sökträd och ett balanserat träd.

I ovanstående träd är den värsta tidskomplexiteten för att söka efter ett element O(h), det vill säga trädets höjd. I ovanstående fall är antalet jämförelser som gjorts för att söka 17 element 4, och höjden på trädet är också 4.

Om vi ​​betraktar det sneda binära trädet, som visas nedan:

I det sneda trädet ovan till höger är antalet jämförelser som görs för att söka 17 element 5, och antalet element som finns i trädet är också 5. Därför kan vi säga att om trädet är ett skevt binärt träd så är tidskomplexiteten skulle vara O(n).

Nu måste vi balansera dessa sneda träd så att de får tidskomplexiteten O(h). Det finns en term som kallas a balansfaktor , som används för att självbalansera det binära sökträdet. Balansfaktorn kan beräknas som:

vad är ymail

Värdet på balansfaktorn kan vara antingen 1, 0 eller -1. Om varje nod i det binära trädet har ett värde på antingen 1, 0 eller -1, sägs det trädet vara ett balanserat binärt träd eller AVL-träd.

Trädet är känt som ett perfekt balanserat träd om balansfaktorn för varje nod är 0. AVL-trädet är ett nästan balanserat träd eftersom varje nod i trädet har värdet på balansfaktorn antingen 1, 0 eller -1.

Skillnader mellan det röd-svarta trädet och AVL-trädet.

Följande är skillnaderna mellan det röd-svarta trädet och AVL-trädet:

Binärt sökträd

Det röd-svarta trädet är ett binärt sökträd, och AVL-trädet är också ett binärt sökträd.

Regler

Följande regler tillämpas i ett röd-svart träd:

1. Noden i ett röd-svart träd är antingen röd eller svart till färgen.
2. Färgen på rotnoden ska vara svart.
3. De intilliggande noderna ska inte vara röda. Med andra ord kan vi säga att den röda noden inte kan ha röda barn, men den svarta noden kan ha svarta barn.
4. Det bör finnas samma antal svarta noder i varje väg; då kan bara ett träd betraktas som ett röd-svart träd.
5. De externa noderna är nollnoderna, som alltid är svarta till färgen.

Regel för AVL-trädet:

Varje nod bör ha balansfaktorn antingen som -1, 0 eller 1.

Exempel

I figuren ovan måste vi kontrollera om trädet är ett röd-svart träd eller inte. För att kontrollera detta måste vi först kontrollera om trädet är ett binärt sökträd eller inte. Som vi kan observera i figuren ovan att den uppfyller alla egenskaperna hos det binära sökträdet; därför är det ett binärt sökträd. För det andra måste vi kontrollera om den uppfyller ovan nämnda regler eller inte. Ovanstående träd uppfyller alla ovanstående fem regler; därför drar den slutsatsen att ovanstående träd är ett röd-svart träd.

skillnad mellan två strängar python

I figuren ovan måste vi kontrollera om trädet är ett AVL-träd eller inte. Eftersom varje nod har ett balansfaktorvärde antingen som -1, 0 eller 1, så är det ett AVL-träd.

Hur kan trädet betraktas som ett balanserat träd eller inte?

När det gäller ett röd-svart träd, om alla ovanstående regler är uppfyllda, förutsatt att ett träd är ett binärt sökträd, sägs trädet vara ett röd-svart träd.

När det gäller AVL-trädet, om balansfaktorn är -1, 0 eller 1, sägs ovanstående träd vara ett AVL-träd.

Verktyg som används för att balansera

Om trädet inte är balanserat, används två verktyg för att balansera trädet i ett röd-svart träd:

Omfärgning Rotation

Om trädet inte är balanserat, används ett verktyg för att balansera trädet i AVL-trädet:

slumptalsgenerator i c

Rotation

Effektivt för vilken operation

När det gäller det röd-svarta trädet är insättnings- och raderingsoperationerna effektiva. Om trädet blir balanserat genom omfärgningen, är insättnings- och raderingsoperationer effektiva i det röd-svarta trädet.

När det gäller AVL-trädet är sökningen effektiv eftersom den bara kräver ett verktyg för att balansera trädet.

Tidskomplexitet

I fallet med röd-svart träd är tidskomplexiteten för alla operationer, d.v.s. infogning, radering och sökning O(logn).

I fallet med AVL-träd är tidskomplexiteten för alla operationer, dvs infogning, radering och sökning O(logn).

Låt oss förstå skillnaderna i tabellformen.