An strom AVL definován jako samovyrovnávací Rozdíl mezi výškami levého podstromu a pravého podstromu pro libovolný uzel je známý jako faktor rovnováhy uzlu.

Strom AVL je pojmenován po svých vynálezcích Georgy Adelson-Velsky a Evgenii Landis, kteří jej publikovali ve svém článku z roku 1962 An algorithm for the organization of information.

Příklad AVL stromů:

strom AVL

Výše uvedený strom je AVL, protože rozdíly mezi výškami levého a pravého podstromu pro každý uzel jsou menší nebo rovné 1.

arp příkaz

Operace na stromu AVL:

• Vložení
• Vymazání
• Hledání [Je to podobné jako vyhledávání v BST]

Otočení podstromů ve stromu AVL:

Strom AVL se může otáčet jedním z následujících čtyř způsobů, aby se udržel v rovnováze:

Levá rotace :

Když je uzel přidán do pravého podstromu pravého podstromu, pokud se strom dostane do nerovnováhy, provedeme jednu rotaci doleva.

Otočení doleva ve stromu AVL

Pravá rotace :

imessage hry na android

Pokud se do levého podstromu levého podstromu přidá uzel, strom AVL se může vyvést z rovnováhy, provedeme jednu rotaci doprava.

Pravá rotace ve stromu AVL

Rotace doleva-doprava :

Rotace zleva doprava je kombinace, ve které se první rotace doleva uskuteční po provedení rotace doprava.

Otočení zleva doprava ve stromu AVL

Rotace vpravo-vlevo :

Otočení zprava doleva je kombinace, ve které dojde k prvnímu otočení doprava po provedení rotace doleva.

Otočení zprava doleva ve stromu AVL

Aplikace AVL Tree:

1. Používá se k indexování obrovských záznamů v databázi a také k efektivnímu vyhledávání v ní.
2. Pro všechny typy kolekcí v paměti, včetně sad a slovníků, se používají stromy AVL.
3. Databázové aplikace, kde jsou vkládání a mazání méně běžné, ale je nutné časté vyhledávání dat
4. Software, který potřebuje optimalizované vyhledávání.
5. Používá se ve firemních oblastech a příběhových hrách.

Výhody AVL Tree:

1. AVL stromy se mohou samy vyrovnat.
2. Zkreslená určitě není.
3. Poskytuje rychlejší vyhledávání než Red-Black Trees
4. Lepší časová složitost hledání ve srovnání s jinými stromy, jako je binární strom.
5. Výška nesmí překročit log(N), kde N je celkový počet uzlů ve stromu.

Nevýhody AVL Tree:

1. Je těžké to realizovat.
2. Pro některé operace má vysoké konstantní faktory.
3. Méně používané ve srovnání s červeno-černými stromy.
4. Vzhledem ke své poměrně přísné vyváženosti poskytují stromy AVL komplikované operace vkládání a vyjímání, protože se provádí více rotací.
5. Vezměte více zpracování pro vyvážení.

Související články:

spojení a typy spojení

• Úvod do binárních vyhledávacích stromů – výukové programy pro datovou strukturu a algoritmy
• Vložení do stromu AVL
• Odstranění ve stromu AVL