An AVL træ defineret som en selvbalancering Forskellen mellem højderne af det venstre undertræ og det højre undertræ for enhver node er kendt som balancefaktor af noden.

AVL-træet er opkaldt efter dets opfindere, Georgy Adelson-Velsky og Evgenii Landis, som offentliggjorde det i deres papir fra 1962 En algoritme til organisering af information.

Eksempel på AVL-træer:

AVL træ

Ovenstående træ er AVL, fordi forskellene mellem højderne af venstre og højre undertræer for hver knude er mindre end eller lig med 1.

Operationer på et AVL-træ:

• Indskud
• Sletning
• Søger [Det svarer til at udføre en søgning i BST]

Rotation af undertræerne i et AVL-træ:

Et AVL-træ kan rotere på en af ​​følgende fire måder for at holde sig selv afbalanceret:

Venstre rotation :

Når en node tilføjes til højre undertræ i højre undertræ, hvis træet kommer ud af balance, foretager vi en enkelt venstrerotation.

Venstre-rotation i AVL-træet

Højre rotation :

Hvis en node tilføjes til venstre undertræ i venstre undertræ, kan AVL-træet komme ud af balance, vi foretager en enkelt højrerotation.

Højre-rotation i AVL-træet

Venstre-højre rotation :

En venstre-højre-rotation er en kombination, hvor den første venstredrejning finder sted, efter at den højre rotation udføres.

int i streng

Venstre-højre rotation i AVL-træet

Højre-venstre rotation :

En højre-venstre rotation er en kombination, hvor den første højre rotation finder sted, efter at venstre rotation udføres.

Højre-venstre rotation i AVL-træet

Anvendelser af AVL Tree:

1. Det bruges til at indeksere enorme poster i en database og også til effektivt at søge i den.
2. Til alle typer af in-memory-samlinger, inklusive sæt og ordbøger, bruges AVL Trees.
3. Databaseapplikationer, hvor indsættelser og sletninger er mindre almindelige, men hyppige dataopslag er nødvendige
4. Software, der kræver optimeret søgning.
5. Det anvendes i virksomhedsområder og historiespil.

Fordele ved AVL Tree:

1. AVL-træer kan selvbalancere sig selv.
2. Det er bestemt ikke skævt.
3. Det giver hurtigere opslag end rød-sorte træer
4. Bedre søgetidskompleksitet sammenlignet med andre træer som binært træ.
5. Højde kan ikke overstige log(N), hvor N er det samlede antal knudepunkter i træet.

Ulemper ved AVL Tree:

1. Det er svært at gennemføre.
2. Det har høje konstante faktorer for nogle af operationerne.
3. Mindre brugt sammenlignet med rød-sorte træer.
4. På grund af dens ret strenge balance giver AVL-træer komplicerede indsætnings- og fjernelsesoperationer, efterhånden som flere rotationer udføres.
5. Tag mere behandling for at balancere.

Relaterede artikler:

• Introduktion til binære søgetræer – datastruktur og algoritmevejledninger
• Indsættelse i et AVL-træ
• Sletning i et AVL-træ