Úvod do stromu AVL ve struktuře dat

AVL Tree v datové struktuře odkazuje na Adelson, Velski & Landis Tree. Toto je vylepšená verze stromu binárního vyhledávání. Má všechny funkce jako u binárního vyhledávacího stromu, ale liší se pouze v tom, že udržuje rozdíl mezi výškou levého podřízeného stromu a pravého podřízeného stromu a také zajišťuje, že jeho hodnota je ve stromu <= 1, což se nazývá Balance. Faktor.

Balance Factor = height(left-subtree) − height(right-subtree)

Například: Zvažte následující stromy

Ve výše uvedeném příkladu je výška pravého sub-stromu = 2 a vlevo = 3, takže BF = 2, což je <= 1, je tedy považováno za vyvážené.

Proč potřebujeme strom AVL v DS?

Při práci s Binárním vyhledávacím stromem narazíme na scénář, ve kterém jsou prvky seřazené. V takových případech jsou všechny prvky pole uspořádány na jedné straně kořene, což vede ke zvýšení časové složitosti vyhledávání prvku v poli a složitost se stává-O (n), tj. Nejhorší složitost stromu . Pro vyřešení těchto problémů a zkrácení doby vyhledávání byly stromy AVL vynalezeny Adelsonem, Velskim a Landisem.

Příklad:

Na obrázku výše byla Výška levého podstromu = 3 stejná

Výška pravého podstromu = 0

Bilanční faktor = 3-0 = 3. Hledání prvku v takovém stromu má tedy O (n) složitosti, která je podobná lineárnímu vyhledávání. Aby se předešlo složitému vyhledávání, byl zaveden strom AVL, kde je třeba udržovat každý uzel ve stromu

vyrovnávací faktor <= 1, jinak se musí provést různé rotační techniky k vyvážení takového stromu.

Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);

Druhy rotací

Pokud faktor vyvážení stromu nesplňuje podmínku <= 1, musí se na nich provést rotace, aby se z něj stal vyvážený strom.

Existují 4 typy rotace:

1. Otočení doleva: Pokud přidání uzlu napravo od stromu způsobí nevyváženost, je v tomto případě nutné provést otáčení vlevo.

2. Pravá rotace: Pokud přidání uzlu vlevo od stromu způsobí nevyváženost uzlů, je třeba provést pravou rotaci. Jinými slovy, když se počet uzlů zvýší na levé straně, objeví se potřeba přemístit prvky na pravou stranu, aby se vyrovnal, takže se říká, že se jedná o pravou rotaci.

3. Rotace doleva a doprava: Tento typ rotace je kombinací výše uvedených 2 rotací. K tomuto typu rotace dochází, když je jeden prvek přidán do pravého podstromu levého stromu.

V takovém případě nejprve proveďte rotaci doleva na podstromu a poté pravou rotaci levého stromu.

4. Pravá a levá rotace: Tento typ rotace je také složen ze sekvence nad 2 rotacemi. Tento typ rotace je nutný, když je prvek přidán vlevo od pravého podstromu a strom je nevyvážený. V takovém případě nejprve provedeme pravou rotaci na pravém podstromu a poté levou rotaci na pravém stromě.

Operace na stromě AVL v DS

Pod 3 operacemi, které lze provádět ve stromu AVL: -

1. Hledání

Tato operace je podobná provádění vyhledávání ve stromu binárního vyhledávání. Následující kroky jsou následující:

  • Přečtěte si prvek poskytnutý uživatelem vyslovte x.
  • Porovnejte prvek z kořenového adresáře, pokud je stejný, pak opusťte jinak, přejděte k dalšímu kroku.
  • Pokud x

Jinak jděte ke správnému dítěti a porovnejte znovu.

Postupujte podle procesů B a C, dokud nenajdete prvek a neukončíte.

Tento proces má složitost O (log n).

Příklad:

Zvažte tento strom, kde musíme provést hledání hodnoty uzlu 9.
Nejprve x = 9, kořenová hodnota (12)> x, pak musí být hodnota v levém podstromu kořenového prvku.
Nyní je x porovnáno s hodnotou uzlu 3
x> 3, takže musíme postupovat směrem k pravému podstromu.
Nyní je x ve srovnání s uzlem (9), kde 9 == 9 vrací true. Hledání prvku se tak ve stromu dokončí.

2. Vložení

Při vkládání prvku do stromu AVL musíme najít umístění konkrétního prvku, který je třeba vložit, a pak je prvek připojen jako vložení v BST, ale poté se zkontroluje, zda je strom stále vyvážený nebo ne tj. vyrovnávací faktor uzlu je <= 1. A konkrétní rotace se provádějí podle potřeby.

Složitost je O (log n).
Příklad: Zvažte níže uvedený strom,

Každý uzel má vyrovnávací faktor jako 0, -1 nebo 1, takže strom je vyrovnaný. Nyní umožňuje, co se stane, když je vložen uzel s hodnotou 1.
První strom projde, aby našel místo, kam je třeba vložit…
1 <2 je tedy zapsáno jako levé dítě uzlu (2).
Po vložení se uzel (9) stane nevyváženým s faktorem vyvážení = 2. Nyní je podroben pravé rotaci.
Strom se stane rovnováhou po otočení doprava a operace vložení je úspěšně dokončena.

3. Vymazání

Odstranění prvku ve stromu AVL také zahrnuje prohledávání prvku ve stromu a jeho odstranění. Operace vyhledávání je stejná jako BST a po nalezení prvku, který má být odstraněn, je prvek odstraněn ze stromu a prvky jsou upraveny tak, aby se znovu stal BST. Poté, co jsou tyto prvky zkontrolovány, aby měly vyrovnávací faktor 0, -1 nebo 1, a proto jsou provedeny vhodné rotace, aby byl vyvážen.

Složitost, pokud O (log n).

Zvažte daný strom, jehož všechny mají vyvažovací faktor 0, -1 nebo 1.
Nyní odstraníme uzel s hodnotou 16.
První strom prochází, aby našel uzel s hodnotou 16 stejnou jako prohledávací algoritmus.
Uzel 16 bude nahrazen inorder předchůdcem tohoto uzlu, který je největším prvkem z levého podstromu, tj. 12
Strom se stal nevyváženým, takže je třeba provést rotaci LL.
Nyní se každý uzel vyrovnal.

Závěr - strom AVL ve struktuře dat

Strom AVL je potomkem stromu binárního vyhledávání, ale překonává jeho nevýhodu rostoucí složitosti v případě třídění prvků. Monitoruje vyrovnávací faktor stromu na 0 nebo 1 nebo -1. V případě, že se strom stane nevyváženým, jsou provedeny odpovídající rotační techniky, aby se strom vyrovnal.

Doporučené články

Toto je průvodce stromem AVL ve struktuře dat. Zde diskutujeme úvod, operace na AVL stromu v DS a typy rotací. Další informace naleznete také v dalších souvisejících článcích -

  1. jQuery Elements
  2. Co je to Data Science
  3. Typy stromů ve struktuře dat
  4. C # Typy dat

Kategorie:

Velká data