AVL-træindsættelse, rotation og balancefaktor forklaret

Hvad er et AVL-træ?

Et AVL-træ er en undertype af binært søgetræ. AVL-træer er opkaldt efter opfinderne Adelson, Velskii og Landis og har ejendommen til dynamisk selvbalancering ud over alle de ejendomme, der udstilles af binære søgetræer.

En BST er en datastruktur sammensat af noder. Det har følgende garantier:

  1. Hvert træ har en rodknude (øverst).
  2. Rodknudepunktet har nul, en eller to underknudepunkter.
  3. Hver barneknude har nul, en eller to underknudepunkter osv.
  4. Hver knude har op til to børn.
  5. For hver node er dens venstre efterkommere mindre end den aktuelle node, hvilket er mindre end de rigtige efterkommere.

AVL-træer har en ekstra garanti:

  1. Forskellen mellem dybden af ​​højre og venstre undertræ kan ikke være mere end en. For at opretholde denne garanti vil en implementering af en AVL omfatte en algoritme til at genbalancere træet, når tilføjelse af et ekstra element vil forstyrre denne garanti.

AVL-træer har en worst case-opslag, indsæt og slet tid for O (log n).

Højre rotation

AVL Tree Right Rotation

Venstre rotation

AVL Tree Venstre rotation

AVL-indsættelsesproces

Du foretager en indsættelse svarende til en normal indsættelse af binært søgetræ. Efter indsættelse løser du AVL-egenskaben ved at dreje til venstre eller højre.

  • Hvis der er en ubalance i venstre barn af højre undertræ, udfører du en venstre-højre rotation.
  • Hvis der er ubalance i venstre barn i venstre undertræ, udfører du en højre rotation.
  • Hvis der er ubalance i højre barn af højre undertræ, udfører du en venstre rotation.
  • Hvis der er ubalance i højre barn af venstre undertræ, udfører du en højre-venstre rotation.

Et AVL-træ er et selvbalancerende binært søgetræ. Et AVL-træ er et binært søgetræ, der har følgende egenskaber: -> Undertræerne for hver node adskiller sig højst med højst en. -> Hvert undertræ er et AVL-træ.

AVL-træet kontrollerer højden på venstre og højre undertræ og sikrer, at forskellen ikke er mere end 1. Denne forskel kaldes balancefaktoren. Højden på et AVL-træ er altid O (Logn), hvor n er antallet af noder i træet.

AVL-trærotationer

I AVL-træ skal vi efter at have udført hver operation som indsættelse og sletning kontrollere balancefaktoren for hver node i træet. Hvis hver knudepunkt opfylder balancefaktorbetingelsen, afslutter vi operationen, ellers skal vi gøre den afbalanceret. Vi bruger rotationsoperationer til at gøre træet afbalanceret, når træet bliver ubalanceret på grund af enhver operation.

Rotationsoperationer bruges til at gøre et træ afbalanceret. Der er fire rotationer, og de er klassificeret i to typer:

Enkelt venstre rotation (LL-rotation)

I LL-rotation bevæger hver knude en position til venstre fra den aktuelle position.

Single Right Rotation (RR Rotation)

I RR-rotation bevæger hver knude en position til højre fra den aktuelle position.

Venstre højre rotation (LR-rotation)

LR-rotationen er en kombination af en enkelt venstre rotation efterfulgt af en enkelt højre rotation. I LR-rotation bevæger først hver node en position til venstre og derefter en position til højre fra den aktuelle position.

Højre venstre rotation (RL-rotation)

RL Rotation er en kombination af en enkelt højre rotation efterfulgt af en enkelt rotation til venstre. I RL-rotation bevæger først hver node en position til højre og derefter en position til venstre fra den aktuelle position.

Tidsanalyse af AVL-træer

AVL-træ er binært søgetræ med yderligere egenskab, at forskellen mellem højden på venstre undertræ og højre undertræ på enhver node ikke kan være mere end 1.

Algoritme Gennemsnit Værste tilfælde: Mellemrum:, O(n)Tid:O(n)

Anvendelse af AVL træer

AVL-træer er gavnlige i de tilfælde, hvor du designer en database, hvor indsættelser og sletninger ikke er så hyppige, men du ofte skal slå op for de emner, der er derinde.