Før vi vet om forskjellene mellom det binære søketreet og AVL-treet, bør vi vite om det binære søketreet og AVL-treet separat.

Hva er et binært søketre?

De binært søketre er en tre binært tre. Som vi vet, kan det treet ha 'n' antall barn, mens; det binære treet kan inneholde de ytterste to barna. Så begrensningen til et binært tre følges også av det binære søketreet. Hver node i et binært søketre bør ha de ytterste to barn; med andre ord kan vi si at det binære søketreet er en variant av det binære treet.

Det binære søketreet følger også egenskapene til det binære søket. I binært søk må alle elementene i en matrise være i sortert rekkefølge. Vi beregner det midterste elementet i det binære søket der venstre del av midtelementet inneholder verdien som er mindre enn midtverdien, og høyre del av midtelementet inneholder verdiene som er større enn midtverdien.

I binært søketre blir det midterste elementet rotnoden, høyre del blir høyre undertre, og venstre del blir venstre undertre. Derfor kan vi si at det binære søketreet er en kombinasjon av a binært tre og binært søk .

Merk: Binært søketre kan defineres som det binære treet der alle elementene i det venstre undertreet er mindre enn rotnoden, og alle elementene i det høyre undertreet er større enn rotnoden.

Tidskompleksitet i binært søketre

Hvis det binære søketreet er nesten et balansert tre, vil alle operasjonene ha en tidskompleksitet på O(logn) fordi søket er delt enten til venstre eller høyre undertre.

navn på sminkeprodukter

Hvis det binære søketreet er enten venstre- eller høyreskjevt, vil alle operasjonene ha samme tidskompleksitet som På) fordi vi må krysse til de n elementene.

Hva er AVL-treet?

An AVL-tre er et selvbalanserende binært søketre der forskjellen mellom høyder på venstre og høyre undertrær ikke kan være mer enn ett. Denne forskjellen er kjent som en balansefaktor. I AVL-treet kan verdiene for balansefaktor være enten -1, 0 eller 1.

Hvordan skjer selvbalanseringen av det binære søketreet?

Som vi vet er AVL-treet et selvbalanserende binært søketre. Hvis det binære søketreet ikke er balansert, kan det være selvbalansert med noen omorganiseringer. Disse omarrangeringene kan gjøres ved hjelp av noen rotasjoner.

La oss forstå selvbalansering gjennom et eksempel.

if else statement java

Anta at vi ønsker å sette inn 10, 20, 30 i et AVL-tre.

Følgende er måtene å sette inn 10, 20, 30 i et AVL-tre:

Hvis rekkefølgen for innsetting er 30, 20, 10.

Trinn 1: Først lager vi et binært søketre, som vist nedenfor:

Steg 2: I figuren ovenfor kan vi observere at treet er ubalansert fordi balansefaktoren til node 30 er 2. For å gjøre det til et AVL-tre, må vi utføre noen rotasjoner. Hvis vi utfører riktig rotasjon på node 20, vil noden 30 bevege seg nedover, mens noden 20 vil bevege seg oppover, som vist nedenfor:

Som vi kan observere, følger det endelige treet egenskapen til det binære søketreet og et balansert tre; derfor er det et AVL-tre.

I saken var treet venstre ubalansert tre, så vi utfører riktig rotasjon på noden.

Hvis rekkefølgen for innsetting er 10, 20, 30.

Trinn 1: Først lager vi et binært søketre som vist nedenfor:

Steg 2: I figuren ovenfor kan vi observere at treet er ubalansert fordi balansefaktoren til node 10 er -2. For å gjøre det til et AVL-tre, må vi utføre noen rotasjoner. Det er et høyre ubalansert tre, så vi vil utføre venstrerotasjon. Hvis vi utfører venstrerotasjon på node 20, vil node 20 bevege seg oppover, og node 10 vil bevege seg nedover, som vist nedenfor:

Som vi kan observere, følger det endelige treet eiendommen til Binært søketre og a balansert tre ; derfor er det et AVL-tre.

Hvis rekkefølgen for innsetting er 30, 10, 20

Trinn 1: Først lager vi det binære søketreet som vist nedenfor:

Steg 2: I figuren ovenfor kan vi observere at treet er ubalansert fordi balansefaktoren til rotnoden er 2. For å gjøre det til et AVL-tre, må vi utføre noen rotasjoner. Scenarioet ovenfor er venstre-høyre ubalansert ettersom en node er til venstre for overordnet node og en annen er høyre for overordnet node. Først vil vi utføre venstrerotasjonen, og rotasjonen skjer mellom nodene 10 og 20. Etter venstrerotasjonen vil 20 bevege seg oppover, og 10 vil bevege seg nedover som vist nedenfor:

Likevel er treet ubalansert, så vi utfører riktig rotasjon på treet. Når riktig rotasjon er utført på treet, vil treet gjerne, som vist nedenfor:

Som vi kan observere i treet ovenfor, følger treet egenskapen til det binære søketreet og et balansert tre; derfor er det et AVL-tre.

Hvis rekkefølgen på innsettingen er 10, 30, 20

Trinn 1: Først lager vi det binære søketreet, som vist nedenfor:

Steg 2: I figuren ovenfor kan vi observere at treet er ubalansert fordi balansefaktoren til rotnoden er 2. For å gjøre det til et AVL-tre, må vi utføre noen rotasjoner. Scenarioet ovenfor er høyre-venstre ubalansert ettersom en node er rett for sin overordnede node, og en annen node er til venstre for sin overordnede node. Først vil vi utføre riktig rotasjon som skjer mellom nodene 30 og 20. Etter høyre rotasjon vil 20 bevege seg oppover, og 30 vil bevege seg nedover som vist nedenfor:

10 ml er hvor mye

Likevel er treet ovenfor ubalansert, så vi må utføre venstrerotasjon på noden. Når venstrerotasjonen er utført, vil noden 20 bevege seg oppover, og noden 10 vil bevege seg nedover som vist nedenfor:

Som vi kan observere i treet ovenfor, følger treet egenskapen til det binære søketreet og et balansert tre; derfor er det et AVL-tre.

Forskjeller mellom binært søketre og AVL-tre