An AVL koks definēts kā pašlīdzsvarotājs Atšķirība starp kreisā apakškoka un labā apakškoka augstumu jebkuram mezglam ir zināma kā līdzsvara faktors no mezgla.

AVL koks ir nosaukts tā izgudrotāju Džordžija Adelsona-Velska un Jevgeņija Lendisa vārdā, kuri to publicēja savā 1962. gada rakstā Informācijas organizēšanas algoritms.

salīdzināms saraksts

AVL koku piemērs:

AVL koks

Iepriekš minētais koks ir AVL, jo atšķirības starp kreisā un labā apakškoku augstumu katram mezglam ir mazākas vai vienādas ar 1.

Darbības ar AVL koku:

• Ievietošana
• Dzēšana
• Meklēšana [Tas ir līdzīgi meklēšanas veikšanai BST]

Apakškoku pagriešana AVL kokā:

Lai saglabātu līdzsvaru, AVL koks var griezties vienā no četriem veidiem:

iphone emocijzīmes Android tālrunī

Rotācija pa kreisi :

Kad mezgls tiek pievienots labā apakškoka labajā apakškokā, ja koks izkļūst no līdzsvara, mēs veicam vienu rotāciju pa kreisi.

Rotācija pa kreisi AVL kokā

Pareiza rotācija :

Ja kreisā apakškoka kreisajam apakškokam tiek pievienots mezgls, AVL koks var izkļūt no līdzsvara, mēs veicam vienu rotāciju pa labi.

Rotācija pa labi AVL kokā

Rotācija pa kreisi-pa labi :

cits java

Rotācija pa kreisi un pa labi ir kombinācija, kurā pirmā pagriešana notiek pa kreisi pēc tam, kad tiek izpildīta rotācija pa labi.

algoritma dziļuma pirmā meklēšana

Rotācija pa kreisi un pa labi AVL kokā

Rotācija pa labi un pa kreisi :

Rotācija pa labi un pa kreisi ir kombinācija, kurā tiek veikta pirmā pagriešana pa labi pēc tam, kad tiek izpildīta rotācija pa kreisi.

Rotācija pa labi un pa kreisi AVL kokā

AVL Tree pielietojumi:

1. To izmanto, lai indeksētu milzīgus ierakstus datu bāzē un arī efektīvi meklētu tajā.
2. Visu veidu atmiņā esošajām kolekcijām, ieskaitot komplektus un vārdnīcas, tiek izmantoti AVL koki.
3. Datu bāzes lietojumprogrammas, kurās ievietošana un dzēšana ir retāk sastopama, bet ir nepieciešama bieža datu meklēšana
4. Programmatūra, kurai nepieciešama optimizēta meklēšana.
5. To izmanto korporatīvajās jomās un sižeta spēlēs.

AVL Tree priekšrocības:

1. AVL koki var paši sevi līdzsvarot.
2. Tas noteikti nav šķībs.
3. Tas nodrošina ātrāku meklēšanu nekā Red-Black Trees
4. Labāka meklēšanas laika sarežģītība salīdzinājumā ar citiem kokiem, piemēram, bināro koku.
5. Augstums nedrīkst pārsniegt log(N), kur N ir kopējais mezglu skaits kokā.

AVL Tree trūkumi:

1. To ir grūti īstenot.
2. Tam ir augsti nemainīgi faktori dažām operācijām.
3. Mazāk izmantots, salīdzinot ar sarkanmelnajiem kokiem.
4. Pateicoties diezgan stingrajam līdzsvaram, AVL koki nodrošina sarežģītas ievietošanas un noņemšanas darbības, jo tiek veikts vairāk apgriezienu.
5. Veiciet vairāk apstrādes līdzsvarošanai.

Saistītie raksti:

• Ievads binārajā meklēšanas kokos — datu struktūras un algoritmu apmācības
• Ievietošana AVL kokā
• Dzēšana AVL kokā