An AVL drevo definiran kot samouravnotežen Razlika med višino levega poddrevesa in desnega poddrevesa za katero koli vozlišče je znana kot faktor ravnotežja vozlišča.

pripravite se na testni mockito

Drevo AVL je poimenovano po svojih izumiteljih, Georgyju Adelson-Velskyju in Evgeniju Landisu, ki sta ga objavila v svojem članku iz leta 1962 Algoritem za organizacijo informacij.

Primer dreves AVL:

AVL drevo

Zgornje drevo je AVL, ker so razlike med višinami levega in desnega poddrevesa za vsako vozlišče manjše ali enake 1.

Operacije na drevesu AVL:

• Vstavljanje
• Izbris
• Iskanje [Podobno je iskanju v BST]

Vrtenje poddreves v drevesu AVL:

Drevo AVL se lahko vrti na enega od naslednjih štirih načinov, da ostane uravnoteženo:

Leva rotacija :

Ko je vozlišče dodano v desno poddrevo desnega poddrevesa, če drevo izgubi ravnovesje, izvedemo eno samo levo rotacijo.

logično v niz

Vrtenje v levo v drevesu AVL

Desna rotacija :

Če je vozlišče dodano levemu poddrevesu levega poddrevesa, lahko drevo AVL izgubi ravnovesje, naredimo eno samo desno rotacijo.

Vrtenje v desno v drevesu AVL

Vrtenje levo-desno :

python __ime__

Rotacija levo-desno je kombinacija, pri kateri se izvede prva rotacija v levo po izvedbi te rotacije v desno.

Vrtenje levo-desno v drevesu AVL

Vrtenje desno-levo :

javascript večvrstični niz

Rotacija desno-levo je kombinacija, pri kateri se izvede prva desna rotacija po izvedbi leve rotacije.

Vrtenje desno-levo v drevesu AVL

Aplikacije drevesa AVL:

1. Uporablja se za indeksiranje ogromnih zapisov v bazi podatkov in tudi za učinkovito iskanje v njej.
2. Za vse vrste zbirk v pomnilniku, vključno z nizi in slovarji, se uporabljajo drevesa AVL.
3. Aplikacije za zbirke podatkov, kjer so vstavljanja in brisanja manj pogosta, vendar so potrebna pogosta iskanja podatkov
4. Programska oprema, ki potrebuje optimizirano iskanje.
5. Uporablja se v korporativnih območjih in zgodbenih igrah.

Prednosti drevesa AVL:

1. Drevesa AVL se lahko sama uravnotežijo.
2. Zagotovo ni poševno.
3. Omogoča hitrejše iskanje kot Rdeče-črna drevesa
4. Boljša časovna kompleksnost iskanja v primerjavi z drugimi drevesi, kot je binarno drevo.
5. Višina ne sme presegati log(N), kjer je N skupno število vozlišč v drevesu.

Slabosti drevesa AVL:

1. Težko ga je izvajati.
2. Za nekatere operacije ima visoke konstantne faktorje.
3. Manj uporabljena v primerjavi z rdeče-črnimi drevesi.
4. Zaradi precej strogega ravnovesja drevesa AVL zagotavljajo zapletene operacije vstavljanja in odstranjevanja, saj se izvaja več rotacij.
5. Vzemite več obdelave za uravnoteženje.

Povezani članki:

• Uvod v binarna iskalna drevesa – Vadnice za strukturo podatkov in algoritme
• Vstavljanje v drevo AVL
• Izbris v drevesu AVL