Strom AVL vynalezli GM Adelson - Velsky a EM Landis v roce 1962. Strom je pojmenován AVL na počest svých vynálezců.
příkaz java switch
AVL Tree lze definovat jako výškově vyvážený binární vyhledávací strom, ve kterém je každý uzel spojen s balančním faktorem, který se vypočítá odečtením výšky jeho pravého podstromu od výšky jeho levého podstromu.
Říká se, že strom je vyvážený, pokud je faktor vyvážení každého uzlu v rozmezí -1 až 1, jinak bude strom nevyvážený a bude nutné jej vyvážit.
Faktor vyvážení (k) = výška (vlevo(k)) - výška (vpravo(k))
Pokud je faktor vyvážení libovolného uzlu 1, znamená to, že levý podstrom je o jednu úroveň výše než pravý podstrom.
Pokud je faktor vyvážení libovolného uzlu 0, znamená to, že levý podstrom a pravý podstrom mají stejnou výšku.
Pokud je faktor vyvážení libovolného uzlu -1, znamená to, že levý podstrom je o jednu úroveň níže než pravý podstrom.
AVL strom je uveden na následujícím obrázku. Můžeme vidět, že faktor rovnováhy spojený s každým uzlem je mezi -1 a +1. jedná se tedy o příklad stromu AVL.
Složitost
| Algoritmus | Průměrný případ | Nejhorší případ |
|---|---|---|
| Prostor | na) | na) |
| Vyhledávání | o (log n) | o (log n) |
| Vložit | o (log n) | o (log n) |
| Vymazat | o (log n) | o (log n) |
Operace na stromu AVL
Vzhledem k tomu, že strom AVL je také binárním vyhledávacím stromem, jsou všechny operace prováděny stejným způsobem, jako se provádějí v binárním vyhledávacím stromu. Vyhledávání a procházení nevede k narušení vlastnictví stromu AVL. Vkládání a mazání jsou však operace, které mohou tuto vlastnost narušit, a proto je třeba je znovu navštívit.
| SN | Úkon | Popis |
|---|---|---|
| 1 | Vložení | Vkládání do stromu AVL se provádí stejným způsobem, jako se provádí v binárním vyhledávacím stromu. Může to však vést k porušení vlastnosti stromu AVL, a proto může strom vyžadovat vyvážení. Strom lze vyvážit použitím rotací. |
| 2 | Vymazání | Odstranění lze také provést stejným způsobem, jako se provádí v binárním vyhledávacím stromu. Odstranění může také narušit rovnováhu stromu, proto se k obnovení rovnováhy stromu používají různé typy rotací. |
Proč AVL Tree?
AVL strom řídí výšku binárního vyhledávacího stromu tím, že jej nedovoluje zkosit. Čas potřebný pro všechny operace v binárním vyhledávacím stromu o výšce h je Ach) . Lze ji však rozšířit na Na) pokud bude BST zkreslený (tj. nejhorší případ). Omezením této výšky na log n, AVL strom ukládá horní hranici pro každou operaci, která má být O(log n) kde n je počet uzlů.
AVL rotace
Rotaci ve stromu AVL provádíme pouze v případě, že je Balance Factor jiný než -1, 0 a 1 . V zásadě existují čtyři typy rotací, které jsou následující:
- L L rotace: Vložený uzel je v levém podstromu levého podstromu A
- R R rotace: Vložený uzel je v pravém podstromu pravého podstromu A
- L R rotace: Vložený uzel je v pravém podstromu levého podstromu A
- R L rotace: Vložený uzel je v levém podstromu pravého podstromu A
Kde uzel A je uzel, jehož součinitel rovnováhy je jiný než -1, 0, 1.
První dvě rotace LL a RR jsou jednoduché rotace a další dvě rotace LR a RL jsou dvojité rotace. Aby byl strom nevyvážený, musí být minimální výška alespoň 2. Rozumějme každé otočení
1. Rotace RR
Když se BST stane nevyváženým, protože uzel je vložen do pravého podstromu pravého podstromu A, pak provedeme rotaci RR, rotace RR je rotace proti směru hodinových ručiček, která se aplikuje na hranu pod uzlem s faktorem rovnováhy -2
Ve výše uvedeném příkladu má uzel A balanční faktor -2, protože uzel C je vložen do pravého podstromu A pravého podstromu. Rotaci RR provádíme na hraně pod A.
2. Rotace LL
Když se BST stane nevyváženým, protože uzel je vložen do levého podstromu levého podstromu C, pak provedeme rotaci LL, rotace LL je rotace ve směru hodinových ručiček, která se aplikuje na hranu pod uzlem s faktorem rovnováhy 2.
Ve výše uvedeném příkladu má uzel C balanční faktor 2, protože uzel A je vložen do levého podstromu C levého podstromu. Rotaci LL provádíme na hraně pod A.
3. Rotace LR
Dvojité rotace jsou o něco tvrdší než jednoduchá rotace, jak již bylo vysvětleno výše. LR rotace = RR rotace + LL rotace, tj. nejprve se provede rotace RR na podstromu a poté rotace LL na celém stromu, plným stromem rozumíme první uzel z dráhy vloženého uzlu, jehož faktor vyvážení je jiný než -1 , 0 nebo 1.
typy spojení v rdbms
Pochopme každý krok velmi jasně:
| Stát | Akce |
|---|---|
 | Uzel B byl vložen do pravého podstromu A levého podstromu C, díky čemuž se C stal nevyváženým uzlem s balančním faktorem 2. V tomto případě je rotace L R, kde: Vložený uzel je v pravém podstromu levého podstromu stromu C |
 | Protože rotace LR = rotace RR + LL, proto se nejprve provede RR (proti směru hodinových ručiček) na podstromu s kořenem v A. Provedením rotace RR uzel A , se stal levým podstromem B . |
 | Po provedení rotace RR je uzel C stále nevyvážený, tj. má balanční faktor 2, protože vložený uzel A je vlevo od C |
 | Nyní provedeme LL rotaci ve směru hodinových ručiček na plném stromu, tedy na uzlu C. node C se nyní stal pravým podstromem uzlu B, A je levým podstromem uzlu B |
 | Faktor vyvážení každého uzlu je nyní buď -1, 0 nebo 1, tj. BST je nyní vyvážený. |
