An AVL-tre definert som en selvbalansering Forskjellen mellom høydene til venstre undertre og høyre undertre for en hvilken som helst node er kjent som balansefaktor av noden.

AVL-treet er oppkalt etter dets oppfinnere, Georgy Adelson-Velsky og Evgenii Landis, som publiserte det i deres papir fra 1962 En algoritme for organisering av informasjon.

Eksempel på AVL-trær:

AVL-tre

Treet ovenfor er AVL fordi forskjellene mellom høydene til venstre og høyre undertrær for hver node er mindre enn eller lik 1.

Operasjoner på et AVL-tre:

• Innsetting
• Sletting
• Søker [Det ligner på å utføre et søk i BST]

Rotere undertrærne i et AVL-tre:

Et AVL-tre kan rotere på en av følgende fire måter for å holde seg selv balansert:

Venstre rotasjon :

Når en node legges inn i høyre undertre i høyre undertre, hvis treet kommer ut av balanse, gjør vi en enkelt venstrerotasjon.

Venstre-rotasjon i AVL-treet

Høyre rotasjon :

Hvis en node legges til det venstre undertreet til det venstre undertreet, kan AVL-treet komme ut av balanse, vi gjør en enkelt høyrerotasjon.

Høyre-rotasjon i AVL-treet

Venstre-høyre rotasjon :

En venstre-høyre-rotasjon er en kombinasjon der første venstrerotasjon finner sted etter at høyrerotasjonen utføres.

pete davidson alder

Venstre-Høyre Rotasjon i AVL-treet

Høyre-venstre rotasjon :

En høyre-venstre-rotasjon er en kombinasjon der første høyrerotasjon finner sted etter at venstrerotasjonen utføres.

Høyre-venstre rotasjon i AVL-treet

Anvendelser av AVL Tree:

1. Den brukes til å indeksere enorme poster i en database og også for å effektivt søke i den.
2. For alle typer in-memory-samlinger, inkludert sett og ordbøker, brukes AVL Trees.
3. Databaseapplikasjoner, der innsettinger og slettinger er mindre vanlige, men hyppige dataoppslag er nødvendig
4. Programvare som trenger optimalisert søk.
5. Det brukes i bedriftsområder og historiespill.

Fordeler med AVL Tree:

1. AVL-trær kan selvbalansere seg selv.
2. Det er sikkert ikke skjevt.
3. Det gir raskere oppslag enn rød-svarte trær
4. Bedre søketidskompleksitet sammenlignet med andre trær som binært tre.
5. Høyden kan ikke overstige log(N), hvor N er det totale antallet noder i treet.

Ulemper med AVL Tree:

1. Det er vanskelig å gjennomføre.
2. Den har høye konstante faktorer for noen av operasjonene.
3. Mindre brukt sammenlignet med rød-svarte trær.
4. På grunn av sin ganske strenge balanse, gir AVL-trær kompliserte innsettings- og fjerningsoperasjoner ettersom flere rotasjoner utføres.
5. Ta mer prosessering for balansering.

Relaterte artikler:

• Introduksjon til binære søketrær – veiledninger for datastruktur og algoritmer
• Innsetting i et AVL-tre
• Sletting i et AVL-tre