AVL-puu sissejuhatus andmestruktuuris
AVL-puu andmestruktuuris viitab Adelsonile, Velskile ja Landisele. See on binaarse otsingupuu täiustatud versioon. Sellel on kõik binaarse otsingupuu omadused, kuid need erinevad ainult seetõttu, et need säilitavad erinevuse vasaku alapuu ja parema alapuu vahel ning tagavad ka selle, et selle väärtus on puus <= 1, seda nimetatakse tasakaaluks Faktor.
Balance Factor = height(left-subtree) − height(right-subtree)
Näiteks: kaaluge järgmisi puid
Ülaltoodud näites öeldakse, et parema alapuu kõrgus = 2 ja vasak = 3, seega BF = 2, mis on <= 1, on puu tasakaalus.
Miks on meil DS-is vaja AVL-i puud?
Binaarse otsingupuuga töötades puutume kokku stsenaariumiga, kus elemendid on järjestatud järjekorras. Sellistel juhtudel on kõik massiivi elemendid paigutatud juure ühele küljele, see suurendab massiivi elemendi otsimise aja keerukust ja keerukus muutub - O (n), st puu halvimal juhul keerukus . Selliste probleemide lahendamiseks ja otsimisaja lühendamiseks leiutasid AVL-puud Adelson, Velski & Landis.
Näide:
Ülaloleval joonisel oli vasaku alampuu kõrgus = 3 sama
Parema alaosa kõrgus = 0
Seega tasakaalutegur = 3-0 = 3. Seega on sellises puus elemendi otsimisel keerukus O (n), mis sarnaneb lineaarse otsimisega. Selle keeruka otsingu vältimiseks võeti kasutusele AVL-puu, kus puu kõik sõlmed peavad säilima
tasakaalutegur <= 1, vastasel juhul tuleb sellise puu tasakaalustamiseks kasutada erinevaid pöörlemistehnikaid.
Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);
Pöörete tüübid
Kui puu tasakaalutegur ei vasta <= 1 tingimusele, tuleb puu selle tasakaalustatud puuks muutmiseks pöörata.
Seal on 4 tüüpi pöörlemist:
1. Pööre vasakule: kui puu paremal asuva sõlme lisamine muudab selle tasakaalust välja, tuleb sel juhul teha pöörlemine vasakule.
2. Parempoolne pöörlemine: kui sõlme lisamine puu vasakule muudab sõlme tasakaalustamatuks, tuleb teha parem pöörlemine. Teisisõnu, kui sõlmede arv suureneb vasakpoolsel küljel, siis tekib vajadus elementide tasakaalustamiseks selle paremale küljele nihutada, seega öeldakse, et see on parempoolne pöörlemine.
3. Pööre vasakule-paremale: Seda tüüpi pöörlemine on kombinatsioon ülaltoodud kahest selgitatud pöörlemisest. Seda tüüpi pöörlemine toimub siis, kui vasakpoolse puu parempoolsesse alamrühma lisatakse üks element.
Sel juhul teostage esmalt alampuust vasakpööre, millele järgneb vasakpoolse puu parempoolne pöörlemine.
4. Paremale-vasakule pööramine: Seda tüüpi pöörlemine koosneb ka järjestusest, mis koosneb üle kahe pöörde. Seda tüüpi pöörlemist on vaja, kui parema alammenüüst vasakule lisatakse element ja puu muutub tasakaalust välja. Sellisel juhul teostame esmalt parempoolsel alampuul parempoolse pöörlemise ja seejärel parempoolse puu vasakpööramise.
Operatsioonid DSL AVL-puul
Allpool 3 toimingut, mida saab AVL-puul teha: -
1. Otsi
See toiming sarnaneb otsingu tegemisega binaarses otsingupuus. Järgmised sammud on järgmised:
- Lugege elementi, mille kasutaja on öelnud x.
- Võrrelge elementi juurest, kui see on sama, väljuge teisiti, minge järgmisele sammule.
- Kui x
Muu saab minna õige lapse juurde ja võrrelda uuesti.
Järgige protsesse B ja C, kuni leiate elemendi ja väljute.
Sellel protsessil on O (log n) keerukus.
Näide:
 | Mõelge sellele puule, kus peame otsima sõlme väärtust 9. Esmalt laske x = 9, juurväärtus (12)> x, siis peab väärtus asuma juurelemendi vasakus alamrubriigis. |
 | Nüüd võrreldakse x sõlme väärtusega 3 x> 3, seega peame liikuma parema subtrüki poole. |
 | Nüüd võrreldakse x sõlmega (9), kus 9 == 9 tagastab tõese väärtuse. Seega elemendiotsing lõpeb puus. |
2. Sisestus
Elemendi AVL-puusse sisestamisel peame leidma sisestatava asukoha konkreetse elemendi ja seejärel kinnitama element sama nagu sisestus BST-s, kuid pärast seda kontrollitakse, kas puu on endiselt tasakaalus või mitte. st sõlme bilansitegur on <= 1. Ja konkreetsed pöörded viiakse läbi vastavalt vajadusele.
Keerukus on O (log n).
Näide. Vaatleme allolevat puud,
 | Igal sõlmel on tasakaalutegur 0, -1 või 1, seega on puu tasakaalus. Nüüd saate teada, mis juhtub, kui sisestatakse väärtus 1 väärtusega sõlme. Esimene puu läbitakse, et leida koht, kuhu see tuleb sisestada… 1 <2 kirjutatakse seega sõlme (2) vasaku lapsena. |
 | Pärast sisestamist muutub sõlme (9) tasakaalustamatus tasakaaluteguriga = 2. Nüüd pööratakse seda paremale. |
 | Puu saab pärast parempoolset pööramist tasakaalu ja sisestusoperatsioon on edukalt lõpule viidud. |
3. kustutamine
Elemendi kustutamine AVL-puust hõlmab ka puust elemendi otsimist ja seejärel selle kustutamist. Otsimistoiming on sama mis BST-l ja pärast kustutatava elemendi leidmist eemaldatakse element puult ja elemendid kohandatakse, et muuta see uuesti BST-ks. Pärast seda, kui nende elementide tasakaalutegur on 0, -1 või 1, kontrollitakse ja tasakaalustamiseks tasakaalustatakse.
Keerukus, kui O (log n).
 | Mõelge antud puule, mille kõigi tasakaalutegur on 0, -1 või 1. Kustutame nüüd sõlme väärtusega 16. Esimene puu läbitakse, et leida sõlm väärtusega 16, mis on sama kui otsimisalgoritm. |
 | Sõlm 16 asendatakse selle sõlme sisendkäija eelkäijaga, mis on vasakpoolsest alampuust suurim element, st 12 Puu on tasakaalust väljas, mistõttu tuleb teha puurimine. |
 | Nüüd on iga sõlme tasakaalus. |
Järeldus - AVL-puu andmestruktuuris
AVL-puu on binaarse otsingupuu järeltulija, kuid ületab selle suureneva keerukuse puuduse, kui elemente sorteerida. See jälgib puu tasakaalutegurit 0 või 1 või -1. Puu tasakaalustamatuse korral viiakse puu tasakaalustamiseks läbi vastavad pöörlemisvõtted.
Soovitatavad artiklid
See on juhend AVL-puule andmestruktuuris. Siin käsitleme sissejuhatust, AVL-puu operatsioone DS-is ja pöörde tüüpe. Lisateavet leiate ka meie muudest seotud artiklitest -
- jQuery elemendid
- Mis on andmeteadus
- Puude tüübid andmestruktuuris
- C # andmetüübid