Vysvetlenie vkladania, otáčania a faktora vyváženia stromu AVL

Čo je to strom AVL?

Strom AVL je podtypom binárneho vyhľadávacieho stromu. Pomenované podľa vynálezcov Adelsona, Velského a Landisa, majú stromy AVL okrem všetkých vlastností, ktoré vykazujú binárne vyhľadávacie stromy, aj vlastnosť dynamického samovyvažovania.

BST je dátová štruktúra zložená z uzlov. Má nasledujúce záruky:

  1. Každý strom má koreňový uzol (v hornej časti).
  2. Koreňový uzol má nula, jeden alebo dva podradené uzly.
  3. Každý podradený uzol má nulu, jeden alebo dva podradené uzly atď.
  4. Každý uzol má až dve deti.
  5. Pre každý uzol sú jeho ľaví potomkovia menší ako aktuálny uzol, čo je menej ako pravých potomkov.

Stromy AVL majú ďalšiu záruku:

  1. Rozdiel medzi hĺbkou pravého a ľavého podstromu nemôže byť viac ako jeden. Na zachovanie tejto záruky bude implementácia AVL obsahovať algoritmus na opätovné vyváženie stromu, keď by pridanie ďalšieho prvku narušilo túto záruku.

Stromy AVL majú najhorší prípad vyhľadávania, vkladania a mazania času O (log n).

Pravá rotácia

Pravá rotácia stromu AVL

Rotácia doľava

Ľavá rotácia stromu AVL

Proces vkladania AVL

Urobíte vloženie podobné bežnému vloženiu binárneho vyhľadávacieho stromu. Po vložení opravíte vlastnosť AVL pomocou rotácie doľava alebo doprava.

  • Ak dôjde k nerovnováhe u ľavého dieťaťa pravého podstromu, vykonáte rotáciu zľava doprava.
  • Ak dôjde k nerovnováhe u ľavého dieťaťa ľavého podstromu, urobíte pravú rotáciu.
  • Ak dôjde k nerovnováhe u pravého dieťaťa pravého podstromu, vykonáte rotáciu doľava.
  • Ak dôjde k nerovnováhe u pravého potomka ľavého podstromu, vykonáte rotáciu vpravo - vľavo.

Strom AVL je samovyvažujúci binárny vyhľadávací strom. Strom AVL je binárny vyhľadávací strom, ktorý má nasledujúce vlastnosti: -> Podstromy každého uzla sa líšia výškou najviac o jednu. -> Každý podstrom je stromom AVL.

Strom AVL kontroluje výšku ľavého a pravého sub-stromu a zaručuje, že rozdiel nie je väčší ako 1. Tento rozdiel sa nazýva bilančný faktor. Výška stromu AVL je vždy O (Logn), kde n je počet uzlov v strome.

Rotácie stromov AVL

V strome AVL musíme po vykonaní všetkých operácií, ako je vkladanie a mazanie, skontrolovať rovnovážny faktor každého uzla v strome. Ak každý uzol spĺňa podmienku rovnovážneho faktora, operáciu uzavrieme, inak ju musíme vyvážiť. Rotačné operácie používame na to, aby bol strom vyvážený, kedykoľvek sa strom stane nevyváženým v dôsledku akejkoľvek operácie.

Rotačné operácie sa používajú na vyváženie stromu. Existujú štyri rotácie a sú rozdelené do dvoch typov:

Jedna ľavá rotácia (LL rotácia)

Pri rotácii LL sa každý uzol posúva z aktuálnej polohy o jednu pozíciu doľava.

Jedna pravá rotácia (RR rotácia)

Pri rotácii RR sa každý uzol posúva z aktuálnej polohy o jednu pozíciu doprava.

Ľavá pravá rotácia (rotácia LR)

Rotácia LR je kombináciou jednoduchej rotácie vľavo a jednej rotácie vpravo. Pri rotácii LR sa najskôr každý uzol presunie z aktuálnej polohy o jednu pozíciu doľava a potom o jednu pozíciu doprava.

Pravá ľavá rotácia (RL rotácia)

Rotácia RL je kombináciou jednej pravej rotácie, po ktorej nasleduje jednoduchá ľavá rotácia. Pri rotácii RL sa najskôr každý uzol presunie z aktuálnej polohy o jednu pozíciu doprava, potom o jednu pozíciu doľava.

Časová analýza stromov AVL

Strom AVL je binárny vyhľadávací strom s ďalšou vlastnosťou, že rozdiel medzi výškou ľavého podstromu a pravého podstromu ľubovoľného uzla nemôže byť väčší ako 1.

Priemerný algoritmus Najhorší prípad: Medzera:, O(n)Čas:O(n)

Aplikácia stromov AVL

Stromy AVL sú užitočné v prípadoch, keď navrhujete databázu, kde vkladanie a mazanie nie je také časté, ale musíte často vyhľadávať položky, ktoré sa tam nachádzajú.