TechCodeview

Før du forstår Rød-sort træ og AVL træ forskelle, bør vi kende til det rød-sort træ og AVL træet separat.

Hvad er et rød-sort træ?

Det rød-sorte træ er et selvbalanceret binært søgetræ hvor hver node indeholder en ekstra bit information, der angiver farven på noden. Farven på noden kan være enten rød eller sort, afhængigt af bitinformationen gemt af noden.

java design mønster

Ejendomme

Følgende er egenskaberne forbundet med et rød-sort træ:

• Træets rodknude skal være sort.
• En rød knude kan kun have sorte børn. Eller vi kan sige, at to tilstødende noder ikke kan være røde.
• Hvis knudepunktet ikke har et venstre eller højre barn, siges den knude at være en bladknude. Så vi sætter venstre og højre børn under bladknuden kendt som nul

Den sorte dybde eller sorte højde af en bladknude kan defineres som antallet af sorte, som vi støder på, når vi bevæger os fra bladknuden til rodknuden. En af de vigtigste egenskaber ved det rød-sort træ er, at hver bladknude skal have den samme sorte dybde.

Lad os forstå denne egenskab gennem et eksempel.

I ovenstående træ er der fem noder, hvor den ene er en rød og de andre fire noder er sorte. Der er tre bladknuder i ovenstående træ. Nu beregner vi den sorte dybde af hver bladknude. Som vi kan observere, at den sorte dybde af alle de tre bladknuder er 2; derfor er det et rød-sort træ.

Hvis træet ikke adlyder nogen af ​​ovenstående tre egenskaber, er det ikke et rød-sort træ.

Højden på et rød-sort træ

Betragt h som højden af ​​træet med n noder. Hvad ville være den mindste værdi af n?. Værdien af ​​n er den mindste, når alle noderne er sorte. Hvis træet indeholder alle de sorte noder, så ville træet være et komplet binært træ. Hvis højden af ​​et komplet binært træ er h, så er antallet af noder i et træ:

n = 2h-1

Hvad ville være den største værdi af n?

js sæt

Værdien af ​​n er størst, når hver sort node har to røde børn, men den røde node kan ikke have røde børn, så den får sorte børn. På denne måde er der skiftevis lag af sorte og røde børn. Så hvis antallet af sorte lag er h, så er antallet af røde lag også h; derfor bliver træets samlede højde 2t. Det samlede antal noder er:

n = 2*2h-1

Hvad er AVL-træet?

An AVL træ er et selvbalancerende binært søgetræ, hvis vi observerer nedenstående tilfælde, som er et binært søgetræ og et balanceret træ.

I ovenstående træ er den værste tidskompleksitet for at søge et element O(h), dvs. træets højde. I ovenstående tilfælde er antallet af sammenligninger foretaget for at søge 17 element 4, og træets højde er også 4.

Hvis vi betragter det skæve binære træ, som vist nedenfor:

I ovenstående skæve træ til højre er antallet af sammenligninger foretaget for at søge 17 element 5, og antallet af elementer til stede i træet er også 5. Derfor kan vi sige, at hvis træet er et skævt binært træ, så er tidskompleksiteten ville være O(n).

Nu skal vi balancere disse skæve træer, så de får tidskompleksiteten O(h). Der er et udtryk kendt som a balancefaktor , som bruges til at selvbalancere det binære søgetræ. Balancefaktoren kan beregnes som:

Værdien af ​​balancefaktoren kan være enten 1, 0 eller -1. Hvis hver node i det binære træ har en værdi på enten 1, 0 eller -1, siges det at træet er et balanceret binært træ eller AVL-træ.

Træet er kendt som et perfekt balanceret træ, hvis balancefaktoren for hver knude er 0. AVL-træet er et næsten balanceret træ, fordi hver knude i træet har værdien af ​​balancefaktor enten 1, 0 eller -1.

Forskelle mellem det rød-sort træ og AVL træet.

Følgende er forskellene mellem det rød-sort træ og AVL træet:

Binært søgetræ

Det rød-sorte træ er et binært søgetræ, og AVL-træet er også et binært søgetræ.

Regler

Følgende regler anvendes i et rød-sort træ:

1. Noden i et rød-sort træ er enten rød eller sort i farven.
2. Farven på rodnoden skal være sort.
3. De tilstødende noder bør ikke være røde. Med andre ord kan vi sige, at den røde knude ikke kan have røde børn, men den sorte knude kan have sorte børn.
4. Der bør være det samme antal sorte noder i hver sti; så kan kun et træ betragtes som et rød-sort træ.
5. De ydre knuder er nulknuderne, som altid er sorte i farven.

Regel for AVL-træet:

Hver knude skal have balancefaktoren enten som -1, 0 eller 1.

parseint java

Eksempel

I ovenstående figur skal vi kontrollere, om træet er et rød-sort træ eller ej. For at kontrollere dette skal vi først kontrollere, om træet er et binært søgetræ eller ej. Som vi kan observere i ovenstående figur, opfylder den alle egenskaberne for det binære søgetræ; derfor er det et binært søgetræ. For det andet skal vi kontrollere, om det opfylder ovennævnte regler eller ej. Ovenstående træ opfylder alle ovenstående fem regler; derfor konkluderer den, at ovenstående træ er et rød-sort træ.

I ovenstående figur skal vi tjekke, om træet er et AVL-træ eller ej. Da hver node har en balancefaktorværdi enten som -1, 0 eller 1, så er det et AVL-træ.

Hvordan kan træet betragtes som et balanceret træ eller ej?

I tilfælde af et rød-sort træ, hvis alle ovenstående regler er opfyldt, forudsat at et træ er et binært søgetræ, så siges træet at være et rød-sort træ.

I tilfælde af AVL-træet, hvis balancefaktoren er -1, 0 eller 1, så siges ovenstående træ at være et AVL-træ.

Redskaber brugt til balancering

Hvis træet ikke er afbalanceret, bruges to værktøjer til at balancere træet i et rød-sort træ:

Omfarvning Rotation

Hvis træet ikke er afbalanceret, bruges ét værktøj til at balancere træet i AVL-træet:

konverter nfa til dfa

Rotation

Effektiv til hvilken operation

I tilfældet med det rød-sort træ er indsættelses- og sletningsoperationerne effektive. Hvis træet bliver afbalanceret gennem omfarvningen, er indsættelses- og sletningsoperationer effektive i det rød-sort træ.

I tilfældet med AVL-træet er søgeoperationen effektiv, da den kun kræver ét værktøj til at balancere træet.

Tidskompleksitet

I tilfældet med rød-sort træ er tidskompleksiteten for alle operationerne, dvs. indsættelse, sletning og søgning O(logn).

I tilfælde af AVL-træ er tidskompleksiteten for alle operationerne, dvs. indsættelse, sletning og søgning O(logn).

Lad os forstå forskellene i tabelformen.