Før du forstår Rød-svart tre og AVL-tre forskjeller, bør vi vite om det rød-svarte treet og AVL-treet separat.

Hva er et rød-svart tre?

Det rød-svarte treet er et selvbalansert binært søketre der hver node inneholder en ekstra bit informasjon som angir fargen på noden. Fargen på noden kan være enten rød eller svart, avhengig av bitinformasjonen som er lagret av noden.

java design mønster

Egenskaper

Følgende er egenskapene knyttet til et rød-svart tre:

• Rotnoden til treet skal være svart.
• En rød node kan bare ha svarte barn. Eller vi kan si at to tilstøtende noder ikke kan være røde.
• Hvis noden ikke har et venstre eller høyre barn, sies den noden å være en bladnode. Så vi legger venstre og høyre barn under bladnoden kjent som null

Den svarte dybden eller svarte høyden til en bladknute kan defineres som antallet svarte som vi møter når vi beveger oss fra bladnoden til rotnoden. En av nøkkelegenskapene til det rød-svarte treet er at hver bladnode skal ha samme sorte dybde.

La oss forstå denne egenskapen gjennom et eksempel.

I treet ovenfor er det fem noder, der en er rød og de andre fire nodene er svarte. Det er tre bladnoder i treet ovenfor. Nå beregner vi den svarte dybden til hver bladnode. Som vi kan observere at den svarte dybden til alle de tre bladnodene er 2; derfor er det et rød-svart tre.

Hvis treet ikke adlyder noen av de tre egenskapene ovenfor, er det ikke et rød-svart tre.

Høyden på et rød-svart tre

Betrakt h som høyden på treet som har n noder. Hva vil være den minste verdien av n?. Verdien av n er den minste når alle nodene er svarte. Hvis treet inneholder alle de svarte nodene, vil treet være et komplett binært tre. Hvis høyden på et komplett binært tre er h, er antallet noder i et tre:

n = 2t-1

Hva vil være den største verdien av n?

ytelsestesting

Verdien av n er størst når hver svart node har to røde barn, men den røde noden kan ikke ha røde barn, slik at den vil ha svarte barn. På denne måten er det vekselvis lag med svarte og røde barn. Så hvis antallet svarte lag er h, så er antallet røde lag også h; derfor blir treets totale høyde 2t. Det totale antallet noder er:

n = 2*2h-1

Hva er AVL-treet?

An AVL-tre er et selvbalanserende binært søketre hvis vi observerer tilfellet nedenfor, som er et binært søketre og et balansert tre.

I treet ovenfor er den verste tidskompleksiteten for å søke etter et element O(h), dvs. høyden på treet. I tilfellet ovenfor er antallet sammenligninger gjort for å søke 17 element 4, og høyden på treet er også 4.

Hvis vi vurderer det skjeve binære treet, som vist nedenfor:

I det skjeve treet ovenfor til høyre er antall sammenligninger gjort for å søke 17 element 5, og antall elementer som er tilstede i treet er også 5. Derfor kan vi si at hvis treet er et skjevt binært tre så er tidskompleksiteten ville være O(n).

Nå må vi balansere disse skjeve trærne slik at de får tidskompleksiteten O(h). Det er et begrep kjent som en balansefaktor , som brukes til å selvbalansere det binære søketreet. Balansefaktoren kan beregnes som:

Verdien av balansefaktoren kan være enten 1, 0 eller -1. Hvis hver node i det binære treet har en verdi på enten 1, 0 eller -1, sies det at treet er balansert binært tre eller AVL-tre.

Treet er kjent som et perfekt balansert tre hvis balansefaktoren til hver node er 0. AVL-treet er et nesten balansert tre fordi hver node i treet har verdien av balansefaktor enten 1, 0 eller -1.

Forskjeller mellom det rød-svarte treet og AVL-treet.

Følgende er forskjellene mellom det rød-svarte treet og AVL-treet:

Binært søketre

Det rød-svarte treet er et binært søketre, og AVL-treet er også et binært søketre.

Regler

Følgende regler brukes i et rød-svart tre:

1. Noden i et rød-svart tre er enten rød eller svart i fargen.
2. Fargen på rotnoden skal være svart.
3. De tilstøtende nodene skal ikke være røde. Med andre ord kan vi si at den røde noden ikke kan ha røde barn, men den svarte noden kan ha svarte barn.
4. Det bør være samme antall svarte noder i hver bane; da kan bare et tre betraktes som et rød-svart tre.
5. De eksterne nodene er nullnodene, som alltid er svarte i fargen.

Regel for AVL-treet:

Hver node bør ha balansefaktoren enten som -1, 0 eller 1.

parseint java

Eksempel

I figuren ovenfor må vi sjekke om treet er et rød-svart tre eller ikke. For å sjekke dette må vi først sjekke om treet er et binært søketre eller ikke. Som vi kan observere i figuren ovenfor at den tilfredsstiller alle egenskapene til det binære søketreet; derfor er det et binært søketre. For det andre må vi verifisere om den tilfredsstiller de ovennevnte reglene eller ikke. Treet ovenfor tilfredsstiller alle de fem ovennevnte reglene; derfor konkluderer den med at treet ovenfor er et rød-svart tre.

I figuren ovenfor må vi sjekke om treet er et AVL-tre eller ikke. Siden hver node har en balansefaktorverdi enten som -1, 0 eller 1, så er det et AVL-tre.

Hvordan kan treet betraktes som et balansert tre eller ikke?

I tilfellet med et rød-svart tre, hvis alle reglene ovenfor er oppfylt, forutsatt at et tre er et binært søketre, så sies treet å være et rød-svart tre.

Når det gjelder AVL-treet, hvis balansefaktoren er -1, 0 eller 1, sies treet ovenfor å være et AVL-tre.

Verktøy som brukes til balansering

Hvis treet ikke er balansert, brukes to verktøy for å balansere treet i et rød-svart tre:

Omfarging Rotasjon

Hvis treet ikke er balansert, brukes ett verktøy for å balansere treet i AVL-treet:

b pluss tre

Rotasjon

Effektiv for hvilken operasjon

Når det gjelder det rød-svarte treet, er innsettings- og slettingsoperasjonene effektive. Hvis treet blir balansert gjennom omfargingen, er innsettings- og slettingsoperasjoner effektive i det rød-svarte treet.

Når det gjelder AVL-treet, er søkeoperasjonen effektiv ettersom den krever bare ett verktøy for å balansere treet.

Tidskompleksitet

I tilfellet med rød-svart tre er tidskompleksiteten for alle operasjonene, dvs. innsetting, sletting og søk O(logg).

Når det gjelder AVL-tre, er tidskompleksiteten for alle operasjonene, dvs. innsetting, sletting og søk O(logg).

La oss forstå forskjellene i tabellformen.