4. Rotace RL
Jak již bylo diskutováno, že dvojité rotace jsou o něco tvrdší než jednoduchá rotace, která již byla vysvětlena výše. R L rotace = LL rotace + RR rotace, tj. nejprve se provede rotace LL na podstromu a poté rotace RR na celém stromu, plným stromem rozumíme první uzel z dráhy vloženého uzlu, jehož faktor vyvážení je jiný než -1 , 0 nebo 1.
| Stát | Akce |
|---|---|
 | Uzel B byl vložen do levého podstromu C pravý podstrom A , kvůli kterému se A stal nevyváženým uzlem s balančním faktorem - 2. V tomto případě se jedná o rotaci RL, kde: Vložený uzel je v levém podstromu pravého podstromu A |
 | Protože rotace RL = rotace LL + rotace RR, tedy LL (ve směru hodinových ručiček) na podstromu zakořeněném v C se provádí jako první. Provedením rotace RR uzel C se stal správným podstromem B . |
 | Po provedení rotace LL uzel A je stále nevyvážený, tj. má balanční faktor -2, což je způsobeno pravým podstromem uzlu pravého podstromu A. |
 | Nyní provedeme RR rotaci (rotaci proti směru hodinových ručiček) na plném stromu, tedy na uzlu A. node C se nyní stal pravým podstromem uzlu B a uzel A se stal levým podstromem uzlu B. |
 | Faktor vyvážení každého uzlu je nyní buď -1, 0 nebo 1, tj. BST je nyní vyvážený. |
Otázka: Vytvořte strom AVL s následujícími prvky
H, I, J, B, A, E, C, F, D, G, K, L
1. Vložte H, I, J
Po vložení výše uvedených prvků, zejména v případě H, se BST stane nevyváženým, protože Balanční faktor H je -2. Protože BST je zkosený doprava, provedeme rotaci RR na uzlu H.
Výsledný strom bilancí je:
co je abecední číslo
2. Vložte B, A
Po vložení výše uvedených prvků, zejména v případě A, se BST stane nevyváženým, protože Balanční faktor H a I je 2, uvažujeme první uzel z posledního vloženého uzlu, tj. H. Protože BST z H je zkosený doleva, na uzlu H provedeme rotaci LL.
Výsledný strom bilancí je:
3. Vložte E
Po vložení E se BST stane nevyváženým, protože Balanční faktor I je 2, protože pokud cestujeme z E do I, zjistíme, že je vložen do levého podstromu pravého podstromu I, provedeme rotaci LR na uzlu I. LR = rotace RR + LL
3 a) Nejprve provedeme rotaci RR na uzlu B
Výsledný strom po rotaci RR je:
3b) Nejprve provedeme LL rotaci na uzlu I
Výsledný vyvážený strom po rotaci LL je:
4. Vložte C, F, D
Po vložení C, F, D, BST se stane nevyváženým, protože Balanční faktor B a H je -2, protože pokud cestujeme z D do B, zjistíme, že je vložen do pravého podstromu levého podstromu B, provedeme RL Rotace na uzlu I. RL = LL + RR rotace.
4a) Nejprve provedeme LL rotaci na uzlu E
Výsledný strom po rotaci LL je:
java string append
4b) Na uzlu B pak provedeme rotaci RR
Výsledný vyvážený strom po rotaci RR je:
5. Vložte G
Po vložení G se BST stane nevyváženým, protože Balanční faktor H je 2, protože pokud cestujeme z G do H, zjistíme, že je vložen do levého podstromu pravého podstromu H, provedeme rotaci LR na uzlu I. LR = RR + LL rotace.
numpy linspace
5 a) Nejprve provedeme rotaci RR na uzlu C
Výsledný strom po rotaci RR je:
5 b) Na uzlu H pak provedeme rotaci LL
Výsledný vyvážený strom po rotaci LL je:
6. Vložte K
Po vložení K se BST stane nevyváženým, protože Balanční faktor I je -2. Protože BST je z I do K zkosený doprava, provedeme tedy rotaci RR na uzlu I.
Výsledný vyvážený strom po rotaci RR je:
7. Vložte L
Po vložení je strom L stále vyvážený, protože Balanční faktor každého uzlu je nyní buď -1, 0, +1. Strom je tedy vyváženým stromem AVL
