Introduktion til AVL-træ i datastruktur

AVL-træ i datastruktur henviser til Adelson, Velski & Landis Tree. Dette er en forbedret version af det binære søgetræ. Det har alle funktioner fra Binary Search Tree, men kun adskiller sig, da de opretholder en forskel mellem højden på det venstre under-træ og det højre under-træ og sikrer også, at dets værdi er <= 1 i træet, dette kaldes balance faktor.

Balance Factor = height(left-subtree) − height(right-subtree)

For eksempel: Overvej følgende træer

I ovenstående eksempel er højden på højre undertræ = 2 og venstre = 3 således BF = 2, der er <= 1, således siges træet at være afbalanceret.

Hvorfor har vi brug for et AVL-træ i DS?

Mens vi arbejder med Binary Search Tree, støder vi på et scenarie, hvor elementerne er i sorteret rækkefølge. I sådanne tilfælde er alle elementerne i arrayet arrangeret på den ene side af roden, dette fører til en stigning i tidskompleksiteten for at søge efter et element i en matrix og kompleksiteten bliver- O (n) dvs. værste tilfælde kompleksitet af træet . For at løse sådanne problemer og reducere søgetiden blev AVL-træer opfundet af Adelson, Velski & Landis.

Eksempel:

I ovenstående figur var Højde på venstre undertræ = 3 som

Højde på højre undertråd = 0

Således er balancefaktor = 3-0 = 3. Så søgning efter et element i et sådant træ har O (n) af kompleksitet, der ligner lineær søgning. For at undgå den komplekse søgning blev AVL-træet introduceret, hvor hver knude i træet skal vedligeholdes

balancefaktor <= 1, ellers skal forskellige rotationsteknikker udføres for at afbalancere et sådant træ.

Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);

Typer af rotationer

Når balancefaktoren for træet ikke tilfredsstiller <= 1 betingelse, skal der udføres rotationer på dem for at gøre det til et afbalanceret træ.

Der er 4 typer rotationer:

1. Venstre rotation: Hvis tilføjelsen af ​​en knude til højre for træet gør det ubalance, skal der i så fald venstre rotation udføres.

2. Højre rotation: Hvis tilføjelsen af ​​en knude til venstre for træet skaber knudepunktobalance, skal højre rotation udføres. Med andre ord, når antallet af noder øges på venstre side, fremkommer der et behov for at flytte elementerne til højre for at afbalancere det, og det siges at være højre rotation.

3. Venstre-højre rotation: Denne rotationstype er en kombination af de ovenfor nævnte 2 rotationer forklaret. Denne rotationstype opstår, når et element tilføjes til højre undertræ i et venstre træ.

I et sådant tilfælde skal du først udføre venstre rotation på undertråden efterfulgt af en højre rotation af venstre træ.

4. Højre-venstre rotation: Denne rotationstype er også sammensat af en sekvens på over 2 rotationer. Denne type rotation er nødvendig, når et element tilføjes til venstre for højre undertræ, og træet bliver ubalanceret. I et sådant tilfælde udfører vi først højre rotation på højre undertrin og derefter venstre rotation på højre træ.

Funktioner på AVL-træ i DS

Nedenfor 3 handlinger, der kan udføres på AVL-træet:

1. Søg

Denne handling ligner udførelsen af ​​en søgning i Binary Search Tree. Følgende trin er som nedenfor:

  • Læs elementet leveret af brugeren siger x.
  • Sammenlign elementet fra roden, hvis det er det samme, skal du afslutte ellers gå til næste trin.
  • Hvis x

Ellers gå til det rigtige barn og sammenlign igen.

Følg processer B og C, indtil du finder elementet og afslutte.

Denne proces har O (log n) kompleksitet.

Eksempel:

Overvej dette træ, hvor vi er nødt til at udføre en søgning efter nodeværdi 9.
Lad først x = 9, rodværdi (12)> x derefter, værdien skal være i den venstre undertræ i rodelementet.
Nu sammenlignes x med knudeværdien 3
x> 3 derfor skal vi gå mod det rigtige undertrin.
Nu sammenlignes x med node (9), hvor 9 == 9 returnerer sandt. Elementetsøgning afsluttes således i træet.

2. Indsættelse

Når vi indsætter et element i AVL-træet, er vi nødt til at finde det sted, hvor bestemt element, der skal indsættes, og derefter er elementet knyttet det samme som en indsættelse i BST, men efter det kontrolleres det, om træet stadig er afbalanceret eller ej dvs. balancefaktoren for en knude er <= 1. Og særlige rotationer udføres efter behov.

Kompleksiteten er O (log n).
Eksempel: Overvej nedenstående træ,

Hver knude har en balancefaktor som 0, -1 eller 1, således at træet er afbalanceret. Lad nu hvad der sker, når en node med værdi 1 indsættes.
Det første træ krydses for at finde det sted, hvor det skal indsættes …
1 <2 er således skrevet som et venstre barn af noden (2).
Efter indsættelse bliver knudepunktet (9) ubalance med en balancefaktor = 2. Nu udsættes den for højre rotation.
Et træ bliver balance efter højre rotation og dermed er indsættelsesoperationen afsluttet.

3. Sletning

Sletning af et element i AVL-træet omfatter også at søge efter et element i træet og derefter slette det. Søgefunktionen er den samme som BST, og efter at have fundet det element, der skal slettes, fjernes elementet fra træet, og elementerne justeres for at gøre det til BST igen. Efter at disse elementer er kontrolleret for at have en balancefaktor på 0, -1 eller 1, og således udføres passende rotationer for at gøre det afbalanceret.

Kompleksitet, hvis O (log n).

Overvej det givne træ, hvis alle har en balancefaktor på 0, -1 eller 1.
Lad os nu slette en node med værdi 16.
Det første træ gennemskæres for at finde noden med værdien 16 som en søgealgoritme.
Node 16 vil blive erstattet med inorder-forgængeren for denne knude, der er det største element fra venstre undertræ, dvs. 12
Træet er blevet ubalanceret, og derfor skal LL - rotation udføres.
Nu er hver knude blevet afbalanceret.

Konklusion - AVL-træ i datastruktur

AVL-træet er en efterkommer af Binary Search Tree, men overvinder dets ulempe med stigende kompleksitet, hvis elementerne sorteres. Det overvåger balancefaktoren for træet til at være 0 eller 1 eller -1. I tilfælde af at træet bliver ubalanceret udføres tilsvarende rotationsteknikker for at afbalancere træet.

Anbefalede artikler

Dette er en guide til AVL-træ i datastruktur. Her diskuterer vi Introduktion, betjening på AVL-træ i DS og rotationstyper. Du kan også gennemgå vores andre relaterede artikler for at lære mere–

  1. jQuery Elements
  2. Hvad er datavidenskab
  3. Typer af træer i datastruktur
  4. C # Datatyper

Kategori:

Big Data