Uvod v AVL drevo v strukturi podatkov
Drevo AVL v strukturi podatkov se nanaša na drevo Adelson, Velski in Landis. To je izboljšana različica drevesa binarnega iskanja. Vse funkcije ima kot binarno drevo za iskanje, vendar se razlikujejo le po tem, da ohranjajo razliko med višino levega pod drevesa in desnim pod drevesom, poleg tega pa zagotavljajo, da je njegova vrednost v drevesu <= 1, to je znano kot Balance Faktor.
Balance Factor = height(left-subtree) − height(right-subtree)
Na primer: Upoštevajte naslednja drevesa
V zgornjem primeru je višina desnega pod drevesa = 2 in leve = 3, torej BF = 2, kar je <= 1, torej naj bi bilo drevo uravnoteženo.
Zakaj potrebujemo drevo AVL v DS?
Med delom z binarnim drevesom iskanja naletimo na scenarij, v katerem so elementi razvrščeni. V takšnih primerih so vsi elementi matrike razporejeni na eni strani korena, kar vodi do povečanja časovne zapletenosti iskanja elementa v matriki in kompleksnost postane -O (n), tj. Najslabša zapletenost drevesa . Za reševanje takšnih vprašanj in zmanjšanje časa iskanja so AVL drevesa izumili Adelson, Velski in Landis.
Primer:
Na zgornji sliki je bila višina levega podreja = 3
Višina desnega podstavka = 0
Tako je faktor ravnotežja = 3-0 = 3. Tako iskanje elementa v takšnem drevesu ima O (n) zapletenosti, ki je podobna linearnemu iskanju. Da bi se izognili zapletenemu iskanju, je bilo uvedeno drevo AVL, kjer mora vzdrževati vsako vozlišče v drevesu
faktor ravnotežja <= 1, sicer se za uravnoteženje takšnega drevesa izvajajo različne tehnike vrtenja.
Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);
Vrste rotacij
Če faktor uravnoteženosti drevesa ne izpolnjuje pogoja <= 1, je treba na njih opraviti vrtenja, da se spremeni v uravnoteženo drevo.
Obstajajo 4 vrste rotacij:
1. Levo vrtenje: Če dodajanje vozlišča desno od drevesa povzroči neravnovesje, potem je treba v tem primeru izvesti levo vrtenje.
2. Desno vrtenje: Če dodatek vozlišča na levi strani drevesa povzroči neravnovesje vozlišča, je treba izvesti desno rotacijo. Z drugimi besedami, ko se število vozlišč poveča na levi strani, potem se pojavi potreba po premikanju elementov na desno stran, da se uravnoteži, zato se pravi, da je desno vrtenje.
3. Levo-desno vrtenje: Ta vrsta vrtenja je kombinacija zgoraj navedenih dveh rotacij. Ta vrsta vrtenja se pojavi, ko je en element dodan v desno podrežje levega drevesa.
V takem primeru najprej izvedite vrtenje v levo na poddrevi, nato pa desno vrtenje levega drevesa.
4. Desno-levo vrtenje: Ta vrsta vrtenja je sestavljena tudi iz zaporedja zgornjih 2 vrtenja. Ta vrsta vrtenja je potrebna, če se element doda na levi strani desnega podstavka in drevo postane neuravnoteženo. V takem primeru najprej izvedemo desno vrtenje na desnem podrevju in nato levo vrtenje na desnem drevesu.
Operacije na drevesu AVL v DS
Spodaj 3 operacije, ki jih je mogoče izvesti na drevesu AVL:
1. Iščite
Ta operacija je podobna iskanju v binarnem iskalnem drevesu. Sledijo naslednji koraki:
- Preberite element, ki ga uporabnik reče x.
- Primerjajte element iz korena, če je isti, potem izstopite drugače, pojdite na naslednji korak.
- Če x
Pojdi še do pravega otroka in še enkrat primerjaj.
Sledite procesom B in C, dokler ne najdete elementa in zapustite.
Ta postopek ima zapletenost O (log n).
Primer:
 | Razmislite o tem drevesu, kjer moramo opraviti iskanje vrednosti vozlišča 9. Najprej x = 9, korenska vrednost (12)> x, potem mora biti vrednost v levem podrevju korenskega elementa. |
 | Zdaj se x primerja z vrednostjo 3 vozlišča x> 3 torej moramo nadaljevati proti desnemu podrejenju. |
 | Zdaj se x primerja z vozliščem (9), kjer 9 == 9 vrne resnico. Tako se iskanje elementov dokonča v drevesu. |
2. Vstavitev
Med vstavljanjem elementa v drevo AVL moramo poiskati določen element, ki ga je treba vstaviti, nato pa je element pritrjen enako kot vstavitev v BST, potem pa preverimo, ali je drevo še uravnoteženo ali ne tj. faktor ravnotežja vozlišča je <= 1. In določene rotacije se izvajajo po potrebi.
Kompleksnost je O (log n).
Primer: razmislite o spodnjem drevesu,
 | Vsako vozlišče ima faktor ravnotežja kot 0, -1 ali 1, zato je drevo uravnoteženo. Zdaj pustimo, kaj se zgodi, ko je vstavljeno vozlišče z vrednostjo 1. Prvo drevo se prečka in poišče mesto, kamor ga je treba vstaviti … 1 <2 je tako zapisan kot levi otrok vozlišča (2). |
 | Po vstavitvi postane vozlišče (9) neuravnoteženo s faktorjem ravnotežja = 2. Zdaj se podvrže desni rotaciji. |
 | Drevo postane ravnotežje po desni zasuku in s tem je operacija vstavitve uspešno končana. |
3. Črtanje
Brisanje elementa v drevesu AVL vključuje tudi iskanje elementa v drevesu in njegovo brisanje. Iskalna operacija je enaka kot BST in po iskanju elementa, ki ga je treba izbrisati, se element odstrani z drevesa in elementi se prilagodijo tako, da postane ponovno BST. Ko se preveri, ali imajo faktor uravnoteženosti 0, -1 ali 1, se izvedejo ustrezne rotacije, da se uravnoteži.
Kompleksnost, če O (log n).
 | Upoštevajmo dano drevo, katerega vsi imajo faktor uravnoteženosti 0, -1 ali 1. Zdaj izbrišemo vozlišče z vrednostjo 16. Prvo drevo je prečkano, da bi našlo vozlišče z vrednostjo 16 enako algoritmu iskanja. |
 | Vozlišče 16 bo nadomeščeno s predhodnim vrstnim redom tega vozlišča, ki je največji element levega podrejeja, tj. 12 Drevo je postalo neuravnoteženo, zato je treba izvesti vrtenje LL. |
 | Zdaj je vsako vozlišče postalo uravnoteženo. |
Zaključek - AVL drevo v strukturi podatkov
Drevo AVL je potomec binarnega iskalnega drevesa, vendar premaga pomanjkljivosti vse večje zapletenosti, če so elementi razvrščeni. Spremlja faktor uravnoteženosti drevesa 0 ali 1 ali -1. Če drevo postane neuravnoteženo, se za uravnoteženje drevesa izvedejo ustrezne tehnike vrtenja.
Priporočeni članki
To je vodnik za drevo AVL v strukturi podatkov. Tukaj razpravljamo o uvodu, operacijah na drevesu AVL v DS in vrstah rotacij. Obiščite lahko tudi druge naše sorodne članke, če želite izvedeti več -
- jQuery Elementi
- Kaj je Data Science
- Vrste dreves v strukturi podatkov
- C # podatkovni tipi